A-A+

Innodb页面存储结构-1

2014年05月21日 DB 暂无评论

本文介绍Innodb的索引数据页面存储结构,主要介绍数据页面的整体结构,而页面的详细结构将会在另一篇中介绍。

1. B+树

阅读本文前,首先要知道一些关于B树的基础知识。Innodb的一个表可能包含多个索引,每个索引都使用B+树来存储。而索引包括聚集索引和二级索引,聚集索引使用表的主键作为索引键,包含表的所有字段。二级索引只包含索引键和聚集索引键(主键)的内容,不包括其他字段。每一个索引都是一棵B+树,每棵B+树由很多页面组成,而每个页面大小一般为16K。从B+树的组织结构来看,B树的页面可分为:

  • 叶子节点:B树层次为0的页面,存储记录的所有内容
  • 非叶子节点:B树层次大于0的页面,只存储索引键和页面指针。

一个B+树的结构大概为

1

图1 B+树的总体结构

从上图可知,相同层次的页面是用一个双向链表连接起来的。一般情况下,从B+树的最左边叶子节点开始,一直向右扫描,就可以得到B+树的从小到大的所有数据。因此,对于叶子节点,有如下特征:

  • 页内数据是按索引键排序的。
  • 页面的任一记录的索引键值不小于其左兄弟页面的任何记录。

那么,下文主要介绍两方面内容:

  • 页面的存储格式
  • 页面记录如何保证有序

2. 页面存储格式

一个页面的存储格式如下图显示:

wps_clip_image-8606

图2 Innodb页面存储格式

从上图得,一个页面的存储由以下几部分组成:

1. 页头(Page Header):记录页面的控制信息,共占150字节,包括页的左右兄弟页面指针、页面空间使用情况等,页头的详细说明会在下一篇中描述。

2. 最小虚记录、最大虚记录:两个固定位置存储的虚记录,本身并不存储数据。最小虚记录比任何记录都小,而最大虚记录比任何记录都大。

3. 记录堆(record heap):指上图的橙黄色部分。表示页面已分配的记录空间,也是索引数据的真正存储区域。记录堆分为两种,即有效记录和已删除记录。有效记录就是索引正常使用的记录,而已删除记录表示索引已经删除,不在使用的记录,如上图的深蓝色部分。随着记录的更新和删除越来越频繁,记录堆中已删除记录将会越多,即会出现越来越多的空洞(碎片)。这些已删除记录连接起来,就会成为页面的自由空间链表。

4. 未分配空间:指页面未使用的存储空间,随着页面不断使用,未分配空间将会越来越小。当新插入一条记录时,首先尝试从自由空间链表中获得合适的存储位置(空间足够),如果没有满足的,就会在未分配空间中申请。

5. slot区:slot是一些页面有效记录的指针,每个slot占两个字节,存储了记录相对页面首地址的偏移。如果页面有n条有效记录,那么slot的数量就在n/8+2~n/4+2之间。下一节详细介绍slot区,它是记录页面有序和二分查找的关键。

6. 页尾(Page Tailer):页面最后部分,占8个字节,主要存储页面的校验信息。

页面中的页头,最大/最小虚记录以及页尾都是页面中有固定的存储位置。而我们最关心的页面结构可能是记录堆以及slot区。那么,页面记录如何保证有序的呢?看下节的介绍。

3. 如何保证有序

上文说到,数据页内的数据是按索引键有序的。那么怎么保证这种有序性呢?我们先分析一些可能做法。

普通做法1:

在记录堆中,记录是按存储顺序排序的,即rec1<rec2<rec3...<rec_m。那么,如果需要插入一条新记录rec索引键大小在rec2和rec3之间,那么就需要rec3记录及以后的记录堆内容需要向右memmov一个rec大小的空间,然后再插入新记录rec。这样能保证数据是有序的,但性能会非常低下。

普通做法2:

换一种做法,如果页面记录不是按存储空间有序,而是使用一个链表连接起来,从链头到链尾依次有序。那么插入一条记录,只要修改前后两记录的指针就行,这样就可以避免记录的移动同时保证了有序性。但是,带来的问题是,链表是无法使用二分查找的,这样的设计会导致查询效率低下。

