MySQL数据库精研之旅第十四期：索引的 “潜规则”(上)
专栏：MySQL数据库成长记
个人主页：手握风云
目录
一、索引简介
1.1. 索引是什么
1.2. 为什么需要索引
二、索引应该选择哪种数据结构
2.1. Hash
2.2. 二叉搜索树
2.3. N叉树
2.4. B+树
三、MySQL中的页
3.1. 为什么要使用页
3.2. 页文件头和页文件尾
3.3. 页主体
3.4. 页目录
3.5. 数据页头
四、B+树在MySQL索引中的应用
4.1. 计算三层树高的B+树可以存放多少条记录
一、索引简介
1.1. 索引是什么
MySQL的索引是⼀种数据结构，它可以帮助数据库高效地查询、更新数据表中的数据。索引通过⼀定的规则排列数据表中的记录，使得对表的查询可以通过对索引的搜索来加快速度。不同的数据结构由于实现的算法不同，最终不同数据结构查询的时间复杂度和空间复杂度也不同。
MySQL索引类似于书籍的⽬录，通过指向数据行的位置，可以快速定位和访问表中的数据，比如汉语字典的目录（索引）页，我们可以按笔画、偏旁部首、拼音等排序的目录（索引）快速查找到需要的字。
- 笔画索引
当字典中要收录一个字的时候，不但要把字放在字典的合适位置，同时也会更新索引。有多少个索引，就需要更新多少个索引。字典收录字的时候按组织数据的规则把字安排在一个合适的位置，查询是按同样的规则进行检索。索引就是确定了组织数据的方式，不同的索引类型组织数据的方式不同。
1.2. 为什么需要索引
显而易见，使用索引的目的只有一个，就是提升数据检索的效率，在应用程序的运行过程中，查询操作的频率远远高于增删改的频率。MySQL最主要的功能就是存储数据，同时在保证安全的前提下尽量提升查询效率。
二、索引应该选择哪种数据结构
2.1. Hash
时间复杂度，查询速度非常快。MySQL并没有把Hash当成默认索引使用的数据结构，原因是Hash不支持范围查找。
2.2. 二叉搜索树
二叉搜索树中序遍历之后得到一个有序序列，最坏情况下退化为一棵单边数，时间复杂度为。由于数据保存在磁盘上，每一次通过父节点去找子节点，就会发生一次磁盘IO，磁盘I0是制约整个数据库甚至是应用程序性能的主要因素。
二叉树的度是2，当节点特别多的时候无法保证树的高度，当树越高发生磁盘IO的次数就越多，数据库的性能就越差。
2.3. N叉树
N叉树解决了树高的问题，从而减少磁盘IO的次数，并且支持范围查找。
2.4. B+树
B+树是一种经常用于数据库和文件系统等场合的平衡查找树，MySQL索引采用的数据结构。
- B+树与B树的区别：
- 叶子节点之间有一个相互连接的引用，可以通过一个叶子节点找到与它相邻的兄弟节点，因为MySQL在组织叶子节点时使用的是双向循环链表。
- 非叶子节点中的值都包含在叶子节点中。B+树的非叶子节点中只包含对子节点的引用，没有保存真正的数据，所有真实数据都保存在叶子节点中。
- 对于B+树而言，在相同树高的情况下，查找任一元素的时候复杂度都一样，性能均衡。
使用了B+树能够保持数据稳定有序，插入与修改有较稳定的时间复杂度。B+树的叶子节点可以按一KEY进行排序，保证了数据的有序性，从而可以支持范围查找。
三、MySQL中的页
3.1. 为什么要使用页
在.ibd 文件中最重要的结构体就是Page(页)，页是内存与磁盘交互的最小单元、默认大小为16KB每次内存与磁盘的交豆至少读取一页，所以在磁盘中每个页内部的地址都是连续的，之所以这样做，是因为在使用数所以一次从磁据的过程中，根据局部性原理，将来要使用的数据大概率与当前访问的数据在空间上是临近的盘中读取一页的数据放入内存中，当下次查询的数据还在这个页中时就可以从内存中直接读取，从而减少磁盘IO提高性能。
MySQL中的页是由操作系统中的4个页拼装在一起的。当我们执行一条SQL语句时，每次查询都要把16kb的页全部查出来，这是由于时间局部性和空间局部性。如果一个信息项被访问，那么近期内还可能会被访问，将来要用到的信息大概率与正在使用的信息在空间地址上是临近的｡
3.2. 页文件头和页文件尾
页文件头和页文件尾包含的信息，如下图所示：
这里我们只关注，上一页页号和下一页页号，通过这两个属性可以把页与页之间链接起来，形成一个双向链表。
3.3. 页主体
页主体部分是保存真实数据的主要区域，每当创建一个新页，都会自动分配两个行，一个是页内最小行Infimun ，另一个是页内最大行 Supremùn，这两个行并不存储任何真实信息，而是做为数据行链表的头和尾，第一个数据行有一个记录下一行的地址偏移量的区域 next_record 将页内所有数据行组成了一个单向链表，此时新页的结构如下所示：
最小行与最大行之间从哪开始到哪结束，中间不储存任何数据。
当向一个新页插入数据时，将 Infimun 连接第一个数据行，最后一行真实数据行连接 supremun ，)这样数据行就构建成了一个单向链表，更多的行数据插入后，会按照主键从小到大的顺序进行链接，如下图所示：
页中的数据行之间是单向链表的关系，并且是有序的。
3.4. 页目录
一个页有16kb，可以存很多数据行，在一个页中进行数据行的遍历也很费时，如何优化？
- 当按主键或索引查找某条数据时，最直接简单的方法就是从头行infimun开始，沿着链表顺序逐个比对查找，但一个页有16KB，通常会存在数百行数据，每次都要遍历数百行，无法满足高效查询，为了提高查询效率，InnoDB采用二分查找来解决查询效率问题；
- 具体实现方式是，在每一个页中加入一个叫做页目录Page Directory 的结构,将页内包括头行、尾行在内的所有行进行分组，约定头行单独为一组，其他每个组最多8条数据，同时把每个组最后一行在页中的地址，按主键从小到大的顺序记录在页目录中在，页目录中的每一个位置称为一个槽，每个槽都对应了一个分组，一旦分组中的数据行超过分组的上限8个时，就会分裂出一个新的分组；
- 后续在查询某行时，就可以通过二分查找，先找到对应的槽，然后在槽内最多8个数据行中进行遍历即可，从而大幅提高了查询效率，这时一个页的核心结构就完成了；
- 例如要查找主键为6的行，先比对槽中记录的主键值，定位到最后一个槽2，再从最后一个槽中的第一条记录遍历，第二条记录就是我们要查询的目标行｡
先在页中建立一个页目录，页中有很多的分组，当一个分组中的数据行大于8时，会自动拆分出另一个分组，同时在页目录中建立槽。槽和分组是一一对应的关系，槽里记录了当前分组最后一条记录的主键值。要想查询id = 7的记录，首先判断槽中的值，找到数据可以存在的分组再去分组中逐条的比对，最终找到目标行。
3.5. 数据页头
数据页头记录了当前页保存数据相关的信息，如下图所示：
四、B+树在MySQL索引中的应用
非叶子节点保存索引数据，叶子节点保存真实数据，以下B+树表示的是表中的主键索引：
数据行的排列方式是从左到右，从上到下去组织，插入一条数据时把数据行安排在合适的位置即可。
以查找id为5的记录，完整的检索过程如下：
- 首先判断B+树的根节点中的索引记录，此时5 < 7 ，应访问左孩子节点，找到索引页2；
- 在索引页2中判断id的大小，找到与5相等的记录，命中，加载对应的数据页；
以上的例子3次磁盘10就可以找到数据行，还可以把索引页缓存到内存，进一步提升效率。
4.1. 计算三层树高的B+树可以存放多少条记录
- 假设一个数据行大小为1kb，一页就可以存16条数据；
- 索引页一条数据大小：主键用bigint类型占8byte，下一页地址假设6byte，一共是14byte，一个索引页就可以保存1024*16/14 = 1170；一个索引页的度是1170，也就是可以有1170个子节点；
- 如果只有三层树高的情况，综合只保存索引的根节点和二级节点的索引页以及保存真实数据的数据页，那么一共可以保存1170 * 1170 * 16=21,902,400条记录，也就是说在两千多万条数据的表中，可以通过三次IO就完成数据的检索；