一文讲透索引数据结构——B-Tree / B+Tree / Hash 的特点及对比
B-Tree
二叉树的缺点：
B-Tree（多路平衡查找树）
B+Tree
01-标准的B+Tree结构
演变过程：分裂时中间元素向上分裂，同时该中间元素会停留在分裂后的右子树中，这样才能保证所有的数据会出现在叶子结点
相对于B-Tree区别：
- 所有的数据都会出现在叶子节点
- 叶子节点形成一个单向链表
02-MySQL索引中的B+Tree结构
MySQL索引数据结构对经典的B+Tree进行了优化。在原B+Tree的基础上，增加一个指向相邻叶子节点的链表指针，就形成了带有顺序指针的B+Tree，提高区间访问的性能
Hash
哈希索引就是采用一定的hash算法，将键值换算成新的hash值，映射到对应的槽位上，然后存储在hash表中；
如果两个(或多个)键值，映射到一个相同的槽位上，他们就产生了hash冲突（也称为hash碰撞），可以通过链表来解决
Hash索引特点：
- Hash索引只能用于对等比较(=，in)，不支持范围查询（between，>，< ，...）
- 无法利用索引完成排序操作（Hash运算出来的结果是无序的）
- 查询效率高，通常（不存在hash冲突的情况）只需要一次检索就可以了，效率通常要高于B+tree索引
存储引擎支持：
在MySQL中，支持hash索引的是Memory存储引擎
而InnoDB中具有自适应hash功能，hash索引是InnoDB存储引擎根据B+Tree索引在指定条件下自动构建的
为什么InnoDB存储引擎选择使用B+tree索引结构？
- 相对于二叉树，层级更少，搜索效率高；
对于B-Tree，无论是叶子节点还是非叶子节点，都会保存数据，这样导致一页中存储的键值减少，指针跟着减少，在保存相同数据量的情况下，只能增加树的高度，导致性能降低
- 如果采用B+Tree索引结构，不管查找哪一个数据都要到叶子结点当中才能找到对应的数据，搜索效率更稳定；
- 在B+Tree索引结构中，叶子结点形成了一个双向链表，便于范围搜索和排序
- 相对Hash索引，B+tree支持范围匹配及排序操作
这个可以作为面试题好好理解下