MySQL InooDB 索引实现

1 索引定义

维基百科对数据库索引的定义:
数据库索引是数据库管理系统（DBMS）中的一个排序数据结构, 以协助快速查询和更新数据库表中的数据。

MongoDB对索引的定义:
索引是一种特殊的数据结构, 以有序和便于遍历的形式存储数据集合中特定字段或一组字段的值。
索引条目的排序支持有效的相等匹配和基于范围的查询操作。

理解:
数据库表中的数据以文件的形式存放在磁盘上, 每一行数据都有其磁盘地址。 如果没有索引, 要从表中检索一条数据, 只能依次遍历整张表的数据, 直到找到这条数据。
而索引是一种特殊的专门用于快速检索的数据结构。有了索引后, 只需在索引中检索这条数据, 找到数据存放在磁盘的地址后, 就可以找到数据了。

2 索引的实现原理

假设现在有 1 到 9 总共 9 个数字, 在不做任何处理的情况下, 需要从中找到数字 9, 有什么好的方式呢？

这时能做的也就只能一个个遍历了, 但是我们知道逐个遍历的随机性比较大, 同时性能会随着数据量的增加逐渐下降。

那么有没有好的方式呢？有。

1. 我们可以将所有的数字先按照从小到大的顺序进行排序
2. 每次查找时都从已有的数据的中间开始, 用中间的数字和要查找的数字进行比较。如果要查找的数字比中间大, 把左侧的数据都放弃; 如果要查找的数字比中间小, 把右侧的数据放弃。

像上面的查找方式实际上就是利用了二分查找的思想。
在一个已经排过序的数据中, 进行二分查找是一个很快的过程, 因为每次查找都能过滤掉一半的数据。

而数据库的索引就是借助二分查找思想实现的。

3 索引实现的数据结构

索引就是通过二分查找的思想设计的, 那么落实到具体的实现就是需要确定一个比较适合二分查找思想的数据结构。

不同的数据结构有不同的特性, 比如:

1. 数组的查找效率是非常快, 但是在数组中间的新增删除会很慢, 会涉及到后面数据的移动
2. 链表的变更很快, 但是查询很慢, 每次查询都需要从头往后逐个遍历

所以选择一个合适的数据结构, 对索引的性能很重要。
那么有什么数据结构符合:

1. 支持变更 (二分查找要求数据有序, 所以会涉及到数据的调整)
2. 查询效率不错
3. 适合二分查找的思想

3.1 二叉查找树 (BST, Binary Search Tree)

通过二分查找这个条件基本可以过滤掉很多条件, 而在常用的数据结构中, 最索引符合条件的数据结构能想到的就是树了。

因为索引的数据是有序的, 所以还是需要有序的树, 也就是**二叉查找树 (BST, Binary Search Tree)**。

二叉查找树 (二叉搜索树, 二叉排序树) 的特点

1. 若任意节点的左子树不空, 则左子树上所有结点的值均小于它的根结点的值
2. 若任意节点的右子树不空, 则右子树上所有结点的值均大于它的根结点的值
3. 任意节点的左、右子树也分别为二叉查找
4. ……

二叉查找数可以实现快速查找, 又能实现快速插入。
但是二叉树有一个问题: 它的查找耗时和这棵树的深度有关, 在最坏的情况下, 时间复杂度会退化为 O(n)。

假设现在向二叉查找树中插入 2, 3, 4, 5, 6。
这个时候将会得到如下的一棵二叉查找树:

它会变成变成链表 (也叫做 “斜树”), 这种情况下不能达到加快查询速度的目的, 和顺序查找效率差不多。
造成树倾斜的原因: 左右子树深度差太大, 导致不平衡。

3.2 平衡二叉树 (AVL, Balanced Binary Search Tree)

既然二叉树会 “失衡”, 那么能让他 “不失衡” 吗?
有, 这时就是平衡二叉树了, 平衡二叉树要求左右子树深度差绝对值不能超过 1, 向树中插入数据时, 一旦树出现不平衡, 需要通过左旋或右旋进行调整。

平衡的解决了树失衡的情况, 那么平衡二叉树作为索引实现是最合适吗?

