索引结构

索引结构分类

支持情况

二叉查找树

缺点：

• 不平衡，顺序插入时，形成链表（退化），查询性能大大降低。
• 大数据量情况下，层级较深，检索速度慢。

AVL

缺点：旋转耗时

红黑树

性质 1. 结点是红色或黑色。

性质 2. 根结点是黑色。

性质 3. 所有叶子都是黑色。（叶子是 NIL 结点）

性质 4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）

性质 5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

优点：相比于 AVL 树，无需频繁旋转，更加省时

缺点：大数据量情况下，层级仍然较深，检索速度慢

B-Tree

（多路平衡查找树）

以一颗最大度数(max-degree)为 5 阶的 b-tree 为例(每个节点最多存储 4 个 key，5 个指针)，中间元素向上分裂。

缺点

• 每个节点均存数据，记录的子树有限，层数相对还是较深。

B+Tree

所有的数据都会在叶子结点层

上面的元素只起索引的作用

叶子结点形成一个单向链表

中间元素向上分裂，同时会保留在右子树里

数据存储只在叶子结点中

MySQL 中对 B+Tree 进行了优化，叶子层单向指针变成双向，更加便于范围查询

一页 16k，上面层，每一个节点都只存 key 和指针，就可以存很多很多

InnoDB 主键索引 B+tree 高度估算：

一个页 16k，一层大概有 1171 个指针

2 层是 2w 数据，即使存 2kw 多的数据，也只有 3 层

优点：

• 更少的 IO 次数：B+树的非叶节点只包含键，而不包含真实数据，因此每个节点存储的记录个数比 B 数多很多（即阶 m 更大），因此 B+树的高度更低，访问时所需要的 IO 次数更少。此外，由于每个节点存储的记录数更多，所以对访问局部性原理的利用更好，缓存命中率更高。
• 更适于范围查询：在 B 树中进行范围查询时，首先找到要查找的下限，然后对 B 树进行中序遍历，直到找到查找的上限；而 B+树的范围查询，只需要对链表进行遍历即可。
• 更稳定的查询效率：B 树的查询时间复杂度在 1 到树高之间(分别对应记录在根节点和叶节点)，而 B+树的查询复杂度则稳定为树高，因为所有数据都在叶节点。

劣势：由于键会重复出现，因此会占用更多的空间。但是与带来的性能优势相比，空间劣势往往可以接受，因此 B+树的在数据库中的使用比 B 树更加广泛。

Hash 索引

特点：冲突时，就用链表存储

优点：查询效率高，O1

缺点：只支持等值匹配，不支持范围索引和排序操作

只有 Memory 引擎支持

而 InnoDB 中具有自适应 Hash 索引（内存结构 Buffer Pool），满足条件时，自动设计为 Hash

为什么 MySQL 采用 B+ 树

• 相对于二叉树，层级更少，搜索效率高；

• 相对于 B-tree，

  • 无论是叶子节点还是非叶子节点，都会存数据，这样导致一页中存储的键值减少，指针跟着减少，要同样保存大量数据，只能增加树的高度，导致性能降低；

  • 而且 B+搜索效率稳定，而且最下层有双向链表，便于范围搜索和排序

• 相比于 Hash，B+支持范围索引（模糊查询）和排序操作