MySQL innoDB索引底层原理详解

250次阅读

共计 3465 个字符，预计需要花费 9 分钟才能阅读完成。

摘要
本文介绍 MySQL 的 InnoDB 索引相对底层原理相关知识，涉及到 B +Tree 索引和 Hash 索引，但本文主要介绍 B +Tree 索引，其中包括聚簇索引和非聚簇索引，InnoDB 数据页结构详解，B+Tree 索引的使用以及优化，同时还有 B +Tree 索引的查询流程简介。
此文是我对学习 InnoDB 索引的一个总结，内容主要参考 MySQL 技术内幕 InnoDB 存储引擎一书，及网上一些博客（参考文献会给出）
一、先从 B +Tree 入手
B+ 树的特性
因作者文笔有限，B+ 树的定义如果在这里重复列出的话，应该只会让大家更困惑，同时相信任何一本数据结构书中都能找到其复杂的定义。但是为了便于读者理解接下来的内容，下面只是简单的介绍一下 B + 树的几个本文中会用到的特性。
B+ 树是为磁盘或其他直接存取辅助设备而设计的一种平衡查找树（如果不知道平衡查找树，请自行 google），在 B + 树中，所有记录节点都是按键值的大小顺序存放在同一层的叶节点中，各叶节点指针进行连接。
下图是在网上找的一张 B + 树示意图

MySQL innoDB 索引底层原理详解

二、InnoDB 数据页结构
1. 页介绍
页是 InnoDB 存储引擎管理数据库的最小磁盘单位。页类型为 B -Tree node 的页，存放的即是表中行的实际数据了。
InnoDB 中的页大小为 16KB，且不可以更改
InnoDB 可以将一条记录中的某些数据存储在真正的数据页面之外，即作为行溢出数据。MySQL 的 varchar 数据类型可以存放 65535 个字节，但实际只能存储 65532 个。同时 InnoDB 是 B + 树结构的，因此每个页中至少应该有两个行记录，否则失去了 B + 树的意义，变成了链表，所以一行记录最大长度的阈值是 8098，如果大于这个值就会将其存到溢出行中。

2.InnoDB 数据页组成部分
File Header(文件头)
Page Header(页头)
Infimun + Supremum Records
User Records(用户记录，即行记录)
Free Space(空闲空间)
Page Directory(页目录)
File Trailer(文件结尾信息)
这也是我摘抄的书上的内容，下面我只介绍一下会帮助理解底层原理的部分。

1. 在 File header 中，FIL+PAGE_PREV,FIL_PAGE_NEXT 两个表示当前页的上一页和下一页，由此可以看出叶子节点是双向链表串起来的。如下图

MySQL innoDB 索引底层原理详解

2.Infimum 和 Supremum 记录
在 InnoDB 存储引擎中，每个数据页中有两个虚拟的行记录，用来限定记录的边界。Infimum 记录是比该页中任何主键值都要小的值，Supremum 指比任何可能大的值还要大的值。这两个值在页创建时被建立，并且在任何情况下不会被删除。

MySQL innoDB 索引底层原理详解

由上图可以看出，行记录是记录在页中的，同时是在页内行记录之间也是双向链表链接的 (在网上有看到说是单链表的)
3.Page Directory
页目录中存放了记录的相对位置，有些时候这些记录指针称为 Slots（槽）或者目录槽，与其他数据库不同的是，InnoDB 并不是每个记录拥有一个槽，InnoDB 中的槽是一个稀疏目录，即一个槽中可能属于多个记录，最少属于 4 个目录，最多属于 8 个目录。槽中记录按照键顺序存放，这样可以利用二叉查找迅速找到记录的指针。但是由于 InnoDB 中的 Slots 是稀疏目录，二叉查找的结果只是一个粗略的结果，所以 InnoDB 必须通过 recorder header 中的 next_record 来继续查找相关记录。同时 slots 很好的解释了 recorder header 中的 n_owned 值的含义，即还有多少记录需要查找，因为这些记录并不包括在 slots 中。

三、查询 B + 树索引的流程
首先通过 B + 树索引找到叶节点，再找到对应的数据页，然后将数据页加载到内存中，通过二分查找 Page Directory 中的槽，查找出一个粗略的目录，然后根据槽的指针指向链表中的行记录，之后在链表中依次查找。
需要注意的地方是，B+ 树索引不能找到具体的一条记录，而是只能找到对应的页。把页从磁盘装入到内存中，再通过 Page Directory 进行二分查找，同时此二分查找也可能找不到具体的行记录（有可能会找到），只是能找到一个接近的链表中的点，再从此点开始遍历链表进行查找。

四、聚簇索引与非聚簇索引
B+ 树索引可以分为聚集索引和辅助索引，他们不同点是，聚集索引的行数据和主键 B + 树存储在一起，辅助索引只存储辅助键和主键。
1. 聚集索引
聚集索引是按每张表的主键构造的一颗 B + 树，并且叶节点中存放着整张表的行记录数据，因此也让聚集索引的节点成为数据页，这个特性决定了索引组织表中数据也是索引的一部分。由于实际的数据页只能按照一颗 B + 树进行排序，所以每张表只能拥有一个聚集索引。查询优化器非常倾向于采用聚集索引，因为其直接存储行数据，所以主键的排序查询和范围查找速度非常快。
不是物理上的连续，而是逻辑上的，不过在刚开始时数据是顺序插入的所以是物理上的连续，随着数据增删，物理上不再连续。
2. 辅助索引
辅助索引页级别不包含行的全部数据。叶节点除了包含键值以外，每个叶级别中的索引行中还包含了一个书签，该书签用来告诉 InnoDB 哪里可以找到与索引相对应的行数据。其中存的就是聚集索引的键。
辅助索引的存在并不影响数据在聚集索引的结构组织。InnoDB 会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后通过主键索引找到一个完整的行记录。当然如果只是需要辅助索引的值和主键索引的值，那么只需要查找辅助索引就可以查询出索要的数据，就不用再去查主键索引了。

五、索引的管理
索引在创建或者删除时，MySQL 会先创建一个新的临时表，然后把数据导入临时表，删除原表，再把临时表更名为原表名称。
但是在 InnoDB Plugin 版本开始，支持快速创建索引。其原理是先在 InnoDB 上加一个 s 锁，在创建过程中不需要建表，所以速度会很快。创建过程中由于加了 s 锁，所以只能进行读操作，不能写操作。
show index form table; 是查看表中索引的信息的。
Table: 索引所在的表名
Non_unique: 非唯一的索引，可以看到 primary key 是 0，因为必须是唯一的
Key_name: 索引名称
Seq_in_index: 索引中该列的位置
Column_name: 索引的列
Collation: 列以什么方式存储在索引中。可以是 A 或者 NULL，B+ 树索引总是 A，即排序的。
Cardinality：表示索引中唯一值的数目的估计值。如果非常小，那么需要考虑是否还需要建立这个索引了。优化器也会根据这个值来判断是否使用这个索引。
Sub_part: 是否是列的部分被索引。100 表示只索引列的前 100 个字符。
Packed: 关键字如果被压缩。
Null：是否索引的列含有 NULL 值。
Index_type: 索引的类型。InnoDB 只支持 B + 树索引，所以显示 BTREE

六、Hash 索引
InnoDB 中自适应哈希索引使用的是散列表的数据结构，并且 DBA 无法干预。
其实这一部分的原理，非常简单，在此就不做过多介绍了

总结
至此本文就结束了，本文只是从原理上进行了简单的介绍，由于笔者水平有限，且了解不深入，本文多处借鉴书本知识。外加了一些自己的见解，如有错误之处，还请不吝赐教。