[ 数据库索引 ] B树和B+树

我会带着你远行 2022-03-06 03:34 318阅读 0赞

### B+树 ###

[点击这里即可][Link 1]

### B树(多路平衡查找树,基本特性同Ｂ+树) ###

B 树中的每个节点由两部分组成：

*  数据
 *  指向孩子节点的指针

每一个节点最多包含`k`个孩子，`k`被称为`B`树的阶，`k`的大小取决于磁盘页的大小(一个节点一次IO，一页)

一个`m`阶的`B`树具有如下几个特征：

*  1.根结点至少有两个子女。
 *  2.每个中间节点都包含k-1个元素和k个孩子，其中 `m/2 <= k <= m`
 *  3.**每一个叶子节点都包含k-1个元素**，其中 `m/2 <= k <= m`（这里就有时候会导致节点的拆分和合并，其实就是为了保持平衡）
 *  4.**所有的叶子结点都位于同一层（有点搞不懂这是为什么？）**
 *  5.**每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70]  
    删除时的左右旋：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 2]

### B+与B树的区别 ###

*  Ｂ树会将数据存放在非叶子节点上，B+树都是存储在叶子节点上，所以一个磁盘页能够容纳更多的索引节点元素
 *  B+ 以链表将数据来凝结起来（主要是为了实现区间查找）
 *  B+树查询必须查找到叶子节点，B树只要匹配到即可不用管元素位置，因此B+树查找更稳定（并不慢）；

# `注意`: #

*  一般情况，根节点会被存储在内存中，其他节点存储在磁盘中。（每一个节点都是一页，也就是说双向链表连接的是一个一个的数据页，数据页中包含的数据可能是一行记录，也可能是多行记录。）
 *  B+树索引并不能找到一个具体行。B+树索引能找到的只是被查找数据行所在的页。然后数据库通过把页读人到内存，再在内存中进行查找，最后得到要查找的数据。
 *  也就是说真正的数据是被存储在磁盘上的。

[Link 1]: https://blog.csdn.net/liushengxi_root/article/details/86751217#MYSQLB_44
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70]: /images/20220306/2cafc581364546ddaa38bf7916e29864.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 1]: /images/20220306/88c5b4fb35124277822e13aeca901a7c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 2]: /images/20220306/84d96ae883a1416fb1c6b329e713d9c4.png