什么是索引
索引是一种为表提供快速查找能力的数据结构，通常用树型结构表示。
为什么使用树形结构？
为了加速查找速度，常见有两类：
- 哈希
例如HashMap，插入/删除/修改/查询的时间复杂度都是O(1) - 树
例如平衡二叉树，插入/删除/修改/查询的时间复杂度都是O(lg(n))
不管是读请求还是写请求，哈希类型的索引都要快一些，那为什么要设计成树形呢？
这与SQL的需求有关（任何设计都来源于需求）：
对于一个精确查询的SQL，例如：select id from t where name = 'dingxiaoyuan';确实是哈希更快
但是对于范围查询（>、<等），哈希的时间复杂度会退化成O(n)，平衡二叉树自身就是有序的，所以能够保持O(lg(n))
InnoDB的自适应哈希就是哈希索引，是对查询的一种优化，所以说并不是不用。
为什么使用B+树？
下面我们逐一分析原因：
1. 为什么不使用二叉搜索树？
- 数据量大时，树的高度比较高，查询效率比较低
- 每个节点只有一条记录，发生多次磁盘I/O
2. 为什么不使用传统的B树？
B树适用于索引的原因：
- B树是一颗m叉树，可以有多个子节点，可以减低数据的高度
- 每个节点可以有多个记录，可以充分利用预读机制，减少磁盘I/O
对于B树而言，每个节点的数据存储在连续区域内，如果节点大小与操作系统页大小相等，可以充分利用与独特性磁盘预读：磁盘不是按需读写，每次都会读取一页数据
局部性原理：一个数据被用到时，其附近的数据大概率会被用到
但是，对于范围查询存在两个特殊的情况：
- 情况一：符合条件的数据在父节点甚至根节点
- 情况二：符合条件的数据在兄弟节点
对于这两种情况，可以使用下面的优化方案：
- 对于情况一
中间节点不再保存数据，而是全部放入叶子节点 - 对于情况二
不再通过遍历树寻找叶子节点，而是直接建立叶子节点之间的链接关系
这就是B+树，如图：
最后，量化一下B+树如何降低树的高度
假设每个节点大小是4KB，一个索引Key8字节，高度为3
- 每个节点可以存储4KB/8B=500个Key
- B树的特性。m叉树满足公式，m/2<= 每个节点Key数量（500） <=m，因此最多有1000个分叉
- 那么
| Key数量 | 占用空间 | |
|---|---|---|
| 层级1 | 500 | 4K |
| 层级2 | 500 * 1000 = 50W | 4M |
| 层级3 | 500 * 1000 * 1000 = 5亿 | 4G |
对于二叉树存储相同数量的索引，需要的高度约为lg(2.5亿)
索引分类
在InnoDB中，索引可以分为两大类
-
聚集索引
聚集索引一个特殊的索引，表数据和索引在一起存储。通常指的就是主键索引
因为这个特性，InnoDB表必须有聚集索引：- 如果定义了PK，那么PK就是主键索引
- 如果没有定义PK，那么第一个非空唯一索引就是聚集索引
- 如果没有PK和合适的唯一索引，那么InnoDB生成一个包含row-id的合成列作为聚集索引
row-id是一个6字节的属性，插入行时单调递增
辅助索引
与聚集索引不同，辅助索引可以有多个，并且只存储定义为索引的列和主键
因此：
- 对于主键查询，只需要遍历一次聚集索引树
- 对于其他索引列查询，需要遍历一次辅助索引树找到主键，再遍历一次聚集索引树
例如：
table t ( id pk ,name key ,sex )
对于 select * from t where name = 'a' 的情况，会先通过辅助索引定位检索到叶子，得到id=5，再通过聚集索引定位行记录
索引的优化
自适应哈希
为什么要有自适应哈希？
对于select * from t where name = 'm';
每次执行都需要遍历两次索引树，与哈希结构相比效率非常低。因此，InnoDB为频繁访问的数据建立哈希索引。
自适应哈希由InnoDB自动构建，以索引树为基础，选择任意长度的Key。当有访问时，由哈希直接得到数据
索引条件下推
ICP是索引作为筛选条件时的一种优化。筛选条件下推到存储引擎，只返回符合条件的数据，而不是所有数据。
例如：（zipcode、lastname、firstname）是联合索引
select * from user
where zipcode = 9527
and lastname like '%ing%'
and address like '%ian%'
- 不使用ICP
返回zipcode=9527的所有记录，然后再做其他条件的筛选 - 使用ICP
返回zipcode=9527的记录前，会检查是否满足lastname的条件，然后返回符合索引条件的数据
结论：不开启ICP会比开启ICP的情况，多返回不满足lastname条件的数据
覆盖索引
如果查询需要返回的列是定义的索引，那么可以通过索引直接返回数据，而不需要在从聚集索引中检索主键
索引的构建过程
排序索引构建是一种自底向上的算法，采用批量加载的方式代替传统的逐条插入方式。
索引的创建过程概括为三个阶段：
- 扫描聚集索引，生成索引条目并添加到排序缓冲区。当缓冲区已满时，排序索引并写入临时文件中。
- 对所有文件中的索引合并排序
- 将排序后的索引写到B-tree
B+树的构建过程
- 初始化阶段，树的每一层都有一个最右节点，作为下一个插入的节点
- 按顺序插入索引
- 插入时发现空间不足，那么在右侧创建新节点作为最有节点，插入的同时向父节点赋值
注意：索引构建会禁用重放日志，通过检查点机制强制脏页写磁盘
