数据库里的B+树为啥要用个指针把最底层的相邻叶节点连起来？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

数据库里的B+树为啥要用个指针把最底层的相邻叶节点连起来？

数据库里的B+树为啥要用个指针把最底层的相邻叶节点连起来？# JobHunting - 待字闺中

m*g2018-08-23 07:08

1 楼

在B+树里，最底下一层的节点是叶节点，前一个
叶节点的最后一块地方里要放上后一个叶节点的
内存地址。
在B+树里查找一个数据（比方说查找一个学生的
编号）都是从根节点开始向下一层一层找，直到
第一次找到最底下的一层叶节点，就能找到这个
学生的学号。而并没有在叶节点之间有向右漂移
查找的动作，那么这个把相邻叶节点之间连起来
的指针有啥用啊？

K*s2018-08-23 07:08

2 楼

便于做range scan/iterator

m*g2018-08-23 07:08

3 楼

能展开说说吗？谢谢了

【在 K***s 的大作中提到】

: 便于做range scan/iterator

K*s2018-08-23 07:08

4 楼

https://en.wikipedia.org/wiki/B%2B_tree#Implementation

【在 m********g 的大作中提到】

: 能展开说说吗？谢谢了

z*f2018-08-23 07:08

5 楼

如同上面克罗斯说的，你说的这个连接相邻的叶子结点的指针，有利于范围查找；举个
例子，如果单个statement，比如select studentID where studentID = 123, 这样的
确找到最底下的叶子结点就完成了，并没有向右漂移；但如果是select studentID
where studentID > 100这样的范围查找呢？因为结果可能在不同叶子结点里面；想想B
树，没有这个指针，只能中序遍历来找到所有的结果，而在B+树里有这个指针，那就直
接是链表的操作了，只要定义了范围的min和max，那么中间的所有叶子节点，就是结果
集，不用再去中序遍历，所以有了这个指针，range scan是不是快了很多？
另外，B+树跟B树还有一点不一样的是，root到不同叶子结点的距离都是一样的，叶子
结点存储实际数据，非叶子结点只存储PK，前者适合磁盘存储，后者适合内存存储，所
以相同内存下B+树可以存更多的索引，便于加速查找。