B+Tree树
实际上它就是B树的变种,以一颗最大度数(max-degree)为4(4阶)的b+tree为例:所有的元素都会出现在叶子节点,
叶子节点形成一个单向链表,每一个节点都会通过一个指针指向下一个元素。
Mysql索引数据结构对经典的B+Tree树结构进行了优化。在原B+Tree树的基础上,增加了一个指向相邻叶子节点的链表指针,就形成了一个带有顺序指针的B+Tree,提高区间的访问性能。有利于数据库的排序操作。
每个数据节点都是存储在一个页当中的。
可以通过一个数据结构可视化的网站来简单演示一下。 https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
插入一组数据: 100 65 169 368 900 556 780 35 215 1200 234 888 158 90 1000 88 120 268 250 。然后观察一些数据插入过程中,节点的变化情况。
最终我们看到,B+Tree 与 B-Tree相比,主要有以下三点区别:
所有的数据都会出现在叶子节点。
叶子节点形成一个单向链表。
非叶子节点仅仅起到索引数据作用,具体的数据都是在叶子节点存放的。
MySQL索引数据结构对经典的B+Tree进行了优化。在原B+Tree的基础上,增加一个指向相邻叶子节点
的链表指针,就形成了带有顺序指针的B+Tree,提高区间访问的性能,利于排序。
来源:https://www.cnblogs.com/wekenyblog/p/17173436.html
免责声明:由于采集信息均来自互联网,如果侵犯了您的权益,请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容,谢谢合作!
页:
[1]