mysql对B+树插入逻辑的优化

墨蓝 2023-10-05 08:54 25阅读 0赞

## B+树插入逻辑 ##

1，如果结点不存在，则新生成一个结点，作为B+树的根结点，结束。  
2，如果结点存在，则查找当前数值应该插入的位置，定位到需要插入到叶子结点，然后插入到叶子结点。  
3，插入的结点如果未达到最大数量，结束。如果达到最大数量，则把当前叶子结点对半分裂：\[m/2\]个放入左结点，剩余放入右结点。  
4，将分裂后到右结点的第一个值提升到父结点中。若父结点元素个数未达到最大，结束。若父结点元素个数达到最大，分裂父结点：\[m/2\]个元素分裂为左结点，m-\[m/2\]-1个分裂为右结点，第\[m/2\]+1个结点提升为父结点。

下面以实际操作讲解。为了演示，我们以3阶B+树为例。  
演示网站：[点这里][Link 1]

1）插入结点5：B+树根结点不存在，生成根结点  
![在这里插入图片描述][20200824100952504.png_pic_center]

2）插入结点8：根结点存在，查找存放结点为根结点，插入  
![在这里插入图片描述][2020082410105870.png_pic_center]

3）插入结点10 ：同2）  
![在这里插入图片描述][2020082410120996.png_pic_center]  
结点元素个数达到最大3，分裂结点。（\[3/2\]=）1个元素放左边，剩余2个元素放右边。并将右子结点的第一个值提升到父结点。  
![在这里插入图片描述][20200824101400426.png_pic_center]

4）插入结点15 ：找到插入到叶子结点，并插入，然后调整。步骤同3）  
![在这里插入图片描述][20200824101616209.png_pic_center]  
5）插入结点20 ：步骤同3）  
![在这里插入图片描述][20200824101730167.png_pic_center]  
插入完成后，父结点元素个数达到最大，继续分裂父结点。（\[3/2\]=）1个结点分裂为左结点；3-\[3/2\]-1=1个结点，分裂为右结点；第（\[3/2\]+1=）2个结点提升为父结点。  
![在这里插入图片描述][20200824103134237.png_pic_center]

## mysql索引的B+树插入优化 ##

以上就是B+树的插入逻辑。你应该已经发现，虽然B+树为3阶树，但是分裂后的叶子结点都只有1～2个。如果这个算法应用到数据库索引，假设一个磁盘分页可以存放2千条数据，但是每次分裂后，都只存储1000条数据在磁盘分页中，那么必然会造成磁盘浪费。而且时接近50%的浪费。B+树的这个设计，是因为插入的结点不是有序的，每次的插入，定位到每个叶子结点的可能性都是有的，所以采用对半分，防止叶子结点频繁分裂造成性能问题。但是索引值一般是自增数值，所以已经分裂过的叶子结点，后面是不会再有结点插入的。所以这部分的浪费是不可接受的。

出于以上考虑，mysql做了一版优化，即叶子结点在分裂时，不再按照对半分，而是保持原有的叶子结点不变，将超出的结点插入新的叶子结点，并把这个结点值，提升到父结点。父结点的分裂逻辑（待考证）。

但是，这样会引发新的问题。假如索引值是严格按照顺序插入的，那么没有问题，如果不是，就会引发更严重的空间浪费。  
例如有下面一颗5阶B+树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0_size_16_color_FFFFFF_t_70_pic_center]

现在插入结点19，定位到左边叶子结点；插入后，该叶子结点达到最大值，然后分裂出新结点结点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0_size_16_color_FFFFFF_t_70_pic_center 1]  
同理，继续插入结点18，同样会分裂出18的叶子结点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0_size_16_color_FFFFFF_t_70_pic_center 2]  
由于，18，19，20之间已经没有其他整型数值，所以18，19这两个结点永远都只有一个值，无疑带来了更严重的存储空间浪费。要知道，磁盘分页存储的可不是十几二十条记录。

然而，mysql团队很快也发现了这个问题，并在一次补丁中修复了该漏洞。详情可参见[官方说明][Link 2]。

接下来，我们就用官方说明里面的方法，来验证现行的mysql索引的插入逻辑是怎么样的。

## mysql的B+树插入逻辑 ##

### mysql版本 ###

### 新建测试表 ###

CREATE TABLE test.page_split_test
    (
      id BIGINT UNSIGNED NOT NULL,
      payload1 CHAR(255) NOT NULL,
      payload2 CHAR(255) NOT NULL,
      payload3 CHAR(255) NOT NULL,
      payload4 CHAR(255) NOT NULL,
      PRIMARY KEY (`id`)
    ) ENGINE=INNODB;

