MySQL B+树索引结构

看了很多关于MySQL B+树索引的文档，但一直有些问题没搞明白：

• B+树索引在磁盘上是怎么存储的？
• 内节点、叶子节点的物理结构又是什么样子的？

直到看到一份资料《MySQL 是怎样运行的：从根儿上理解 MySQL》，基本解决了我的现有疑惑。但好的资料就是看着看着又能让你思考更多问题，有新的疑惑，再去解决新的疑惑让自己不断提升。下面我将把从这个资料学习到的B+树索引结构的知识按自己的逻辑整理后分享给大家，以此角度来给大家安利这份学习资料，大纲如下：

• B+树索引结构的推导过程

  1. 数据行结构--单向链表；
  2. 数据页结构--通过页目录使用二分法快速找到目标行；
  3. 目录项--多个数据页时如何定位到目标行所在的数据页；
  4. B+树索引--目录项太多，大目录嵌套小目录，就形成了B+树

• 聚簇索引

  1. 特点；
  2. 主键的选择以及原因。

• 二级索引结构和特点

• MyISAM 索引结构和特点

B+树索引结构的推导过程

1. 数据行结构

一切要从数据行结构说起，这里特指 InnoDB 行结构： 看起来很复杂，不过此文章只需要关注数据行结构的记录头信息中有个 next_record 结构，它表示从当前记录的真实数据到下一条记录的真实数据的地址偏移量，所以在一个数据页里行与行根据这个设计可以组成一个有序的单向链表（按照主键排序）： InnoDB行--单向链表

2. 数据页结构

一个数据页默认16KB，可以存放很多行数据，那如何在一个数据页中快速找到一行数据呢？在数据页中有个叫“页目录”的结构：

• 把数据页里的数据行按规则分成 n 个组；
• 每个组中主键最大的那一行数据的地址偏移量存到“页目录”的“槽”中。

这样就可以根据主键值使用二分法进行快速查找到目标行所在位置： 多个数据页之间，根据页结构中的 File Header 中的 FIL_PAGE_PREV、FIL_PAGE_NEXT 记录上一个页号和下一个页号，把许许多多页建立一个双向链表串联起来：

3. 目录项

如果一张表的数据存在很多个数据页里，如何找到目标行数据在哪一个数据页中呢？

简单的实现方法是给这些数据页做一个目录：取出每个数据页中最小那行数据的主键值，和页号（page_no），组成一行数据，也称为目录项，记录到目录中。这样也可以通过二分法来查找一个指定的主键值在哪个数据页上：

但是对目录使用二分法查找的前提是：这个目录的内容（目录项）是连续存放在某个地方的。但实际上 IoonDB 的存储的最小单位是页，默认只有 16K，所以这个方法在实现上不可行。

由于目录中的内容“目录项”跟真实的用户记录类似：

• 每个数据页中最小的主键值；
• 页号，也叫 page_no。

所以可以用数据行结构、页结构来存储目录项，为了和真实的用户记录做区分，在数据行结构的记录头信息中把目录项纪录的 record_type 属性设置为“1”，而普通的用户记录则为“0”。所以目录项放到数据页中就被设计成这样了：

4. B+树索引

如上图，如果一张表的行数很多，势必就会有很多数据页，那么就可能出现一个页存不下所有“目录项纪录”的情况，所以可能会有很多个“目录项数据页”，那又怎么快速知道应该在哪个“目录项数据页”上查找目标数据在哪个“数据页”上呢？

也很简单，再为“目录项数据页”生成一个更高一级的目录即可，即大目录嵌套小目录，直到最顶级的那个目录只需要一个“页”就能存下第二级目录的所有目录项：

这就是 B+树索引结构：

• 实际用户记录其实都存放在B+树的最底层的节点上，这些节点也被称为叶子节点或叶节点；
• 其余用来存放目录项的节点称为非叶子节点或者内节点；
• 其中 B+树最上边的那个节点也称为根节点。

5. 时间复杂度

索引树的高度决定了查找数据的速度，而索引树的高度 h 取决于：

• 每个叶子节点（即数据页）中能存放多少条“用户记录”，m；
• 每个内节点或非叶子节点能存放多少条“目录项记录”，n；
• 表的总行数 X。

m*n^(h-1)=X ，则 ℎ−1=log𝑛𝑋/𝑚 ，这就是常说的B+树索引查找的时间复杂度为O(log n) 的由来。（一个页面最少存储2条记录的设计，就是为了让索引的效果更好）

聚簇索引

1. 特点

其实聚簇索引的特点属于老生常谈了，但按例还是得介绍一下。
在 InnoDB 中聚簇索引（主键）就是数据的存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的索引即数据，数据即索引。

• 使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：

  1. 页内的记录是按照主键的大小顺序排成一个单向链表；
  2. 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表；
  3. 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。

• B+树的叶子节点存储的是完整的用户记录。
  所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。

2. 主键的选择

聚簇索引是底层的说法，而主键是运维层面的说法（因为有语法 primary key(id)），通常主键的选择是：id int auto_increment，为什么呢？

• int 或者 bigint 类型占用字节少节省空间，因为二级索引的叶子节点、非叶子节点上都要保存主键键值；
• 索引是有序的，auto_increment 自增属性会保证按顺序插入数据，不会造成数据页的分裂（因为数据页中数据行是按照主键的顺序组成的单向链表，数据一旦变化，是需要维护这种顺序的），减少性能开销；
• id 字段没有业务含义，本身不会被更新，所以记录基本不会挪动在数据页中的位置。

二级索引

二级索引是一个与聚簇索引独立的 B+ 树，叶子节点不再保存完整的用户记录，只保存索引列键值和主键键值，二级索引中无论是数据行之间的单向链表还是数据页之间的双向链表都是按照二级索引列的键值进行排序的：

注意这里画的内节点只包含索引列的值和页号，但实际上还应包含主键值，原文中后面是有单独一章“内节点中目录项记录的唯一性”，说明存主键值是为了解决有二级索引允许重复值，但在B+树索引结构中需要唯一性，这样插入数据才能按序插入到准确位置。

MyISAM

MyISAM 存储引擎与 InnoDB 是不一样的，数据和索引分开存放：

• 将表中的记录按照记录的插入顺序单独存储在一个文件中，称之为数据文件。这个文件并不划分为若干个数据页，有多少记录就往这个文件中塞多少记录就成了。我们可以通过行号而快速访问到一条记录；
• 使用MyISAM存储引擎的表会把索引信息另外存储到一个称为索引文件的另一个文件中。
  MyISAM表的主键索引，叶子节点中存储的不是完整的用户记录，而是主键值 + 行号的组合。也就是先通过索引找到对应的行号，再通过行号去找对应的记录；
  二级索引类似，叶子节点存储的是对应字段的值 + 行号。