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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

请不要在回答技术问题时复制粘贴 AI 生成的内容

这是一个创建于 2251 天前的主题，其中的信息可能已经有所发展或是发生改变。

传统的关系型数据库，如 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 的叶子节点上面），接下来会怎么处理？找了很久都没才找到相关的资料

索引

MongoDB

b-tree

查询

3 条回复 2020-02-24 09:06:48 +08:00

xupefei

2020 年 2 月 23 日

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

2020 年 2 月 23 日

@xupefei 是这样的吗？ Thanks ！

lhx2008

2020 年 2 月 24 日 via Android

BTree 是搜索树的一种，本来就可以范围查找。不能的话用 hashmap 就行了。