使用 B-tree 来进行索引的 MongoDB 是怎么处理一个范围查询的？
LoremIpSum · 2020-02-23 23:05:57 +08:00 · 2396 次点击这是一个创建于 1736 天前的主题，其中的信息可能已经有所发展或是发生改变。
传统的关系型数据库，如 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 的叶子节点上面）， 接下来会怎么处理？找了很久都没才找到相关的资料
 |
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。 |
 |
2
LoremIpSum OP @xupefei 是这样的吗？ Thanks ！
|
 |
3
lhx2008 2020-02-24 09:06:48 +08:00 via Android
BTree 是搜索树的一种，本来就可以范围查找。不能的话用 hashmap 就行了。
|
Select Language