从MySQL Bug#67718浅谈B+树索引的分裂优化

1月 6th, 2013

问题背景

今天,看到Twitter的DBA团队发布了其最新的MySQL分支:Changes in Twitter MySQL 5.5.28.t9,此分支最重要的一个改进,就是修复了MySQL 的Bug #67718:InnoDB drastically under-fills pages in certain conditions。关于此Bug的详细描述,以及如何重现此问题,可以阅读以上的Bug链接,以下简单描述下此Bug对应的问题:

 

InnoDB的索引分裂策略,在特定的情况下,索引页面的分裂存在问题,导致每个分裂出来的页面,仅仅存储一条记录,页面的空间利用率极低。

 

此Bug引起了我的兴趣,因此准备跟大家简单聊聊B+树索引的结构、B+树的分裂、B+树分裂操作的优化、Bug #67718的成因,以及个人对如何修复此Bug的一些建议等。

 

B+树索引结构

传统关系型数据库(Oracle/MySQL/PostgreSQL…),其主要的索引结构,使用的都是B+树。更有甚者,InnoDB引擎的表数据,整个都是以B+树的组织形式存放的。下图,是一个经典的B+树组织结构图(2层B+树,每个页面的扇出为4):

 

注意:

  • 此B+树,以InnoDB实现的B+树结构为准;
  • 此B+树,有5条用户记录,分别是1,2,3,4,5;
  • B+树上层页面中的记录,存储的是下层页面中的最小值(Low Key);
  • B+树的所有数据,均存储在B+树的叶节点;
  • B+树叶节点的所有页面,通过双向链表链接起来;

 

B+树的分裂

在上图B+树的基础上,继续插入记录6,7,B+树结构会产生以下的一系列变化:

插入记录6,新的B+树结构如下:

 

插入记录7,由于叶页面中只能存放4条记录,插入记录7,导致叶页面分裂,产生一个新的叶页面。

 

传统B+树页面分裂操作分析:

  • 按照原页面中50%的数据量进行分裂,针对当前这个分裂操作,3,4记录保留在原有页面,5,6记录,移动到新的页面。最后将新纪录7插入到新的页面中;
  • 50%分裂策略的优势:
    • 分裂之后,两个页面的空间利用率是一样的;如果新的插入是随机在两个页面中挑选进行,那么下一次分裂的操作就会更晚触发;
  • 50%分裂策略的劣势:
    • 空间利用率不高:按照传统50%的页面分裂策略,索引页面的空间利用率在50%左右;
    • 分裂频率较大:针对如上所示的递增插入(递减插入),每新插入两条记录,就会导致最右的叶页面再次发生分裂;

 

疑问

传统50%分裂的策略,有不足之处,如何优化?接着往下看。

 

B+树分裂操作的优化

由于传统50%分裂的策略,有不足之处,因此,目前所有的关系型数据库,包括Oracle/InnoDB/PostgreSQL,以及本人以前参与研发的Oscar数据库,目前正在研发的NTSE、TNT存储引擎,都针对B+树索引的递增/递减插入进行了优化。经过优化,以上的B+树索引,在记录6插入完毕,记录7插入引起分裂之后,新的B+树结构如下图所示:

 

对比上下两个插入记录7之后,B+树索引的结构图,可以发现二者有很多的不同之处:

  • 新的分裂策略,在插入7时,不移动原有页面的任何记录,只是将新插入的记录7写到新页面之中;
  • 原有页面的利用率,仍旧是100%;
  • 优化分裂策略的优势:
    • 索引分裂的代价小:不需要移动记录;
    • 索引分裂的概率降低:如果接下来的插入,仍旧是递增插入,那么需要插入4条记录,才能再次引起页面的分裂。相对于50%分裂策略,分裂的概率降低了一半;
    • 索引页面的空间利用率提高:新的分裂策略,能够保证分裂前的页面,仍旧保持100%的利用率,提高了索引的空间利用率;
  • 优化分裂策略的劣势:
    • 如果新的插入,不再满足递增插入的条件,而是插入到原有页面,那么就会导致原有页面再次分裂,增加了分裂的概率。

 

