BTree、B+Tree和HASH索引

  hash索引的特点是检索效率非常高，检索一次就可以定位，BTree需要从根节点往下查找，经过多次IO访问才能找到结果，所以hash索引的效率远高于BTree。
但hash自身也有很多局限与缺陷：
1.hash只能通过索引精准定位目标，而不能进行范围查询。
2.因为hash只保存了经过hash计算之后的hash值和对应的行指针，所以无法用于排序。
3.hash索引如果遇到大量hash值相等的情况，那么大量的记录指针信息会存于同一个hash值上，这样要定位一条记录时就会很麻烦，最终效率不一定会比BTree索引高。
4.对于组合索引，hash索引会把组合索引合并一起后再计算hash值，而不是各自单独计算hash值，所以通过组合索引前面几个索引键值时，hash索引无法使用。
5.因为不同索引键有可能存在相同的hash值，所以hash索引任何时候都不能避免全表扫描。

BTree又叫平衡多路查找树。一棵m阶的B 树 (m叉树)的特性如下：
1.树中每个结点最多含有m个孩子（m>=2）；
2.除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数）；
3.若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；
4.所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息
5. 每个非终端节点包含n个关键字信息（P0,P1,…Pn, k1,…kn）
6. 关键字的个数n满足：ceil(m/2)-1 <= n <= m-1
7. ki(i=1,…n)为关键字，且关键字升序排序。
8. Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)

B+Tree是在BTree基础上的一种优化。
1.非叶子节点只存储键值信息。这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。
2.所有叶子节点之间都有一个链指针。遍历起来更方便。
3.数据记录都存放在叶子节点中。

参考资料：
包含了二叉树、平衡二叉树、平衡多路查找树（BTree）
https://blog.csdn.net/hao65103940/article/details/89032538