MySQL学习笔记（二）-索引相关之B树与B+树

淡淡的烟草味﹌ 2022-11-19 01:16 64阅读 0赞

## 一、B树 ##

**1、定义**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70]

**2、插入**

> （1）插入一个元素时，首先在B树中是否存在，如果不存在，即比较大小寻找插入位置，在叶子结点处结束，然后在叶子结点中插入该新的元素；  
> （2）如果叶子结点空间足够，这里需要向右移动该叶子结点中大于新插入关键字的元素，如果空间满了以致没有足够的空间去添加新的元素，则将该结点进行“分裂”，将一半数量的关键字元素分裂到新的其相邻右结点中，中间关键字元素上移到父结点中（当然，如果父结点空间满了，也同样需要“分裂”操作）；  
> （3）当结点中关键元素向右移动了，相关的指针也需要向右移。如果在根结点插入新元素，空间满了，则进行分裂操作，这样原来的根结点中的中间关键字元素向上移动到新的根结点中，因此导致树的高度增加一层；

**具体插入例子参考**：https://www.jianshu.com/p/21fa21f5cc7e

**3、删除**

> （1）如果当前需要删除的key位于非叶子结点上，则用后继key（这里的后继key均指后继记录的意思）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步；
> 
> （2）该结点key个数大于等于Math.ceil(m/2)-1，结束删除操作，否则执行第3步。
> 
> （3）如果兄弟结点key个数大于Math.ceil(m/2)-1，则父结点中的key下移到该结点，兄弟结点中的一个key上移，删除操作结束。  
> 否则，将父结点中的key下移与当前结点及它的兄弟结点中的key合并，形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复上第2步。  
> 有些结点它可能即有左兄弟，又有右兄弟，那么我们任意选择一个兄弟结点进行操作即可。

**参考博文及例子：** https://blog.csdn.net/shenchaohao12321/article/details/83243314

## 二、B+树 ##

**1、定义**

*  每个节点最多可以有 m 个元素；
 *  除了根节点外，每个节点最少有 (m/2) 个元素；
 *  如果根节点不是叶节点，那么它最少有 2 个孩子节点；
 *  所有的叶子节点都在同一层；
 *  一个有 k 个孩子节点的非叶子节点有 (k-1) 个元素，按升序排列；
 *  某个元素的左子树中的元素都比它小，右子树的元素都大于或等于它；
 *  非叶子节点只存放关键字和指向下一个孩子节点的索引，记录只存放在叶子节点中；
 *  相邻的叶子节点之间用指针相连。

**2、插入方法：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70 1]

> 我们用实例来分析B+树的插入，我们插入28这个键值，发现当前Leaf Page和Index Page都没有满，我们直接插入就可以了。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70 2]  
> 这次我们再插入一条70这个键值，这时原先的Leaf Page已经满了，但是Index Page还没有满，符合表5-1的第二种情况，这时插入Leaf Page后的情况为50、55、60、65、70。我们根据中间的值60拆分叶节点。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70 3]  
> 因为图片显示的关系，这次我没有能在各叶节点加上双向链表指针。最后我们来插入记录95，这时符合表5-1讨论的第三种情况，即Leaf Page和Index Page都满了，这时需要做两次拆分。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70 4]

**3、删除方法**

*  B+树使用填充因子（fill factor）来控制树的删除变化，50%是填充因子可设的最小值。B+树的删除操作同样必须保证删除后叶节点中的记录依然排序，同插入一样，B+树的删除操作同样需要考虑如表5-2所示的三种情况，与插入不同的是，删除根据填充因子的变化来衡量。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70 5]

> 首先，删除键值为70的这条记录，该记录符合表5-2讨论的第一种情况，删除后。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70 6]  
> 接着我们删除键值为25的记录，这也是表5-2讨论的第一种情况，但是该值还是Index Page中的值，因此在删除Leaf Page中25的值后，还应将25的右兄弟节点的28更新到Page Index中，最后可得到图。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70 7]  
> 最后我们来看删除键值为60的情况，删除Leaf Page中键值为60的记录后，填充因子小于50%，这时需要做合并操作，同样，在删除Index Page中相关记录后需要做Index Page的合并操作，最后得到图。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70 8]  
> **注意：** 辅助索引 的叶子节点的 data 域记录着主键的值，因此在使用辅助索引进行查找时，需要先查找到主键值，然后再到主索引中进行查找；即先进行非聚簇索引查找，再对查找到的主键的值进行聚簇索引查找，最后取到相应的数据。  
> 博文参考：https://www.cnblogs.com/wade-luffy/p/6292784.html

## 三、索引 ##

**1、定义**

*  数据库索引好比是一本书前面的目录，能加快数据库的查询速度。索引是对数据库表中一个或多个列的值进行排序的结构。如果想按特定职员的姓来查找他或她，则与在表中搜索所有的行相比，索引有助于更快地获取信息
 *  常见的查询算法：顺序查找、二分查找、二叉排序树查找、哈希散列法、分块查找、平衡多路搜索树B树（B-tree）
 *  索引是在存储引擎层实现的，而不是在服务器层实现的，所以不同存储引擎具有不同的索引类型和实现。

**2、优缺点**

> 优点：  
> 1.大大加快数据的检索速度;  
> 2.创建唯一性索引，保证数据库表中每一行数据的唯一性;  
> 3.加速表和表之间的连接;  
> 4.在使用分组和排序子句进行数据检索时，可以显著减少查询中分组和排序的时间。  
> 缺点：  
> 1.索引需要占用数据表以外的物理存储空间  
> 2.创建索引和维护索引要花费一定的时间  
> 3.当对表进行更新操作时，索引需要被重建，这样降低了数据的维护速度。

**3、索引类型**

*  唯一索引： UNIQUE 例如：create unique index stusno on student（sno）；

> 表明此索引的每一个索引值只对应唯一的数据记录，对于单列唯一性索引，这保证单列不包含重复的值。对于多列唯一性索引，保证多个值的组合不重复。

*  主键索引： primary key

> 数据库表经常有一列或列组合，其值唯一标识表中的每一行。该列称为表的主键。在数据库关系图中为表定义主键将自动创建主键索引，主键索引是唯一索引的特定类型。该索引要求主键中的每个值都唯一。当在查询中使用主键索引时，它还允许对数据的快速访问。

*  聚集索引（也叫聚簇索引）：cluster

> 在聚集索引中，表中行的物理顺序与键值的逻辑（索引）顺序相同。一个表只能包含一个聚集索引。如果某索引不是聚集索引，则表中行的物理顺序与键值的逻辑顺序不匹配。与非聚集索引相比，聚集索引通常提供更快的数据访问速度。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70]: /images/20221022/8215908d05af45169010fee25617f2af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70 1]: /images/20221022/743763da88184237b3b0736f50adbf24.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70 2]: /images/20221022/4324f2c32446428887b1739139172a95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70 3]: /images/20221022/f9c08e6e599d43d1b9f1be2a1a4b9373.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70 4]: /images/20221022/1dbcb53680ef4d429a9e06989e33b339.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70 5]: /images/20221022/62f065519b09482a816d28ba1521a889.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70 6]: /images/20221022/8e84d848573c4ea985fb15f3dcc88484.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70 7]: /images/20221022/07d15e9e590a453ea48d7dd71b105ceb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70 8]: /images/20221022/40f4893157e5467e9f1755f8ef70943d.png