因此,此优化分裂策略,仅仅是针对递增递减插入有效,针对随机插入,就失去了优化的意义,反而带来了更高的分裂概率。

 

在InnoDB的实现中,为每个索引页面维护了一个上次插入的位置,以及上次的插入是递增/递减的标识。根据这些信息,InnoDB能够判断出新插入到页面中的记录,是否仍旧满足递增/递减的约束,若满足约束,则采用优化后的分裂策略;若不满足约束,则退回到50%的分裂策略。

 

但是,InnoDB的实现,有不足之处,会导致下面提到的一个Bug。

 

Bug#67718的成因

在Bug#67718中提到,在特定的插入情况下,InnoDB的索引页面利用率极低,这是由于InnoDB不正确的使用优化分裂策略导致的。

考虑以下的一个B+树,已有的用户数据是1,2,3,4,5,6,100,并且在插入记录100之后,引起索引页面分裂,记录100在分裂后被插入到新的页面:

 

由于插入100能够满足递增的判断条件,因此采用了优化分裂策略,分裂不移动数据,新纪录100插入到新页面之中,原有页面的最后插入位置仍旧是6号记录不变,原有页面仍旧保持递增的插入标识不变。

此时,考虑连续插入9,8,7这几条记录,会得到什么样的B+树?此时,全局递增插入变为全局递减插入。

插入记录9后的B+树结构:

由于InnoDB的B+树,上层节点保存的是下层页面中的最小值(Low Key),因此记录9仍旧会插入到【3,4,5,6】页面,此时页面已满,需要分裂。而且判断出记录9仍旧满足页面中的递增判断条件(Last_Insert_Pos = 6,9插入到6之后,并且原来是递增插入的)。因此,采用优化的分裂策略,产生新的页面插入记录9,原有页面记录保持不变。

 

插入记录8后的B+树结构:

 

插入记录7,也一样。采用优化的分裂策略,记录7独占一个页面。

 

分析:

  • Bug#67718的主要副作用
    • 是页面的利用率极低,每个索引叶页面,只能存放一条记录;
  • Bug#67718的主要原因
    • InnoDB错误的采用了优化的索引分裂策略。InnoDB判断是否满足递增/递减的插入模式,采用的是页面级的判断,哪怕全局的模式发生了变化,只要页面内记录的模式未变,仍旧会选择优化后的索引分裂策略;

修复Bug#67718的建议

在本人做Oscar数据库的索引分裂优化时,当时也同样碰到了此问题。当时的解决方案是:每次分裂,若插入的记录是页面中的最后一条记录,则至少将此记录前一条记录分裂到新页面之中。采用此策略,针对100,9,8这一个系列的插入,会产生以下的系列B+树:

插入100,9,8后的B+树:

 

插入100时,移动原有页面最后一条记录到新的页面(将6移动到新页面),此时新页面中的记录为【6,100】。接下来插入9,8,都会插入到新的页面之中,不会产生分裂操作,空间利用率提高,减少了索引页面分裂,解决了Bug#67718的问题。

 

