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

使用 B-tree 来进行索引的 MongoDB 是怎么处理一个范围查询的?

  •  
  •   LoremIpSum · 2020-02-23 23:05:57 +08:00 · 2036 次点击
    这是一个创建于 1069 天前的主题,其中的信息可能已经有所发展或是发生改变。

    传统的关系型数据库,如 Mysql,SqlServer 都是用 B+tree 来进行索引的,也就是说如果执行一个范围查询如:

    SELECT * FROM USERS A WHERE A.Id BETWEEN 5 AND 1000;
    

    这个时候查询优化器会使用主键 ID 上的唯一索引先找到 ID=5 的记录,然后以此去遍历叶子节点上面的记录,直到 ID>1000 的时候停止。

    那么好,问题来了,MongoDb 使用 B-tree 进行索引,那么意味着叶子节点之间不是以链表的形式链接在一起的,这个时候同样的查询,假设 MongoDB 找到了记录为 5 的记录(并且这个时候这笔 ID 为 5 的记录就是在 B-tree 的叶子节点上面), 接下来会怎么处理?找了很久都没才找到相关的资料

    3 条回复    2020-02-24 09:06:48 +08:00
    xupefei
        1
    xupefei  
       2020-02-23 23:21:15 +08:00
    B tree 也是可以运行 range query 的。需要访问多个节点,把数据组合起来。
    比如这个数 https://media.geeksforgeeks.org/wp-content/cdn-uploads/BTreeIntro1.png 里,想拿到所有的<20 就要访问三个节点:3 30 60,1 2,4 5 6。最后组合的结果是 1 2 3 4 5 6。
    LoremIpSum
        2
    LoremIpSum  
    OP
       2020-02-23 23:27:18 +08:00
    @xupefei 是这样的吗? Thanks !
    lhx2008
        3
    lhx2008  
       2020-02-24 09:06:48 +08:00 via Android
    BTree 是搜索树的一种,本来就可以范围查找。不能的话用 hashmap 就行了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   实用小工具   ·   2432 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 58ms · UTC 07:07 · PVG 15:07 · LAX 23:07 · JFK 02:07
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.