企业官网建设流程全解析

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支持范围匹配及排序操作

这个可以作为面试题好好理解下