面试题，商品有多种分类，如何快速查找？

之前面试遇到的问题

问题就是数据库保存商品，商品有分类

比如同一个商品，可以是数码产品，可以是热门商品，可以是奢侈品等等

现在用 mysql 来存这个商品，要有分类信息

在进行查询分类的时候，如何快速查找

按照常规做法，就是类似于 bitmap

属于哪个商品，就在二进制位上标 1，存数据库的时候转为十进制存入

查询的时候，根据要查询的商品组合，搜索这个十进制数

但是这种方式有一些问题

第一，十进制数受限于数字最大值，肯定有个上限，几千种种类就没法表示了

第二，如果存如二进制字符串，那搜索就成问题

第三，比如二进制 101 111 1111 这几个值，在从右往左第 1 位和第 3 位都为 1，这个时候要挑选出这两类商品就

不好办了，总不至于把所有数字搜一次吧。

请教各位大佬，有没有比较简单的办法实现呢？谢谢

ericls

2021-03-12 00:37:06 +08:00

直接用一个中间表不可以吗？做过 benchmark 吗？你为什么觉得这个快？

cassyfar

2021-03-12 02:03:22 +08:00

为啥要存成 bitmap 呢？直接存 type id 啊。然后再来个表解释这个 type id 具体什么 type 。

chendy

2021-03-12 02:05:26 +08:00

常规多对多中间表实现有什么问题么……
这么搞性能不知道啥样但是扩展性和可维护性都差啊

mingl0280

2021-03-12 04:18:16 +08:00

bitmap 你牛逼……
数据库的做法是中间表以商品 id 和分类做一个复合主键完事。

fiypig

2021-03-12 06:47:10 +08:00

你这个方法复杂化了吧？

tedzhou1221

2021-03-12 08:59:59 +08:00

bitmap 这放到优化的阶段用是不是好点？例如直接用 redis 的 bitset

存储还中间表好点，起码别人接手方便。如果你们有 ES 或其他大数据平台的组件也可以。

之前做过类型的，譬如：用户画像表，根据用户标签找到对应广告位置。但公司小，就只有 Mysql，所以简单做了。

dongtingyue

2021-03-12 09:40:40 +08:00

就不能回答实际中常用的方式么。

1461665214

2021-03-12 09:46:24 +08:00

hahaha 简单问题复杂化

MoYi123

2021-03-12 09:49:24 +08:00

倒排索引，或者中间表。

hehe12980

2021-03-12 10:09:39 +08:00

为什么要这么麻烦呢你商品分类，按道理 spu 里有个字段肯定叫商品类型，商品类型可以用一张表，这张表可以参考树的思想实现也就是说转换到代码里其实是一颗多叉树，那么前台给我一个商品 id，我可以用这颗树快速定位类型，然后 spu 建一个索引就能快速定位啊，为啥还整到 bitmap 里去了，感觉完全没必要

iceteacover

2021-03-12 10:36:12 +08:00

题主遇到的问题大概是商品分类膨胀很快，一个商品被分到很多类别里面，然后根据类别搜索商品的时候就会慢。

一开始，中间表，存类别 ID+商品 ID，用 MySQL，单表数量在百万级别速度都还是可以。也就是万级别商品 * 百级别分类。

再往上叠加，MySQL 估计性能就要下降了，考虑优化数据库，分库分表之类。

撑不住了就要上搜索引擎，ElasticSearch Solr 之类的用起来，性能肯定没问题，唯一可能遇到的问题是商品和分类反复修改带来的数据不一致，看能做到什么程度，如果商品和分类业务做得好，修改消息出来比较统一，那么可以做到近乎实时，最多叠加一个隔段时间刷新全量数据的异步就可以了。

搜索引擎是一劳永逸的方法，代价当然也很高。讨巧点用 redis 的 set 就也蛮好，每个分类一个 key，分类下的商品 ID 都存在这个 key 的 set 里面。性能方面几乎没啥问题，要注意的还是数据一致性的保证。消息之类的中间价不可少。另外 redis 本身还有一些限制，比如如果某个 set 非常大（几百万），redis 对这个 key 的存储空间会指数级上涨，原因是底层存储会改成用跳表（有点忘记了）。应对方式是切成几个 key 存储，比如有个叫食品的分类，那么可以指定 key=食品 1/食品 2/食品 3/... 然后识别每个 key 的 set 数量（ O （ 1 ）复杂度）每次添加的时候判断 set 是否超过阀值，超过就放新 key 。

方案应该好聊的，就是要和数据量级匹配，慢的地方改改就好了。

bitmap 是种数据格式，哪里都能用，MySQL Redis 或者其他的都可以，不过一般是用来放增长不怎么快的，比如判断用户有无什么身份，分类的话涨的还蛮快，而且不是单一判断而是有业务含义，感觉不大合适 bitmap 。

Rocketer

2021-03-12 23:49:30 +08:00

别过度设计，这个问题就是经典的三表结构。作为商品分类，撑死了也就 5 位数，做好索引按分类 ID 在分类-商品表中检索，性能不会差。

除非你不是真正的商品，而是像微博那样的 timeline，一条发言归属于多个 timeline，那就是另一种解决方案了。现在普遍采用的是空间换时间，每个 timeline 都存一份，不用临时算