当然,肯定还有更优的策略,欢迎感兴趣的朋友们一起讨论!

 

 

  1. jerry
    1月 6th, 201317:49

    这个策略很简单,但是很有效。
    btw:如果一直是递减序列插入(假如每次插入的值都小于树中的所有值),该如何优化。

    • hedengcheng
      1月 6th, 201320:06

      递减与递增有区别吗?

      • jerry
        1月 7th, 201313:33

        因为B+Tree记录的是Low Key,对细节了解不是特别清楚,感觉递减有区别。假如每次插入的值都是比当前最小值小的key,是不是要在最左边每次新增新页?如果是B-Tree的话没这个问题,B+Tree感觉有这个问题,可能Innodb的B+Tree处理过这个问题。

  2. Feico
    1月 6th, 201320:33

    在 key-value不为简单数字的时候,比如说都是一个可变长字符串,那么会出现分裂完之后,节点的剩余空间不足以插入这对key-value怎么办?

    • hedengcheng
      1月 6th, 201321:07

      数据库的索引不会出现你说的这种情况。例如:对于InnoDB来说,索引记录的长度,必须小于页面大小的1/2,因此分裂之后一定能够放下新的记录。

  3. Louix.Gu
    1月 7th, 201300:06

    这个bug没能通过单元测试发现么?另外看https://launchpad.net/mysql-server 的代码,也没发现里面有实质性的单测,这个比较奇怪,是在其他repository中提供了么?

    • hedengcheng
      1月 7th, 201309:45

      这个是新发现的,目前还没有针对这个功能缺陷的测试。

  4. alex
    1月 7th, 201309:54

    如果以空间利用率优先的话,我想是不是可以用以下的策略:
    在插入100之后插入9时, 100后移,插入9,更新上一层索引。 会增加移动数据的开销,但是空间利用率会极高。

    • hedengcheng
      1月 7th, 201313:15

      这个做法是不行的,插入9时,根本不会定位到100这一个页面。

      • alex
        2月 2nd, 201311:55

        恩,你说的对。不过如果简单修改一下定位的逻辑,是能定位到100的页面的吧。

        另外有个问题想请假一下:那这个B+树的叶子节点在文件中是一个什么格式存储的呢?
        每一个节点是定长的吗?

  5. gpfeng.cs
    1月 7th, 201313:07

    分析的比较清晰,PG的Btree在create index时会采用优化分裂策略,会先排序后插入,没记错的这时默认填充因子是90,而一条一条插入时,是不会使用优化分裂策略的,这时的默认填充因子是70,innodb是聚簇索引组织的,主键如果和业务相关,无法保证递增/递减,但是如果主键和业务无关,那么innodb相对于堆表的一次IO优势就没了,另一个解决方案:用户在插入记录时如果包含了主键就放弃使用优化分裂策略

    • hedengcheng
      1月 8th, 201309:57

      首先,我认为PG内部应该也会在插入时进行判断,是否可以采用优化分裂策略,因为可以根据页面中维护的上次插入位置进行判断,或者是说PG没做这个优化?对于InnoDB,一般都会建议使用无意义的自增ID字段做主键,此时能够保证主键索引的空间利用率。当然,这么做的话,是会存在你提到的问题,省一次IO的优势没有这么明显了。还有,至于是否采用优化分裂策略,这个是通过内部维护的信息决定,哪怕全局不可用,局部可用优化分裂策略,也是好的。

      • gpfeng.cs
        1月 8th, 201314:26

        更正一下:
        90是PG创建索引的叶子节点的默认填充因子(可调整)
        70是非叶子节点默认填充因子(不可调整)

        优化策略:
        分裂结点时,如果该结点为该层的最右节点,必须保证分裂后的左节点的空闲空间为(100-fillfactor)%,否则左右结点空闲空间相等

  6. 李添翼
    1月 7th, 201316:10

    这个是不是可以设置成一个填充参数,就像hashtable那样的,让用户根据自己的业务需求去调整就行了!

    • hedengcheng
      1月 8th, 201309:52

      这个是不行的,无论业务模式如何,数据库是并发操作的,真正进入Insert的记录,并不一定按照业务模式递增/递减,还是要靠数据库内部进行判断。

  7. gpfeng.cs
    1月 7th, 201318:41
  8. baifan
    1月 8th, 201310:46

    我觉得这样改还是有点问题,如果碰到数据递减操作但是有上下波动(这种情况还是有的),还是会出现页面大量浪费的情况,比如原始树的6和100改成600和1000,然后连续插入 500 550 400 450 300 350 200 250,这样每两条数据将产生一个新的node。

    • baifan
      1月 8th, 201310:48

      还有 这样的话不会对整个树的平衡性造成影响么

    • hedengcheng
      1月 8th, 201318:35

      谢谢,我看看你提的这个问题。还有回答你下面的那个问题,无论如何分裂,树的平衡性都是能够保证的。

    • hedengcheng
      1月 9th, 201311:36

      谢谢baifan,你提的这个问题是存在的,以你给出的这个序列,还是会存在索引页面利用率不高的情况,有什么更好的优化建议吗?

      • baifan
        1月 10th, 201318:24

        呵呵,我觉得有些特殊情况没覆盖到也是正常的,就像快速排序也对有序的序列性能也很差啊,只要这个算法的特殊情况出现的几率够低就好了

      • baifan
        1月 10th, 201318:25

        mysql 那个优化其实在于Last_Insert_Pos 保存的是6,但实际上Last Insert 应该是100,只不过100被分裂到另外一个node去了,这样才导致了下个9进来的时候判定为连续递增,那么Last_Insert_Pos能不能不是记录该node的最大record,而是记录上一次预想加入的那个值(不管能不能成功加入),那么当100插入的时候Last_Insert_Pos设置为100? 9进来的时候就设置为9? 这样递增判定就不会错了
        不知道这样做有没有其他问题,我只发现会增大了有6那个node的Last_Insert_Pos更新的频率,不管新record能不能加入(好比那个100),Last_Insert_Pos都要刷新。
        而且我觉得Last_Insert_Pos不需要每次有数据进node都记录,在一个node加满最后一条数据之前,Last_Insert_Pos都是无用的,因为node没满,谈不上分裂,只有node加满最后一个record的时候,Last_Insert_Pos才应该开始记录值,不知道 mysql是不是这样做的

        • hedengcheng
          1月 13th, 201317:21

          首先,你提到的前一个问题,也是我想到的,在页面内维护插入序列,丢失了全局序列。
          对于第二个想法,Last_Insert_Pos不需要每次记录,这个是有问题的,因为这个InnoDB的这个优化,对应的是递增/递减插入的分裂优化,而不是仅仅针对最后一次
          的插入,因此,Last_Insert_Pos跟N_Directions合用,才能确定是否需要进行优化分裂,其中,N_Directions指的是页面内同一方向连续插入记录的数量

          • baifan
            1月 14th, 201310:11

            N_Directions? 意思就是node必须满足被插入多个同方向的值才进行优化分裂?哦,那Last_Insert_Pos确实每次要记录,我以为就Last_Insert_Pos一个判定条件

          • yinfeng
            1月 14th, 201314:19

            我好像没有看到决定分裂时使用N_Directions,只是单纯的判断插入位置是在PAGE_LAST_INSERT的左边还是右边;
            例如函数btr_page_get_split_rec_to_right,如果插入点在上次插入记录的右边,且插入点的下一条或者下下条是supremum record,就从插入点分裂,否则从插入点的下下条记录开始分裂

          • hedengcheng
            1月 14th, 201316:27

            有的,判断分裂位置时会用,因为随机插入到最后的位置,不属于递增的分裂优化范畴

  9. wangxiaozhong
    1月 15th, 201314:26

    我决定索引无论怎么分裂,总能构造出一个序列是能让索引的空间利用率很低的用例
    终极的解决方案是能在适当的时候进行索引页面的合并,提高索引页面的重用
    尤其对于大批量删除操作,这些索引页面当时无法回收,以后如果不修改这些页面,将严重影响范围扫描的性能
    如果在适当的时机进行一次索引页面的回收,一切问题可以解决

    • Kowl
      2月 1st, 201317:42

      optimize table 能解决 索引合并的问题吗?
      听起来像ORACLE的索引碎片整理。

  10. weijunbao
    1月 31st, 201314:13

    在当前页面的最后插入的时候,预读下一个Page(NP),如发现NP没满的话,直接在NP插入不行?当然这样额外的IO