跳转至

多路搜索树

https://www.cnblogs.com/bbgs-xc/p/14181810.html

https://developer.aliyun.com/article/843299

B-树（Balanced Tree）

https://blog.csdn.net/sinat_34072381/article/details/107197754#:~:text=%E7%BA%A2%E9%BB%91%E6%A0%91%E4%B8%BA%E4%BA%8C,%E8%8A%82%E7%82%B9%EF%BC%8C%E6%95%B0%E6%8D%AE%E6%90%9C%E7%B4%A2%E6%95%88%E7%8E%87%E4%B8%80%E8%87%B4%E3%80%82

B+树

img

B+树 内部节点不存储关键字指向的数据地址，数据地址全部存储在叶节点，必须遍历到叶节点才能获得数据地址，所有数据的查询效率一致，查询稳定，而B树内部节点保存有关键字指向的数据地址，靠近根节点的数据查询效率较高。

B+树内节点不保存数值指针，内节点占用空间较小（增加了所有内节点读取到内存的可能），树的阶/度更大，深度更低，读取索引文件进行的IO次数也更小。外节点顺序排序，具备良好的空间局部性，缓存命中率高。

B+树内节点关键字数等于孩子指针数，指针指向包含当前关键字的孩子节点，因此 B+树各内节点关键字可能出现重复，B树内节点关键字数等于孩子指针数减一，指针指向大于或小于当前关键字的孩子节点，B树关键字不重复。

B+树内部节点相当于叶节点的索引，叶节点中的关键字组成有序链表，便于区间搜索和遍历，B+树搜索性能几乎等价于二分搜索。

探究 MySQL 中的索引实现

https://www.cnblogs.com/yufeng218/p/12465694.html

B *树

https://zhuanlan.zhihu.com/p/27700617