### 填充B+树根结点 ###

填充根结点至分裂前的最大值

# Fill up the root page, but don't split it.
    
    INSERT INTO test.page_split_test (id, payload1, payload2, payload3, payload4) 
    VALUES 
    (1, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (2, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (3, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (4, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (5, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (6, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (7, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (8, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (9, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (10, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (11, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (12, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (13, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (14, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255));

查看B+树结点情况

SELECT page_number, page_type, number_records, data_size
    FROM information_schema.innodb_buffer_page
    WHERE table_name like "%page_split_test%" AND index_name = "PRIMARY";

结果如下，当前只有一个根结点，含14个数据行  
![在这里插入图片描述][20200824192415985.png_pic_center]

### 首次分裂 ###

继续插入一个数据，B+树达到最大，首次进行分裂。

INSERT INTO test.page_split_test (id, payload1, payload2, payload3, payload4) 
    VALUES (15, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255));

查看B+树结点情况如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0_size_16_color_FFFFFF_t_70_pic_center 3]  
根结点对半分裂成两个结点，左结点（第5页）和右结点（第6页），原来的根结点（第4页）升级为父结点，父结点中包含两个元素，分别为指向两个子结点的引用。

### 继续填充右叶子结点 ###

继续插入数据，填充右叶子结点至临近饱和状态。

INSERT INTO test.page_split_test (id, payload1, payload2, payload3, payload4) 
    VALUES 
    (16, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (17, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (18, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (19, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (20, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (21, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255));

查看B+树状态  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0_size_16_color_FFFFFF_t_70_pic_center 4]  
右叶子结点已达临近饱和状态。

### 添加隔离开的结点 ###

添加结点，和原来的主键隔开距离。（从30开始）

INSERT INTO test.page_split_test (id, payload1, payload2, payload3, payload4) 
    VALUES
    (45, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (30, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (31, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (32, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (33, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255)),
    (34, REPEAT("A", 255), REPEAT("B", 255), REPEAT("C", 255), REPEAT("D", 255));

查看B+树状态。此时新加了一个叶子结点，切父结点新增了指向新增叶子结点的数据。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0_size_16_color_FFFFFF_t_70_pic_center 5]

在这里，mysql并没有像之前的bug一样，生成6个结点，而是将后面的6个结点合并成了一个。这就是mysql做的再一次优化，即叶子结点满了之后，如果该叶子结点后面有还有叶子结点，则会将新的数据插入到后续的叶子结点中。

然而这样的方案，虽然避免了空间浪费，但是增加了索引插入时的性能。极端假设，新增的数据定位到了第一个叶子结点，插入后，叶子结点达到最大数量，然后分裂出最后的一个元素插入到后一个叶子结点。假设后面的叶子结点都是已经满额的状态，那么这个插入会导致所有的叶子结点都发生一次分裂，且所有父结点的数据都要重新调整。这样的效率简直是灾难性的。  
然而，这个问题，可以通过人为的避免，那就是使用自增索引。自增索引，可以保证每次插入的主键都是递增的，永远都只会修改和新增最右的叶子结点，而不用修改原有叶子结点。所以，使用递增索引，可以大大提升数据的插入效率。

以上就是我整理的关于mysql的B+树的插入逻辑。如有不正，还望指出。

[Link 1]: https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
[20200824100952504.png_pic_center]: https://img-blog.csdnimg.cn/20200824100952504.png#pic_center
[2020082410105870.png_pic_center]: https://img-blog.csdnimg.cn/2020082410105870.png#pic_center
[2020082410120996.png_pic_center]: https://img-blog.csdnimg.cn/2020082410120996.png#pic_center
[20200824101400426.png_pic_center]: https://img-blog.csdnimg.cn/20200824101400426.png#pic_center
[20200824101616209.png_pic_center]: https://img-blog.csdnimg.cn/20200824101616209.png#pic_center
[20200824101730167.png_pic_center]: https://img-blog.csdnimg.cn/20200824101730167.png#pic_center
[20200824103134237.png_pic_center]: https://img-blog.csdnimg.cn/20200824103134237.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200824105328315.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200824105456372.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200824105611760.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0,size_16,color_FFFFFF,t_70#pic_center
[Link 2]: https://bugs.mysql.com/bug.php?id=67718
[20200824192415985.png_pic_center]: https://img-blog.csdnimg.cn/20200824192415985.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20200824192627159.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20200824193208532.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20200824193527972.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0,size_16,color_FFFFFF,t_70#pic_center