• MySQL衡量查询效率的标准就是磁盘IO次数（对索引的使用效率至关重要）
• 加速查找速度的数据结构，基本分为以下两类：
  • 树，增删改查的平均时间复杂度都是O(log2N)
  • 哈希（hash），增删改查的平均时间复杂度都是O(1)

1、哈希索引（Hash结构）

• Hash本身就是一种（散列）函数，可以大幅度提升检索数据的效率

• 是通过某种确定的算法将输入变为输出。相同的输入永远可以得到相同的输出。

• 从效率来说Hash比B+树更快

• 不适用性：

  • Hash索引仅能满足 = ，!= , in 的查询。如果进行范围查询，哈希型索引时间复杂度就会退化为O(n)
  • Hash型数据的存储是没有顺序的，在order by下，使用Hash索引还需要对数据重新排序
  • 基于联合索引，Hash值将联合索引键合并后一起计算，无法单独对一个键或多个索引键进行查询
  • 对等值查询来说，Hash索引效率更高，但索引列的重复值很多，效率会降低

• 适用性：

  • 在键值型（key-value）数据库中，如Redis（存储核心就是Hash表）
  • 经常需要等值查询的时候
  • 提供自适应Hash索引（如InnoDB中不支持Hash索引，当一些数据经常被访问满足一定条件时就会将数据页的地址存放到Hash表中）

• 可以通过查看并配置 adaptive_hash_index 参数来设置是否开启自适应Hash。

mysql> show variables like '%adaptive_hash_index';
+----------------------------+-------+
| Variable_name              | Value |
+----------------------------+-------+
| innodb_adaptive_hash_index | ON    |
+----------------------------+-------+
1 row in set (0.01 sec)

2、二叉搜索树

磁盘IO的次数与树的高度相关

• 特点：
  • 一个节点只能有两个子节点（节点度不能超过2）、
  • 左子节点<父节点<右子节点
• 查找规则：
  • 如果key大于根节点，则在右子树中进行查找
  • 如果key小于根节点，则在左子树中进行查找
  • 如果key等于根节点，则返回根节点

3、平衡二叉树（AVL索引）

在二叉树的基础上增加了相关约束

• 左右两个子树的高度差的绝对值不能超过1，并且左右两个子树都是一颗平衡二叉树，时间复杂度O(log2N)
• 常见平衡二叉树：
  • 平衡二叉搜索树
  • 红黑树
  • 树堆
  • 伸展树

4、B-Tree（多路平衡二叉树）

• 每个节点可以包含M个子节点，M称为B-Tree的阶。
• 每个磁盘块中包含关键字和子节点的指针（若磁盘块中包含X个关键字，则指针数为X+1）
• 特性：
  • 根节点的子节点数的范围为[2,M]
  • 每个中间节点包含k-1个关键字和K个子节点，子节点的数量= 关键字的数量+1，k的取值范围为[ceil(M/2),M]
  • 叶子节点包括k-1个关键字（没有子节点），k的取值范围为：[ceil(M/2),M]
  • 所有叶子节点位于同一层

5、B+Tree（多路搜索树）

基于 B-Tree改进，B+Tree更适合文件索引系统

• 特性：
  • 有k个子节点的节点就有k个关键字
  • 非叶子节点的关键字也会同时存在子节点中，并且是在子节点中所有关键字中最大（或最小）
  • 非叶子节点仅用于索引，不保留数据记录，跟记录相关的信息都放在叶子节点中（B-Tree中，非叶子节点既保存索引也保存数据记录）
  • 所有关键字都在叶子节点中出现，叶子节点构成一个有序链表，叶子节点本身按照关键字的大小从小到大顺序链接。

6、R树（存储高维数据的平衡树）