首先作为索引应该存储什么内容

1. 索引的键值。比如在表中的 id 上面创建了一个索引, 在用 where id = 1 的条件查询的时候, 需要能在索引里面找到 id 对应的键值, 也就是 1
2. 索引对应的数据, 因为索引的作用就是去查找数据, 找到了索引, 也就是找到了数据 (这里也可以是存放的是数据的磁盘地址, 通过这个地址, 再到磁盘读取)
3. 必须持有左子节点和右子节点的引用, 这样才能找到下一个节点。比如大于 26 的时候, 走右边, 到下一个树的节点, 继续判断

索引本身就是数据, 所以也是需要持久化的
当数据库宕机等原因, 需要重启后, 我们为表建立的索引是必须要可以继续使用的, 为了达到这个效果, 那么我们就需要将数据存放到磁盘中。

基于上面 2 点的考虑, 现在我们有 1 棵平衡二叉树如下

需要查询索引 = 5 的表记录的磁盘位置, 需要经历如下操作

1. 从磁盘中读取根节点 4
2. 5 比根节点的 4 大, 从磁盘中读取右节点 6
3. 5 比节点 6 小, 从磁盘中读取左节点 5
4. 5 等于节点 5, 从当前节点获取磁盘地址, 获取到数据

从上面的过程中, 每一次节点都需要和磁盘进行一次 IO 操作。 而在系统操作中, 磁盘 IO 是一个很耗时的行为。
所以 InnoDB 在进行磁盘 IO 操作时, 不是按需读取, 而是按照页的维度 (一页默认等于 16k) 进行读取, 也就是每次从磁盘读取数据都是 16k 的数据, 通过这种多读取的方式, 减少 IO 次数。

而平衡二叉树的节点的存储的内容为: 索引值 + 索引对应的数据(数据的磁盘地址) + 引用, 例如整形的索引的, 可能只用了十几个或者几十个字节, 即使加上数据, 它也很少能达到 16K 的容量,
所以访问一个树节点, 进行一次 IO 的时候, 浪费了大量的空间。

也许你会想, 一次 IO, 可以读取 16k 数据, 那么我一次性读取 16k 的树节点不就行了吗?
能实现这个的前提是 16k 的节点在磁盘中都是连续的, 但是树的节点间是通过引用, 也就是指针关联的, 内存不一定的连续的, 所以每次 16k 数据的读取, 不一定都是有用的数据。

解决方案: 让树上每个节点存储更多的数据。
通过让节点的关键字 (索引值) 的数量增加, 那么节点的数据就增加了。

关键字 (索引值) 增加, 会引起节点内指针数量的怎几个, 也就是产生了更多的分叉 (也叫做 “路数”)。
分叉数越多, 数的深度会减少, 这个时候树不再是二叉, 而是多叉, 或者叫做多路。

3.3 多路平衡树 (B Tree, Balanced Tree)

二叉树就是树中每个节点最多就有 2 个子节点。
而 B 树是多路树, 多路就是多叉, 也就是树中的每个节点都是多个字节点。

如图, 上面 B 树的根节点就下面有 3 个子节点, 而 2 节点的下面有 2 个节点。
所以 B 树的节点最多可以有多少个节点呢？

这个涉及到 B 树的一个概念: 度 (Degree), 最大多少度就是表示了 B 树中的节点最多可以为多少路, 也就是多少分叉。
假设一棵树的最大路数 (Max Degree) 是 3, 依次插入 1, 2, 3。 在插入 3 的时候, 第一个磁盘块出现了 3 个关键字, 有 4 个指针, 即变成了 4 路。
这个时候就需要进行分裂, 把中间的数据 2 提上去, 把 1, 3 变成 2 的子节点 (同样的进行了删除节点, 可能需要进行合并操作)。

跟 AVL 树一样, B 树的节点存储索引值 + 索引对应的数据(数据的磁盘地址) + 节点引用。

同时 B 树的分叉数 (路数) 永远比索引值多 1, 比如有节点中有 2 个索引值, 那么会有 3 个指向下游的节点的指针, 大体的结构如下:

