MySQL 源码学习(五)——Page和BTree

InnoDB通过BTree实现索引，Page(这里主要指Index Page，以下类似)包含了所有数据和索引的信息。原因是：Page为了让BTree索引更加高效，对Page的结构进行针对性的设计，使得Page被加载到内存中后，可以基于Page中的信息快速地构建出BTree，同时尽可能地减少额外的内存占用，提升BTree的修改、重构的性能。本文将通过Page的结构，来看InnoDB是如何做到这些的。

Page的主要结构

Page具有四个主要结构：File Header，Page Header, Page Body和Page Trailer。

其中File Header，Page Header和Page Trailer是定长，分别占38,56和8个字节。

而Page Body是变长的，主要存储具体的数据。下面再分别说明每个部分的具体结构。

• File Header

源代码中，File Header可以在fil0file.h文件中找到：

图1 File Header定义

这里主要关注FIL_PAGE_PREV，FIL_PAGE_NEXT及FIL_PAGE_TYPE三个字段。

FIL_PAGE_TYPE

FIL_PAGE_TYPE是PAGE的类型定义，我们知道Btr的数据都在leaf节点，非leaf节点只包含索引数据。PAGE中就一种类型，表示索引Page。从这里也就看出了，实际上整个Btr都是存储在Page中的。

FIL_PAGE_NEXT和PIL_PAGE_PREV

BTree在同一层级，不同node间有一个横向的指针，此两者就是把同一个层级的不同Page连接起来，组成双向链表的指针。

• Page Header

Page Header可以在page0page.h文件中找到定义：

图2 Page Header的定义

Page Header主要用于记录Page的状态信息，共56个字节，这里暂时不展开说明。

• Page Body

Page Body包含了User Record，System Record，Free Space以及Page Dictionary四个部分。

User Record就是存储的实际数据，为InnoDB的行数据格式。

System Record中包含了两个特殊的Record：Infimum Record和Supremum Record。这两个Record是用来表示User Record的边界。Page Body中，User Record也是以链表的形式存储，因此使用Infimum Record表示链表的头，Supremum Record表示链表尾部。为什么要有这两个特殊的Record呢。原因是我们在操作表记录时，主键有可能是不连续的，也有可能在两个主键中间插入一个拥有新主键的记录。但是Page在物理上是连续的，因此只能通过链表来实现逻辑上的连续。当我们用index进行order by时，数据库并不需要进行排序，而只需要遍历链表即可，这也就是通过索引查询高效的原因之一。如图3所示，1~5是链表连接的顺序，也是记录的逻辑顺序。

图3 User Record链表的逻辑顺序

• Free Space

Free Space是空闲的空间，当记录被删除后，User Record所占用的空间就会被放到Free Space中。

• Page Dictionary

Page Dirctionary用于存放Page中Record的相对位置。这种相对位置并非是偏移量，而是类似于一个记录的指针。同时并不是每个记录都会有一个这样的指针，而是拥有这样指针的记录，会使用一个额外的属性：n_owned来记录这条记录后面跟随了几条记录。这样就可以在找到这条记录之后，再次向后找到后面真正需要查找的记录。

需要Page Dictionary的目的是：通过Btree并不能直接查找到对应的Record(Btree 的Leaf节点并不是一条一条的Record)，只能找到这个Record所对应的Page，然后再通过Page Dictinary进行二叉查找找到对应的目录。

• Page Trailer

Page的尾部，只有FIL_PAGE_END_LSN一个字段，8个字节，前4个字节是该页的checksum，后4个字节是File Header中的FILE_PAGE_LSN。主要是用于检测Page是否被完整的写入了磁盘。

从上面对Page对说明中，我们可以看出，BTree是隐含在Page结构中的数据结构。用一张图来表示的话，可以表示为：

图4 Page视角的BTree