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

[LoremIpSum]

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

[xupefei]

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]

@xupefei 是这样的吗？ Thanks ！

[lhx2008]

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