数据结构与算法-树结构-多路查找树-笔记整理《十八》

二叉树问题分析

二叉树需要加载到内存中，节点少的情况下没问题，节点多的情况下：

1. 在构建二叉树时需要多次io，构建速度慢
2. 节点海量，二叉树高度大，降低操作速度

B树

B树中的B是Balanced的意思，B树即多路平衡搜索树

B树简介：

1. B树的阶：节点最多子节点的个数
2. B树的搜索：从根节点开始对节点的关键字进行二分查找，命中则结束；否则查询关键字所属范围的儿子节点，直到儿子指针为空或已是叶子节点
3. 叶子节点与非叶子节点都存放数据
4. 搜索可能在非叶子节点结束
5. 搜索性能相当于在全局关键字集合做一次二分查找

B+树

B+树简介：
B+树是B树的变体，也是一种多路搜索树

1. B+树性能也等价于在关键字全集做一次二分查找，与B树的区别是只有达到叶子节点才命中
2. 数据只存放在叶子节点，也称为稠密索引
3. 非叶子节点是叶子节点的索引，称之为稀疏索引，叶子节点相当于存储关键字数据的数据层

MySQL中的B+Tree：
MySQL原B+Tree的基础上，增加一个指向相邻叶子节点的链表指针，就形成了带有顺序指针的B+Tree，提高区间访问的性能。

B*树

B*树是B+树的变体，在B+树的非根非叶子节点增加指向兄弟的指针

1. B树块最低利用率为2/3，而B+树块最低使用率为1/2，所以B树的空间使用率更高