一句话总结：在 InnoDB 里，一个索引就是一棵 B+ 树。

那么这个 B+ 树是什么样子的呢？

数据存储在叶子节点，中间节点存目录项。

那么，

叶子节点啥样的？

中间节点啥样的？

要知道节点的结构，就得先知道 InnoDB 管理存储空间的基本单位 —— 页。

InnoDB 引擎将数据划分为若干个页，以页作为磁盘和内存之间交互的基本单位，页的大小一般为 16 KB。InnoDB 设计了许多种不同类型的页，比如存放表数据记录的页，存放表空间头部信息的页，存放 Insert Buffer 信息的页，存放 undo 日志的页等等，而这之中存放表中索引数据记录的页即数据页就是 B+ 数的叶子节点。

数据页

数据页中由多个部分组成，不同部分有不同的作用，其结构如下图：

其中，各个部分的作用如下：

  • File Header

File Header 是各种类型的页都有的部分，它描述了一些针对各种页都通用的一些信息，比方说这个页的编号是多少，它的上一个页、下一个页分别是谁等信息。通过 File Header 存储的上一页下一页的信息，各个数据页可以组成一种双向链表的结构。

  • Page Header

Page Header 用来存储本页中已经存储了多少条记录，第一条记录的地址是什么，页目录中存储了多少个槽等。

  • Infimum + Supremum

InnoDB 定义的两条分别为最小记录与最大记录的伪记录

  • User Records

User Records 插入数据库的记录存储的地方，一开始生成页的时候，并没有 User Records 这部分，每当插入一条记录后，都会从 Free Space 部分申请一个记录大小的空间划分到 User Records 部分，当插入的记录越来越多导致 Free Space 用完之后，也就意味着这个也使用完了，要再插入新记录，就需要申请新的页了。每条记录通过 next_record 属性记录着下一条记录的地址偏移量，即所有记录实际上是一个单向链表的结构。记录里的 record_type 属性值为 0。

  • Page Directory

为了便于查找， InnoDB 将 User Records 里的记录划分为多个组，每个组的最后一条记录的地址偏移量取出来放在 Page Directory 中，这个地址偏移量被称为槽（Slot），所以 Page Directory 就是由槽组成的。

所以在页中要查找一条记录的过程是：通过主键值用二分法确定要查找的记录位于哪个槽所对应的组中，在对应的组里遍历（每个组里包含的记录只能是 1 ~ 8 条）找到对应的记录。

  • File Trailer

File Trailer 是用来校验页是否完整的，确保数据在内存和磁盘间同步不会有差错。

以上就是数据页的结构，所以，索引的叶子节点就是存有被设为索引的记录的数据页。

索引的结构

上面说到数据页之间是通过 File Header 里记录的信息来找到上一页和下一页的信息，那么如何找到第一页呢？这里就得需要有目录项了，每个目录项包括两个部分：页的用户记录中最小的主键值和页号。因为存储的记录会很多导致目录项也很多，所以为了方便对目录项进行存放和管理，InnoDB 目录项的结构设计是跟数据页一样的，不同的是其中保存记录的部分存放的是目录的信息，即目录的主键和其页号，且记录里的record_type 属性值为 1。

目录指向叶子节点的的示意图如下：

当存储的记录越来越多导致目录项越来越多时，要查找一个目录项就变得越来越不容易，此时，就需要有指向目录项的目录了，于是一直演变下去就会出现多级目录，形成数据的索引，而这个多级目录就是一个树的结构，如下图所示：

在 InnoDB 里这种树叫 B+ 树，所谓的索引就是长这样。