这样, 设定 B 树每个节点的大小为 16k (充分利用每次 IO 16k 的特性, 这样每次 IO 就是一个节点的数据), 利用 B 树多路的特点, 将表中多个行数据组织在同一个节点中,
这样既可以利用索引的特性, 又可以减少 IO 次数, 提高查询效率。

一个节点为 16k, 每行记录和索引的大小都是在建表时确定的, 而指针的大小跟操作系统的位数有关, 64 位系统, 一个指针占 8 个字节, 32 位系统, 一个指针占 4 个字节。
这样一个节点可以存储的数据 = 16k - 1 个节点引用 (B 树的路数比索引值多 1) / (索引值 + 索引对应的数据 + 节点引用) 个索引值。

但是实际上, InnoDB 还是没有选中 B Tree 作为索引。使用 B Tree 作为索引的实现时:

1. 非叶子节点存储的是索引值 + 数据, 搜索有可能在非叶子节点结束, 也有可能要到叶子节点才结束, 越靠近根节点查询效率越快, 而离根节点越远, 效率越慢, 查询时间很不稳定
2. 每个节点的大小固定为一页 (默认 16k) 的大小, 有限的容量既要存索引值, 还有存储数据。如果数据很多, 那么 1 个节点能存储的索引数会少很多, 那么可能会导致这个树很高, 导致 I/O 的次数提高

3.4 加强版多路平衡查找树 (B+ Tree)

InnoDB 实现的 B+ Tree 和 B Tree 区别不大, 只是做了以下 2 个调整

1. 它的索引值的数量和路数相等, 节点间的索引取值是一个左闭右开的区间 [x, y)
2. B+ Tree 的根节点和非叶子节点中都不会存储数据, 只有叶子节点才存储数据。搜索到索引值不会直接返回, 而是继续走到最后一层的叶子节点, 这里才会找到真正的行数据, 所以每条记录查询的时间基本都是一样的
3. B+ Tree 的每个叶子节点增加了一个指向相邻叶子节点的指针, 它的最后一个数据指向下一个叶子节点的第一个数据, 形成了一个有序的链表

B+ Tree 比 B Tree 更适合作为索引的实现

1. B+ Tree 是 B Tree 的变种, B Tree 能解决的问题, 它也能解决
2. 扫库, 扫表能力更强 (如果要对表进行全表扫描, 只需要遍历叶子节点就可以, 不需要遍历整棵 B+ Tree, 因为叶子节点有指向下一个叶子节点的指针, 所有数据都是串联起来的)
3. B+ Tree 的索引过滤能力相对于 B Tree 更强, 非叶子节点不保存数据区, 所以一个节点保存更多的索引值, 一次磁盘加载的索引值更多
4. 排序能力更强, 因为叶子节点有下一个数据区的指针, 数据形成了链表
5. 效率更加稳定, B+ Tree 永远都是在叶子节点拿到数据, 所以 IO 次数稳定

3.5 为什么不使用红黑树来实现索引

红黑树也是二叉查找树, 但是不是严格平衡的, 其本身有 5 个约束

1. 根节点必须是黑色的
2. 节点分为红色或者黑色
3. 叶子节点都是黑色的 NULL 节点
4. 红色节点的两个子节点都是黑色 (不允许两个相邻的红色节点)
5. 从任意节点出发, 到其每个叶子节点的路径中包含相同数量的黑色节点

基于上面的约束, 可以推导出: 从根节点到叶子节点的最长路径 (红黑相间的路径) 不大于最短路径(全部是黑色节点) 的 2 倍。

不使用红黑树的原因

1. 只有两路
2. 不够平衡

3.6 InnoDB 索引的另一种实现

在 InnoDB 中还有一种 Hash 实现索引的方式。
Hash 以 KV 的形式检索数据, 会根据索引字段生成哈希码和指针, 指针指向数据。

Hash 索引的特点