文艺做法:

为了减少页面记录的移动,保证页面数据的有序性,同时满足二分查找的要求,可以在页面的尾部空间中分配了Slot区。每一个slot占两个字节,存储记录相对页面的偏移。并且slot对应的记录是从右往左(从高地址到低地址)依次有序的,例如图2中S2对应的记录必定大于S1指向的记录。

现假设一个slot对应一条记录,如slot1对应rec_a,slot2对应rec_b,slot3对应rec_c,以此类推,并且rec_a<rec_b<rec_c...。那么,如果在rec_a和rec_b之间插入新记录rec,只要将slot2到slot_n之间的空间向左平移2字节,原slot2空间指向新记录rec。这样,插入记录就不用关心rec的存储位置,只要平移若干slot空间就可以了,并且能保证数据按slot是有序的。

如果查找记录,由于每一个slot的大小固定并且空间是连续的,就可以通过二分查找来定位记录。

个人认为这是比较文艺的做法,但我们看看innodb比较2B的真正做法。

innodb真正的2B做法:

3

图3 页面记录逻辑组织结构

事实上,innodb页面记录都已经通过一个链表维护起来,并且从链头到链尾依次增大(普通方法2)。这种方式之前也已经说到,是无法使用二分查找。为了解决这个问题,innodb使用若干slot指向链的某些记录,而不是slot跟记录一一对应,如图3所示。

Slot指向的记录依然保证着从右往左依次有序的特性,我们使用rec[S2]表示S2指向的记录,那么rec[S2]>rec[S1]。另外,本文称两个slot之间的记录称为一个Slot支链,如图3虚线圈住的部分,表示S2指向的Slot支链。Innodb维护的Slot支链高度为4-8,如果一个支链的高度超过或不足,会导致相应的支链拆分和合并操作。

如何查询?

如果在页面中查询记录r1(为简单起见,假设索引键是唯一的)。首先通过二分查找定位Slot号X,满足

rec[X-1]< r1 <= rec[X]

那么记录r1要么不存在,要么就在Slot支链X中。接着就是遍历这条支链,找到真正记录。但支链的搜索只能一一遍历,不能使用二分查找。

如何插入?

首先通过查询的方式确定插入的Slot支链和插入位置,在自由空间链表或未分配空间中获得空间并写记录内容,slot支链高度加1,同时维护好原链表的关系。

插入记录后,如果Slot支链高度超过8,那么就将该支链拆分为两个子链,同时多申请一个slot(平移此slot及其后面的空间)。

这样设计有什么好处?

这种设计相当于文艺做法有什么好处呢?想了很久,只想到了一个,就是减少了slot的分配和移动。然而,这样设计的缺点倒是不少。

  • 从存储空间中说,虽然slot减少了,但记录需要指针链接起来(同样2个字节),文艺做法是没有必要将记录按序链接起来的,因此这样反而增多了空间使用(另外,支链高度的维护也是有空间代价的,下一篇会详述)。
  • 从存取效率上,不能完全的二分查找,需要使用二分查找+顺序遍历,查询性能也有所折扣。
  • 从复杂度上,大大增大代码的复杂度。

是不是某些巧妙的地方需要这样的设计来达到更好的性能呢?也有这种可能,不过暂时还没发现。而我所知的数据库更多是用那种“文艺”的设计方案。

事实上,定长页面的整体存储结构都是大同小异的,主要都是由图2的这些部分组成。具体不同可能是在于页头的详细内容以及记录的存储格式,这些内容将会下一篇介绍。

参考

《MySQL技术内幕-InnoDB存储引擎》

http://hedengcheng.com/?p=118

原创文章,转载请注明: 转载自腾讯游戏DBA团队

本文链接地址: Innodb页面存储结构-1

文章的脚注信息由WordPress的wp-posturl插件自动生成

Copyright © 腾讯游戏DBA团队 保留所有权利.  

用户登录

分享到: