1、BTree结构
BTree又叫多路平衡搜索树，一颗m叉树的BTree特性如下：
- 树中每个节点多个包含m个子节点
- 若根节点不是叶子节点，则至少有两个子节点
- 除根节点合叶子节点外，每个节点至少有[ceil(m/2)]个子节点
- 所有的叶子节点都在同一层
- 每个非叶子节点由n可key和n+1个指针组成，其中[ceil(m/2)-1]<= n <= m-1
以5叉Btree为例，key的数量：公式推导[ceil(m/2)-1]<= n <= m-1。
2 <= n <= 4。当n>4时，中间节点分裂到父节点，两边节点分裂。
插入3、14、7、1、8、5、11、17、13、6、23、12、20、26、4、16、18、24、25、19数据为例
1）插入前四个数字 3、14、10、1
2）插入8，n>4，中间元素7向上分裂到新的节点
3）插入5、11、17不需要分裂
4）插入13，中间元素13向上分裂到父节点7
5）插入6、23、12、20不需要分裂
6）插入26，中间元素20向上分裂到父节点中
7）插入4，中间元素4向上分裂到父节点中，然后插入16、18、24、25不需要分裂
8）最后插入19，第三个子节点n>5中间节点17向上分裂，但分裂后父节点n>5中间节点13向上分裂
2、B+Tree结构
B+Tree为BTree的变种，B+Tree与BTree的区别为：
- B+Tree最多含有n个key，BTree最多含有n-1个key
- B+Tree的叶子节点保存所有的key信息，根据key大小排序排列
- 所有的非叶子节点都可以看作是key的索引部分
由于B+Tree只有叶子节点保存key信息，查询任何key都要从根节点走到叶子节点，所有B+Tree查询效率更加稳定
3、MySQL中B+Tree结构
MySql索引数据结构对B+Tree进行了优化。在原B+Tree的基础上，增加一个相邻叶子节点的链表指针，提高区间查询的性能
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/148666.html