1. 它的时间复杂度是 O(1), 查询速度比较快。因为哈希索引里面的数据不是按顺序存储的, 所以不能用于排序
2. 在查询数据的时候要根据键值计算哈希码, 所以它只能支持等值查询 (= IN) , 不支持范围查询 (> < >= <= between and)
3. 如果字段重复值很多的时候, 会出现大量的哈希冲突 (采用拉链法解决), 效率会降低

InnoDB 只支持显式创建 B+Tree 索引, 对于一些热点数据页, InnoDB 会自动建立自适应 Hash 索引, 也就是在 B+Tree 索引基础上建立 Hash 索引, 这个过程对于客户端是不可控制的, 隐式的。
这个隐式的建立过程就是 Adaptive Hash Index 自适应哈希索引。这个行为也是通过一个开关控制的 **show variables like ‘innodb_adaptive_hash_index’;**。

4 B+ Tree 的落地实现

MySQL 的数据都是以文件的形式存放在磁盘中的, 在 MySQL 中有这么一个参数 show VARIABLES LIKE ‘datadir’;, 可以找到这个数据目录的地址。
在这个目录下, 每个数据库都有自己的文件夹, 数据库下的表同样的在对应的数据库文件夹下有自己的文件

1. InnoDB 的表有 2 个文件, 表名.frm 和 表名.ibd
2. MyISAM 的表有 3 个文件, 表名.frm, 表名.MYD 和 表名.MYI

其中 .frm 是 MySQL 里面表结构定义的文件, 每个表都会生成的。

4.1 MyISAM

在 MyISAM 中

1. .MYD 文件, D 代表了 Data, 是 MyISAM 的数据文件, 存放数据记录, 也就是表中的所有数据
2. .MYI 文件, I 代表了 Index, 是 MyISAM 的索引文件, 存放的是表中的索引数据。

MyISAM 的 B+ Tree 里面, 叶子节点存放的是数据文件对应的磁盘地址。索引从索引文件 .MYI 中找到键值后, 会再到数据文件 .MYD 中获取相应的数据记录。

这里分析的是主键索引, 如果是非主键索引, 有什么不一样的吗?

在 MyISAM 里面, 非主键索引也在 .MYI 文件里面。
非主键索引跟主键索引存储和检索数据的方式没有任何区别, 一样是在索引文件里面找到磁盘地址, 然后到数据文件里面获取数据。

4.2 InnoDB

在 InnoDB 中只有一个 .ibd 文件。在 InnoDB 中以主键为索引组织数据的存储, 索引文件和数据文件都在同一个 .ibd 文件中。
在 InnoDB 的主键索引的叶子节点上, 直接存储了表中的数据

在 InnoDB 中, 这种组织数据的方式叫做 (聚集) 索引组织表 (clustered index organize table), 即索引和数据组织在一起, 也叫做聚集索引。
同理, MyISAM 那种将索引和数据分开的方式叫做非聚集索引。

在 InnoDB 中, 主键索引是聚集索引, 非主键索引都是非聚集索引。

非主键索引叶子节点存储的是非主键索引索引和对应记录的主键值。
如果使用非主键索引查询, 会先在非主键索引树中找到主键值, 再根据主键值在主键索引树中查询, 最终获取到数据。

4.3 问题的思考

InnoDB 为什么不直接在非主键索引里面存储主键的磁盘地址

B+ Tree 为了维持平衡, 节点的数据会进行调整, 从而有概率引起节点分裂和合并的操作, 这些操作会改变数据的地址。
索引在非主键索引如果存储的是地址, 在调整完主键索引树后, 还需要修改所有的非主键索引的地址, 但是如果存放的是主键的 id, 则不需要关心辅助索引的变化。

一张表没有主键时怎么办
如果显示地定义了主键 (primary key), 那么 InnoDB 会选择这个主键作为聚集索引。
如果没有显示定义主键, 则 InnoDB 会选择第一个不包含有 Null 值的唯一索引作为主键索引
如果没有这样的唯一索引, 则 InnoDB 会选择内置 6 字节的 ROWID 作为隐藏的聚集索引, 它会随着行记录的写入而主键递增。

select _rowId name from 表名;

为什么主键索引的选择都是建议选择自增的列
在上面分析中, 索引有一个特点就是有序, 如果选择自增的列作为主键索引, 那么每次新增的数据都是在原有数据后面的追加

