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

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

This topic created in 2295 days ago, the information mentioned may be changed or developed.

传统的关系型数据库，如 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 replies • 2020-02-24 09:06:48 +08:00

xupefei

Feb 23, 2020

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

Feb 23, 2020

@xupefei 是这样的吗？ Thanks ！

lhx2008

Feb 24, 2020 via Android

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