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

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

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

Page的主要结构

Page具有四个主要结构:File HeaderPage Header, Page BodyPage Trailer

其中File HeaderPage HeaderPage Trailer是定长,分别占38,568个字节。

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

  • File Header

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

blob.png

1 File Header定义

这里主要关注FIL_PAGE_PREVFIL_PAGE_NEXTFIL_PAGE_TYPE三个字段。

FIL_PAGE_TYPE

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

FIL_PAGE_NEXTPIL_PAGE_PREV

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

  • Page Header

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

blob.png

2 Page Header的定义

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

  • Page Body

Page Body包含了User RecordSystem RecordFree Space以及Page Dictionary四个部分。

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

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

blob.png

3 User Record链表的逻辑顺序

  • Free Space

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

  • Page Dictionary

Page Dirctionary用于存放PageRecord的相对位置。这种相对位置并非是偏移量,而是类似于一个记录的指针。同时并不是每个记录都会有一个这样的指针,而是拥有这样指针的记录,会使用一个额外的属性: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结构中的数据结构。用一张图来表示的话,可以表示为:

blob.png

4 Page视角的BTree


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。