1. 插入性能优化, 因为每次插入都是在原有数据后面追加, 不会造成数据的移动, 所以插入性能很好
2. 顺序读取优化, 索引的数据最终都是需要持久化到磁盘的, 如果索引递增, 那么就可以保证索引的数据都是顺序写入磁盘的, 这样就可以大大提高顺序读取的性能
3. 减少索引碎片, 当使用非递增主键时, 删除或新增操作可能导致数据页的移动或分裂, 从而引起索引碎片。递增主键的插入和删除通常只会在索引的末尾进行, 减少了这种碎片化的可能性

5 InnoDb 中使用索引的一些特性

5.1 离散度

建立索引, 不是越多越好, 也不是随便哪一列都适合建立索引。

一般选择作为索引的列, 可以从查询频率和离散度(数据的重复率), 两个角度来考虑。

列的离散度的计算公式:
count(distinct(列名)) / count(1), 列的去重数据和所有数据行的比例。数据行数相同的情况下, 分子越大, 列的离散度就越高。

简单来说: 列的重复值越多, 离散度就越低, 重复值越少, 离散度就越高。
一个简单的例子: 在用户表里面, 给性别列加索引和给姓名加索引, 2 者的收益不同, 前者的离散度较低, 后者较高。

注: 可以通过 show indexes from 表名;, 查看表的索引情况。
查询结果中的 Cardinality, 代表基数, 代表了预估的不重复的值的数量。索引的基数和表总行数越接近, 列的离散度就越高。

散列度的判断也不一定是完全考量的, 一些特殊的场景, 也可以考虑建立索引。

举个例子:
假设有一种信息发送表, 表里面每天都会增加大量数据, 表中有 1 列表示当前消息的状态, 已发送, 待发送 2 个状态, 如果直接考虑离散度, 那么这个列的离散度就很低, 不适合建立索引。

业务场景, 定时器定时的从表中查询出待发送的消息, 进行发送, 每次发送成功后, 就将记录的状态更新为已发送。
那么这时候给状态加上索引, 因为表中大部分的情况都是已发送的, 未发送的只占里面总量的很少很少, 通过这个索引可以筛选掉一大部分的以发送数据。

5.2 联合索引最左原则

联合索引是指在多个列上建立索引。

联合索引在 B+ Tree 中是复合的数据结构, 他按照从左到右的顺序来建立索引树。
比如: 当前有 name 和 phone 的复合索引, 在树中, name 是有序的, phone 是无序的。只有当 name 相等的情况下, phone 才有序。

当查询的时候使用的条件为 where name= 'A' and phoe = '123';, B+ Tree 会优先比较 name 来确定下一步应该搜索的方向, 往左还是往右。
如果 name 相同的情况, 再比较 phone。 如果查询条件没有 name, 就不知道第一步应该查哪个节点, 因为建立搜索树的时候 name 是第一个比较因子, 所以用不到索引。

5.3 覆盖索引

通过索引查询数据时, 不管是单例索引还是复合索引, 如果 select 的数据列值用从索引中就能取得, 不必从数据区中读取, 这时候使用的索引就叫做覆盖索引, 这样就避免了回表。

比如现在我有 1 张表 t1, 表中有 id, name, phone, sex 三个字段, 有一个组合索引 name + phone + sex,

select sex from t1 where name = 'A' and phone = '123';

这时查询的条件和结果都可以在索引树中找到, 不需要回表, 这时候就是覆盖索引。

回表的过程

1. 非主键索引, 先通过索引找到主键索引的键值 (主键索引跳过此步骤)
2. 通过主键值到主键索引中找到对应的行
3. 从行中找到查询列中其他不在索引里面的字段的值 (也就是重新回到表数据中)

需要回到数据区, 也就是表中的情况, 就是回表

5.4 索引条件下退 (ICP)

ICP 功能默认是开启的, 我们先尝试关闭 ICP 功能:

-- 关闭 ICP
set optimizer_switch='index_condition_pushdown=off';

-- 查看参数
show variables like 'opimizer_switch';

