二叉树问题分析
二叉树需要加载到内存中，节点少的情况下没问题，节点多的情况下：
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树的空间使用率更高；
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: