读MySQL技术内幕 B+树与算法笔记

超、凢脫俗 2023-02-23 01:04 5阅读 0赞

读MySQL技术内幕 索引与算法笔记。  
B+树的B不代表二叉(binary)，而是代表平衡(balance)，因为B+树最早是从平衡二叉树演化而来，但是B+树不是一个二叉树。  
B+树索引并不能找到一个给定键值得具体行。B+树索引能找到的只是被查找数据行所在的页。然后数据库通过把页读入内存，再在内存中进行查找，最后得到查找的数据。  
平衡二叉树定义：首先符合二叉查找树的定义，其次必须满足任何节点的左右两个子树的高度最大差为1。

# B+树 #

B+树是为**磁盘**或其他直接**存取辅助设备**设计的一种平衡查找树。它所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上，由各叶子节点指针进行连接。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70]

## B+树插入操作 ##

B+树的插入必须保证插入后叶子节点中的记录依然排序。向B+树插入数据时会有下表中三种情况，分别对应不同的插入算法。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 1]  
并不是总是从中间阶段开始分裂，这样可能会导致页空间的浪费，key如果是随机生成的，则有可能从中间节点开始分裂，key如果是顺序生成的，则直接创建一个新的页。  
下面实例演示B+树的插入过程。

1.  Leaf Page没满且Index Page没满  
    向前面的B+树中插入键值28，可直接得到如下B+树：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 2]
2.  Leaf Page满且Index Page没满  
    再向该B+树插入键值70，此时需要根据中间值60拆分叶子节点，得到如下B+树：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 3]
3.  Leaf Page满且Index Page满  
    最后向该B+树插入键值95，叶子节点和索引节点都需要拆分，得到如下B+树：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 4]  
    为了保持平衡对于新插入的键值可能需要做大量的拆分页（split）操作。因为B+树结构主要用于磁盘，页的拆分意味着磁盘的操作，所以应该在可能的情况下尽量减少页的拆分操作。因此，B+树同样提供了类似于平衡二叉树的旋转（Rotation）功能。

## B+树删除操作 ##

B+树使用填充因子（fill factor）来控制树的删除变化，50%是填充因子可设的最小值。B+树的删除操作同样必须保证删除后叶子节点中的记录依然排序。B+树的删除操作需要考虑下表中的三种情况：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 5]  
假设填充因子为50%。先删除键值70，符合表中第一种情况，得到如下B+树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 6]  
再删除键值25，还是属于第一种情况  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 7]  
再删除键值60的。删除Leaf Page中键值为60的记录后，填充因子小于50%，这时需要做合并操作，同样，在删除Index Page中相关记录后需要做Index Page的合并操作，与插入时的旋转操作一样，最后得到如下B+树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 8]

# B+树索引 #

在数据库中，B+树的高度一般都在2～4层，就是说查找某一键值的行记录时最多只需要2到4次IO。一般的**机械磁盘每秒**至少可以做**100**次IO，2～4次的IO意味着查询时间**0.02～0.04**秒。

## 聚集索引 ##

聚集索引是按照每张表的主键构造一棵B+树，同时叶子节点中存放的就是整张表的行记录数据，也将聚集索引的叶子节点称为数据页。这个特性决定了索引组织表中数据也是索引的一部分，左右兄弟节点的数据页都通过一个双向链表来进行链接。  
 数据页上存放的是完整的每行的记录，而在非数据页的索引页中，存放的仅仅是键值及指向数据页的偏移量，而不是一个完整的行记录。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 9]  
聚集索引的存储并不是物理上连续的，而是逻辑上连续的。这其中有两点，一是前面说过的页通过双向链表链接，页按照主键的顺序排序；另一点是每个页中额记录也是通过双向链表进行维护的，物理存储上可以同样不按照主键存储。

## 辅助索引 ##

叶子节点并不包含行记录的全部数据，叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签。该书签用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。由于InnoDB存储引擎表是索引组织表，因此InnoDB存储引擎的辅助索引的书签就是相应行数据的聚集索引键。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 10]  
如果在一棵高度为3的辅助索引树中查找数据,那需要对这棵辅助索引树遍历3次找到指定主键,如果聚集索引树的高度同样为3,那么还需要对聚集索引树进行3次查找,最终找到一个完整的行数据所在的页,因此一共需要6次逻辑IO访问以得到最终的一个数据页。

参考：  
[MySQL技术内幕五：InnoDB的索引与算法][MySQL_InnoDB]  
[MySQL技术内幕读书笔记（五）——索引与算法][MySQL]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200704172846769.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200704173307124.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200704173711841.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200704173741719.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200704173817490.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200704173949289.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200704174247665.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200704174318262.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200704174345689.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200704174951372.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/2020070417523376.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[MySQL_InnoDB]: https://zhuanlan.zhihu.com/p/141678950
[MySQL]: https://www.cnblogs.com/BlueMountain-HaggenDazs/p/9355784.html