现在有一张雇员表 employees, 里面有 2 个非空的 varchar 的字段 first_name 和 last_name, 在表上建立了一个复合索引 (last_name, first_name)。
现在要查询出所有姓是 wang (last_name) 和名字中最后一个字为 zi 的员工

select * from employees where last_name = 'wang' and first_name like '%zi';

这条 SQL 有两种执行方式:

(1) 根据联合索引查出所有姓 wang 的二级索引数据, 然后回表, 到主键索引上查询全部符合条件的数据 (假设现在有 3 条数据) 。然后返回给 MySQL Server 层, 在 Server 层过滤出名字以 zi 结尾的员工。
(2) 根据联合索引查出所有姓 wang 的二级索引数据, 然后从二级索引中筛选出 first_name 以 zi 结果的索引, 然后在回表, 到主键索引上查询全部符合条件的数据 (假设现在有 1 条数据), 返回给 Server 层。

注: 在 MySQL 的设计中, 索引的比较是在存储引擎进行的, 数据记录的比较, 是在 Server 层进行的。

很明显, 第二种方式到主键索引上查询的数据更少。而且当 first_name 的条件不能用于索引过滤时, Server 层不会把 first_name 的条件传递给存储引擎, 所以不会读取到两条没有必要的记录。

如果这时候满足 last_name = ‘wang’ 的记录有 10000 条, 就有 9999 条是没必要读取的记录。

通过 explain 分析上面的 SQL, 可以看到结果里面的 Extra 列里面的结果为 Using where。
Using where 代表从存储引擎取回的数据不全部满足条件, 需要在 Server 层过滤。
先用 last_name 条件进行索引范围扫描, 读取数据表记录, 然后进行比较, 检查是否符合 first_name like ‘%zi’ 的条件, 此时 3 条中只有 1 条符合条件。

开启 ICP 功能

set optimizer_switch='index_condition_pushdown=on';

此时再通过 explain 分析上面的 SQL, 可以看到结果里面的 Extra 列里面的结果为 Using index condition。
把 first_name like ‘%zi’ 下推给存储引擎后, 只会从数据库表读取所需的 1 条记录。

索引条件下推 (Index Condition Pushdown), 5.6 以后完善的功能。只适用于二级索引。
ICP 的目标是减少访问表的完整行的读数量从而减少 I/O 操作。

6 索引带来的问题

使用索引可以带来查询效率的提升, 但是其本身也会引入其他的问题。

性能开销
在往表中新增/删除记录时, InnoDB 除了需要保证数据的正确落库, 还需要同时还需要维护对应的索引树, 这个过程有可能会导致索引树的调整, 页合并, 页分裂等情况, 都是对数据库性能的开销

占用存储空间
索引最终是需要持久到磁盘中的, 而这一份都是需要磁盘空间的, 而且这部分空间是非数据的开销, 只是单纯是辅助查询的空间消耗

过多或不正确的索引, 可能查询性能下降
过多的索引, 离散度不高的索引等, 可能会导致数据库选择不合适的索引, 做出错误的查询执行计划, 进而影响到查询的效率

7 索引的使用上的建议

索引的使用

1. 常用在 where 条件 / order 排序 / join 的 on 字段上建索引
2. 索引的数量不要太多 –> 浪费空间, 更新变慢
3. 区分度低的字段, 例如性别, 不用要建索引 –> 离散度太低, 导致扫描行数过多
4. 频繁更新的值, 不要作为主键或者索引 –> 可能会导致页分裂
5. 组合索引把散列度高的 (区分度高) 的值放在前面
6. 创建复合索引, 而不是修改单列索引
7. 无序的值 (例如身份证, UUID) 尽量不要作为索引
8. 当字段值比较长的时候, 可以考虑前缀索引, 截取字段的前面一部分内容建立索引, 至于截取多少, 可以通过散列值判断

索引失效

1. 在索引列上使用函数, 表达式, 计算
2. 字符串不加引号, 出现隐式转换, varchar 和 char 字段等于查询等场景
3. like 条件中前面带 %
4. 不等于查询, not like, not in, !=