数据结构的定义是什么（数据结构指的是什么）
831
2022-05-29
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
RDS-MYSQL 云数据库 MySQL RDS MySQL MySQL
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
相关文章
推荐文章
最近发表
