V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
NoKey
V2EX  ›  程序员

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

  •  
  •   NoKey · 2021-03-12 00:30:31 +08:00 · 2490 次点击
    这是一个创建于 1113 天前的主题,其中的信息可能已经有所发展或是发生改变。

    之前面试遇到的问题

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

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

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

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

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

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

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

    但是这种方式有一些问题

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

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

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

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

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

    15 条回复    2021-03-30 23:20:24 +08:00
    ericls
        1
    ericls  
       2021-03-12 00:37:06 +08:00 via iPhone   ❤️ 1
    直接用一个中间表不可以吗?做过 benchmark 吗? 你为什么觉得这个快?
    cassyfar
        2
    cassyfar  
       2021-03-12 02:03:22 +08:00
    为啥要存成 bitmap 呢?直接存 type id 啊。然后再来个表解释这个 type id 具体什么 type 。
    chendy
        3
    chendy  
       2021-03-12 02:05:26 +08:00
    常规多对多中间表实现有什么问题么……
    这么搞性能不知道啥样但是扩展性和可维护性都差啊
    mingl0280
        4
    mingl0280  
       2021-03-12 04:18:16 +08:00 via Android
    bitmap 你牛逼……
    数据库的做法是中间表以商品 id 和分类做一个复合主键完事。
    fiypig
        5
    fiypig  
       2021-03-12 06:47:10 +08:00 via iPhone
    你这个方法复杂化了吧?
    tedzhou1221
        6
    tedzhou1221  
       2021-03-12 08:59:59 +08:00
    bitmap 这放到优化的阶段用是不是好点?例如直接用 redis 的 bitset

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

    之前做过类型的,譬如:用户画像表,根据用户标签找到对应广告位置。但公司小,就只有 Mysql,所以简单做了。
    dongtingyue
        7
    dongtingyue  
       2021-03-12 09:40:40 +08:00
    就不能回答实际中常用的方式么。
    1461665214
        8
    1461665214  
       2021-03-12 09:46:24 +08:00
    hahaha 简单问题复杂化
    MoYi123
        9
    MoYi123  
       2021-03-12 09:49:24 +08:00
    倒排索引,或者中间表。
    hehe12980
        10
    hehe12980  
       2021-03-12 10:09:39 +08:00
    为什么要这么麻烦呢 你商品分类,按道理 spu 里有个字段肯定叫商品类型,商品类型可以用一张表,这张表可以参考树的思想实现也就是说转换到代码里其实是一颗多叉树,那么前台给我一个商品 id,我可以用这颗树快速定位类型,然后 spu 建一个索引就能快速定位啊,为啥还整到 bitmap 里去了,感觉完全没必要
    iceteacover
        11
    iceteacover  
       2021-03-12 10:36:12 +08:00   ❤️ 2
    题主遇到的问题大概是商品分类膨胀很快,一个商品被分到很多类别里面,然后根据类别搜索商品的时候就会慢。

    一开始,中间表,存类别 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
        12
    Rocketer  
       2021-03-12 23:49:30 +08:00 via iPhone
    别过度设计,这个问题就是经典的三表结构。作为商品分类,撑死了也就 5 位数,做好索引按分类 ID 在分类-商品表中检索,性能不会差。

    除非你不是真正的商品,而是像微博那样的 timeline,一条发言归属于多个 timeline,那就是另一种解决方案了。现在普遍采用的是空间换时间,每个 timeline 都存一份,不用临时算
    NoKey
        13
    NoKey  
    OP
       2021-03-16 23:17:00 +08:00
    @chendy 主要是我不太清楚多对多的时候,怎么查出来
    比如,举例物品和种类的对应关系表
    物品 1 种类 1
    物品 1 种类 2
    物品 1 种类 3
    物品 2 种类 1
    物品 3 种类 1
    物品 3 种类 2

    现在要查出,即是种类 1,又是种类 2 的物品
    这样的 sql,应该怎么写啊。
    NoKey
        14
    NoKey  
    OP
       2021-03-17 22:42:12 +08:00
    @ericls
    比如,举例物品和种类的对应关系表
    物品 1 种类 1
    物品 1 种类 2
    物品 1 种类 3
    物品 2 种类 1
    物品 3 种类 1
    物品 3 种类 2

    现在要查出,即是种类 1,又是种类 2 的物品
    这样的 sql,应该怎么写啊。
    NoKey
        15
    NoKey  
    OP
       2021-03-30 23:20:24 +08:00
    有哪位大佬能告知一下,多表关联的话,sql 怎么写么
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3552 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 04:49 · PVG 12:49 · LAX 21:49 · JFK 00:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.