# 平衡多路搜索树

Ｂ树和Ｂ＋树的出现是因为磁盘ＩＯ；众所周知，ＩＯ操作的效率很低，那么，当在大量数据存储中，查询时我们不能一下子将所有数据加载到内存中，只能逐一加载磁盘页，每个磁盘页对应树的节点。造成大量磁盘ＩＯ操作（最坏情况下为树的高度）。平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。所以，我们为了减少磁盘ＩＯ的次数，就你必须降低树的深度，将“瘦高”的树变得“矮胖”。一个基本的想法就是：

1. **每个节点存储多个元素**
2. **摒弃二叉树结构，采用多叉树**

这样就引出来了一个新的查找树结构 ——多路查找树（multi-way search tree）。 一颗平衡多路查找树自然可以使得数据的查找效率保证在`O(logN)`这样的对数级别上。

## :pencil2: &#x31;**、B树** <a href="#yibshu" id="yibshu"></a>

### :pen\_fountain: **1.1、B树的定义** <a href="#id-1b-shu-de-ding-yi" id="id-1b-shu-de-ding-yi"></a>

B数也称为B-树，他是一棵多路平衡查找树。我们描述一棵B树时需要指定它的阶数，阶数表示了一个节点最多有多少的孩子节点，一般使用字母m表示阶数。当m取2时，就是我们常见的二叉搜索树。

一棵m阶的B数定义如下：

1. 每个节点最多有`m-1`个关键字
2. 根节点最少可以只有一个关键字
3. 非根节点至少有`ceil(m/2)-1`个关键字
4. 每个节点的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它
5. 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的路径长度都相同

![](http://img.xianzilei.cn/B%E6%A0%91%E4%BE%8B%E5%9B%BE-002.png)

上图表示是一棵4阶B树（当然实际中B树的阶数一般远大于4，通常大于100，这样即使存储大量的数据，B树的高度仍然很低），每个节点最多有3个关键字，每个非根节点最少有`Math.ceil(4/2)-1`=1个关键字。我们将**一个key和其对应的data称为一个记录**。数据库中如果以B树作为索引结构，此时B树中的`key`就表示键，而`data`表示了这个键对应的条目在硬盘上的逻辑地址。

### :pen\_fountain: **1.2、B树的搜索操作** <a href="#id-2b-shu-de-sou-suo-cao-zuo" id="id-2b-shu-de-sou-suo-cao-zuo"></a>

**以上图为例，比如我要查找关键字为25对应的数据，步骤如下**：

1. 首先拿到根节点关键字，目标关键字与根节点的关键字key比较，25<36，去往其左孩子节点查找
2. 获取当前节点的关键字15和28,15<25<28，所有查询15和28的中间孩子节点
3. 获取当前节点的关键字19和25，发现25=25，所以直接返回关键字和data数据（如果没有查询到则返回null）

### :pen\_fountain: 1.3、**B树的插入操作** <a href="#id-3b-shu-de-cha-ru-cao-zuo" id="id-3b-shu-de-cha-ru-cao-zuo"></a>

插入操作是指插入**一条记录**，即（key, data）的键值对。如果B树中已存在需要插入的键值对，则用需要插入的**新data替换旧的data**。若B树不存在这个key，则一定是在**叶子节点**中进行插入操作。

#### **1.3.1 基本步骤** <a href="#id-31-ji-ben-bu-zhou" id="id-31-ji-ben-bu-zhou"></a>

1. 根据key找到要插入的叶子节点位置，插入记录
2. 判断当前节点key的个数是否小于等于`m-1`，如果是直接结束，否则进行第三步
3. 以节点中间的key为中心分裂成左右两部分，然后将这个中间的key插入到父节点中，这个key的左子树指向分裂后的左半部分，这个key的右子支指向分裂后的右半部分，然后将当前节点指向父节点，继续进行第3步，直到处理完根节点。

#### **1.3.2 图文说明** <a href="#id-32-tu-wen-shuo-ming" id="id-32-tu-wen-shuo-ming"></a>

以5阶B树为例（5阶B树节点最多有4个关键字，最少有2个关键字，其中根节点最少可以只有一个关键字），从初始时刻依次插入数据。

* 在空数中插入39

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-q_ZFC6ZxzeRlGu6P%2Fimage.png?alt=media\&token=2e4a79cd-4aa6-49ed-9330-a2a57223f8f4)

* 继续插入22，97和41

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-qrvzL8m7U8DS0Fty%2Fimage.png?alt=media\&token=66c1be32-0b6a-45ec-9d3d-434cde2de21f)

此时根节点有4个关键字

* 继续插入53

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-qx5k6QE6ZsThOv--%2Fimage.png?alt=media\&token=48004305-9c01-4439-9f87-9059d81047fa)

此时发现该节点有5个关键字超过了最大允许的关键字个数4，所以以key为41为中心进行分裂，分裂后当前节点指向根节点，根节点的关键字为1，满足B数条件，插入操作结束，结果如下所示（注意，如果阶数是偶数，分裂时就不存在排序恰好在中间的key，那么我们选择中间位置的前一个key或中间位置的后一个key为中心进行分裂即可）

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-r17jg9zgfYmtbL-O%2Fimage.png?alt=media\&token=21d444e5-b555-49d2-a701-64e1a644ec6f)

* 插入13，21，40

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-r8ElNJuOe6yLnsJR%2Fimage.png?alt=media\&token=4e27c74b-08a7-4179-b4af-3b5b359fbbcb)

此时当前节点5个关键字，需要分裂，则以22为中心，22节点插入到其父节点中，分裂后当前节点指向根节点，根节点的关键字为2，满足B数条件，插入操作结束，结果如下所示

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-rCp8nbsRrUnEPrpg%2Fimage.png?alt=media\&token=2242c082-3779-4fbe-b86c-a0a47ec9e011)

* 同理依次输入30，27, 33 ，36，35，34 ，24，29，结果如下所示

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-rIPRnFqPWc1J3bAE%2Fimage.png?alt=media\&token=8acc324e-6c25-4ecb-a9b3-1bc58d5f500c)

* 继续插入26

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-rOFkEmjbVn2G87PR%2Fimage.png?alt=media\&token=b25d02e4-bb89-4660-9ae9-3ad19759ab3b)

此时节点关键字等于5，以27为中心分裂，并将27插入到父节点中，分裂后当前节点指向根节点，如下所示

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-rY4a4bHpelq8unIt%2Fimage.png?alt=media\&token=ca054024-333a-4b08-b551-8f0eaf866e70)

此时27的进位导致当前节点也需要分裂，则以33为中心进行分裂，结果如下

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-ra5RgIz6o7uJzMYR%2Fimage.png?alt=media\&token=85952c3e-2ebc-463f-8a26-5d965c84c959)

* 7）同理最后再依次插入17，28，29，31，32，结果如下图所示

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-rfSqjvBznNC1vH_C%2Fimage.png?alt=media\&token=fa921968-75a8-4310-850f-d27bb0ca1b39)

#### **1.3.3 总结** <a href="#id-33-zong-jie" id="id-33-zong-jie"></a>

一般来说，对于确定的m和确定类型的记录，节点大小是固定的，无论它实际存储了多少个记录。但是分配固定节点大小的方法会**存在浪费的情况**，比如key为28和29所在的节点，还有2个key的位置没有使用，但是已经不可能继续在插入任何值了，因为这个节点的前序key是27，后继key是30，所有整数值都用完了。所以如果记录先按key的大小排好序，再插入到B树中，节点的使用率就会很低，**最差情况下使用率仅为50%**。

### :pen\_fountain: 1.4、**B树的删除操作** <a href="#id-4b-shu-de-shan-chu-cao-zuo" id="id-4b-shu-de-shan-chu-cao-zuo"></a>

**删除操作是指根据key删除记录，如果B树中的记录中不存对应key的记录，则删除失败。**

#### **1.4.1 基本步骤** <a href="#id-41-ji-ben-bu-zhou" id="id-41-ji-ben-bu-zhou"></a>

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上移，删除操作结束。
4. 否则，将**父节点中的key下移与当前节点及它的兄弟节点中的key合并**，形成一个新的节点。原父节点中的key的两个孩子指针就变成了一个孩子指针，指向这个新节点。然后当前节点的指针指向父节点，重复上第2步。（有些节点它可能即有左兄弟，又有右兄弟，那么我们任意选择一个兄弟节点进行操作即可）

#### **1.4.2 图文说明** <a href="#id-42-tu-wen-shuo-ming" id="id-42-tu-wen-shuo-ming"></a>

以5阶B树为例（5阶B树节点最多有4个关键字，最少有2个关键字，其中根节点最少可以只有一个关键字）。初始时刻以上述插入操作的最终状态为例。

* 初始状态

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-rq1S4Yk3JYmN_Zoh%2Fimage.png?alt=media\&token=a9fcc672-503d-43ca-bc8d-2d69fb9fbb6e)

* 删除节点21

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-rv4wTKydo5NQ4lJ_%2Fimage.png?alt=media\&token=c8bffbe9-8e69-464a-9260-9ad83e0dd623)

删除后节点中的关键字个数仍然大于等2，所以删除结束。

* 继续删除27，此时27由于是非叶子节点，则由它的后继节点28替换27，再删除28，结果如下所示

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-s-8N4mdw2j7mdMSg%2Fimage.png?alt=media\&token=fa3be598-6a33-429e-95c7-0d5295068d4b)

此时发现叶子节点的个数小于2，而它的兄弟节点中有3个记录（当前节点还有一个右兄弟，选择右兄弟就会出现合并节点的情况，不论选哪一个都行，只是最后B树的形态会不一样而已），我们可以从兄弟节点中借取一个key。所以父节点中的28下移，兄弟节点中的26上移,删除结束。结果如下图所示

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-s4n-gSUi_DXA9p8y%2Fimage.png?alt=media\&token=3a0dd0d7-e08b-4994-8f16-7b48e6446723)

* 删除32，结果如下图所示

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-s9tzpORFV1_Girl2%2Fimage.png?alt=media\&token=91d69cde-025a-4d47-a9f2-6db2ace6b726)

当前节点中只有一个key，而兄弟节点中也仅有2个key。所以只能让**父节点中的30下移和这个两个孩子节点中的key合并**，成为一个新的节点，当前节点的指针指向父节点。结果如下图所示

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-sEXHubbhaujDvf17%2Fimage.png?alt=media\&token=532edc32-63ea-4784-84ce-49bbc1ecfb98)

当前节点key的个数满足条件，故删除结束

* 接着删除key为40的记录，删除后结果如下图所示

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-sJDbaDz9c4Y1Cwy_%2Fimage.png?alt=media\&token=2606a594-dda5-49c1-b02e-156ec6322979)

同理，当前节点的记录数小于2，兄弟节点中没有多余key，所以父节点中的key下移，和兄弟（这里我们选择左兄弟，选择右兄弟也可以）节点合并，合并后的指向当前节点的指针就指向了父节点。如下图所示

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-sQ-de50vN_caA71j%2Fimage.png?alt=media\&token=66c852f4-d9e6-4dc7-97b7-837550f3de11)

同理，对于当前节点而言只能继续合并了，最后结果如下所示

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-sSPVKfRkBuRlGu0i%2Fimage.png?alt=media\&token=da894b89-2f2a-4511-8651-0ac6ca52a928)

合并后节点当前节点满足条件，删除结束。

## :pencil2: 2、**B+树** <a href="#erbshu" id="erbshu"></a>

### :pen\_fountain: 2.1、**B+树的定义** <a href="#id-1b-shu-de-ding-yi-1" id="id-1b-shu-de-ding-yi-1"></a>

B+树是B树的一种变形形式。**网上各种资料上B+树的定义各有不同，一种定义方式是关键字个数和孩子节点个数相同。这里我们采取维基百科上所定义的方式，即关键字个数比孩子节点个数小1，这种方式是和B树基本等价的**。除了B树的性质，B+树还包括以下要求：

1. B+树包含2种类型的节点：**内部节点（也称索引节点）和**叶子节点。根节点本身即可以是内部节点，也可以是叶子节点。根节点的关键字个数最少可以只有1个。
2. B+树与B树最大的不同是**内部节点不保存数据**，**只用于索引**，所有数据（或者说记录）都**保存在叶子节点中**。
3. m阶B+树表示了**内部节点最多有m-1个关键字**（或者说内部节点最多有m个子树），阶数m同时限制了**叶子节点最多存储m-1个记录**。
4. 内部节点中的key都按照**从小到大**的顺序排列，对于内部节点中的一个key，左树中的所有key都**小于**它，右子树中的key都**大于等于**它。叶子节点中的记录也按照key的大小排列。
5. 每个**叶子节点都存有相邻叶子节点的指针**，叶子节点本身依关键字的大小自小而大顺序链接。

![](http://img.xianzilei.cn/B%2B%E6%A0%91%E4%BE%8B%E5%9B%BE-001.png)

上图是一棵阶数为4的B+树

### :pen\_fountain: 2.2、**B+树的搜索操作** <a href="#id-2b-shu-de-sou-suo-cao-zuo-1" id="id-2b-shu-de-sou-suo-cao-zuo-1"></a>

**操作流程同B树的搜索流程，只不过如果要找的关键字匹配上了索引节点的关键字，需要继续往下找，因为索引节点不存储数据，所有的数据都存储在叶子节点上。**

### :pen\_fountain: 2.3、**B+树的插入操作** <a href="#id-3b-shu-de-cha-ru-cao-zuo-1" id="id-3b-shu-de-cha-ru-cao-zuo-1"></a>

#### **2.3.1 基本步骤** <a href="#id-31-ji-ben-bu-zhou-1" id="id-31-ji-ben-bu-zhou-1"></a>

1. 若为空树，创建一个叶子节点，然后将记录插入其中，此时这个叶子节点也是根节点，插入操作结束。
2. 针对**叶子类型**节点：根据key值找到叶子节点，向这个叶子节点插入记录。插入后，若当前节点key的个数小于等于m-1，则插入结束。否则将这个叶子节点分裂成左右两个叶子节点，左叶子节点包含前m/2个记录，右节点包含剩下的记录，将第m/2+1个记录的key进位到父节点中（父节点一定是索引类型节点），进位到父节点的key左孩子指针向左节点,右孩子指针向右节点。将当前节点的指针指向父节点，然后执行第3步。
3. 针对**索引类型**节点：若当前节点key的个数小于等于m-1，则插入结束。否则，将这个索引类型节点分裂成两个索引节点，左索引节点包含前(m-1)/2个key，右节点包含m-(m-1)/2个key，将第m/2个key进位到父节点中，进位到父节点的key左孩子指向左节点, 进位到父节点的key右孩子指向右节点。将当前节点的指针指向父节点，然后重复第3步。

#### **2.3.2 图文说明** <a href="#id-32-tu-wen-shuo-ming-1" id="id-32-tu-wen-shuo-ming-1"></a>

以5阶B+树为例（5阶B+树节点最多有4个关键字，最少有2个关键字，其中根节点最少可以只有一个关键字），从初始时刻依次插入数据。

* 在空树插入5

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-sd_p4eaIvVT_VTap%2Fimage.png?alt=media\&token=b622308b-d699-490c-a25c-7cb409053562)

* 依次插入8,10,15

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-snUuoR7w6_dyULje%2Fimage.png?alt=media\&token=6921d39f-8e9e-42a8-9353-d1a5eaf3a9c2)

* 插入16

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-suBOBmxsgDaNn8B_%2Fimage.png?alt=media\&token=0aa13e82-6dbb-4a34-83ee-9a83532b7dcf)

此时节点超过关键字的个数，所以需要进行分裂。由于该节点为叶子节点，所以可以分裂出来左节点2个记录，右边3个记录，中间key成为索引节点中的key（也可以左节点3个记录，右节点2个记录），分裂后当前节点指向了父节点（根节点）。结果如下图所示

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-sx4-SLP81NbeCjWL%2Fimage.png?alt=media\&token=4960b574-89fb-428d-9f8f-854e9f232bbb)

当前节点的关键字个数满足条件，插入结束

* 插入17

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-t1If1VzJPgvR4FYa%2Fimage.png?alt=media\&token=04560196-32d4-479b-a0ce-75944ca688b3)

* 插入18

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-t6itS-w4SgkL1hfc%2Fimage.png?alt=media\&token=c49c7e5b-3085-4647-99d0-2879a3781e76)

当前节点超过关键字的个数，进行分裂。由于是叶子节点，分裂成两个节点，左节点2个记录，右节点3个记录，关键字16进位到父节点（索引类型）中，将当前节点的指针指向父节点，如下图所示

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-tA9UiH9caQehVwGY%2Fimage.png?alt=media\&token=b007bcd5-59e1-4505-976d-c2d6f249c31a)

当前节点的关键字个数满足条件，插入结束

* 同理继续插入6,9,19，细节不再描述

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-tIfoxSm62H31jCoZ%2Fimage.png?alt=media\&token=0f0ecb11-2e15-4500-a986-187f4b89447e)

* 继续插入7

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-tMsBLLPEXx31d8tE%2Fimage.png?alt=media\&token=af57891d-a33a-495a-9e51-1e8c8539b6d7)

当前节点超过关键字的个数，进行分裂。由于是叶子节点，分裂成两个节点，左节点2个记录，右节点3个记录，关键字7进位到父节点（索引类型）中，将当前节点的指针指向父节点，如下图所示

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-tR4Ch-1oe_FBtgc5%2Fimage.png?alt=media\&token=867414ea-1fa0-49c1-9282-3f8f83dcea83)

当前节点超过关键字的个数，进行分裂。由于是索引节点，左节点2个关键字，右节点2个关键字，关键字16进入到父节点中，将当前节点指向父节点，如下图所示

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-tVOEupWqMVsBoJ-l%2Fimage.png?alt=media\&token=145bf086-52db-4546-9614-4f1d72d4acea)

当前节点的关键字个数满足条件，插入结束

### :pen\_fountain: 2.4、**B+树的删除操作** <a href="#id-4b-shu-de-shan-chu-cao-zuo-1" id="id-4b-shu-de-shan-chu-cao-zuo-1"></a>

#### **2.4.1 基本步骤** <a href="#id-41-ji-ben-bu-zhou-1" id="id-41-ji-ben-bu-zhou-1"></a>

如果叶子节点中没有相应的key，则删除失败。否则执行下面的步骤：

1. 删除叶子节点中对应的key。删除后若节点的key的个数大于等于`ceil(m-1)/2 – 1`，删除操作结束,否则执行第2步。
2. 若兄弟节点key有富余（大于`ceil(m-1)/2 – 1`），向兄弟节点借一个记录，同时用借到的key替换父结（指当前节点和兄弟节点共同的父节点）点中的key，删除结束。否则执行第3步。
3. 若兄弟节点中没有富余的key,则当前节点和兄弟节点合并成一个新的叶子节点，并删除父节点中的key（父节点中的这个key两边的孩子指针就变成了一个指针，正好指向这个新的叶子节点），将当前节点指向父节点（必为索引节点），执行第4步（第4步以后的操作和B树就完全一样了，主要是为了更新索引节点）。
4. 若索引节点的key的个数大于等于`ceil(m-1)/2 – 1`，则删除操作结束。否则执行第5步
5. 若兄弟节点有富余，父节点key下移，兄弟节点key上移，删除结束。否则执行第6步
6. 当前节点和兄弟节点及父节点下移key合并成一个新的节点。将当前节点指向父节点，重复第4步。

**注意，通过B+树的删除操作后，索引节点中存在的key，不一定在叶子节点中存在对应的记录。**

#### **2.4.2 图文说明** <a href="#id-42-tu-wen-shuo-ming-1" id="id-42-tu-wen-shuo-ming-1"></a>

以5阶B树为例（5阶B树节点最多有4个关键字，最少有2个关键字，其中根节点最少可以只有一个关键字）。初始时刻以上述插入操作的最终状态为例。

* 初始状态

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-pTYPQiNQoaAfJgty%2Fimage.png?alt=media\&token=c7e70ada-984e-40c1-a9c5-ab10a34f11a0)

* 删除22

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-pYr1y1J3eWQbdMq5%2Fimage.png?alt=media\&token=56832eef-ba36-425c-86ed-bd486a0027e5)

删除后叶子节点中key的个数大于等于2，删除结束

* 删除15

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-pf9RX2IfJVN_En8L%2Fimage.png?alt=media\&token=90aa256b-fa8b-40f0-8c75-5f947c57894c)

当前节点只有一个key，不满足条件，而兄弟节点有三个key，可以从兄弟节点借一个关键字为9的记录,同时更新将父节点中的关键字由10也变为9，删除结束。

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-pjGCXr2QujgiJmo3%2Fimage.png?alt=media\&token=b81e5c71-369a-4171-a83b-508ddc65ae77)

* 删除7

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-pMLAaQPfqcEjLB8K%2Fimage.png?alt=media\&token=4b14868f-0fd4-4707-9562-945c1693c82e)

当前节点关键字个数小于2，（左）兄弟节点中的也没有富余的关键字（当前节点还有个右兄弟，不过选择任意一个进行分析就可以了，这里我们选择了左边的），所以当前节点和兄弟节点合并，并删除父节点中的key，当前节点指向父节点。

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-n6JVrJ4N2w4W4VcA%2Fimage.png?alt=media\&token=022abe3e-48d0-4894-992f-c25898b95039)



此时当前节点的关键字个数小于2，兄弟节点的关键字也没有富余，所以父节点中的关键字下移，和两个孩子节点合并，结果如下图所示。

![](https://2046787257-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MAj0mT0YWnpRKaj44YN%2F-MF-MaZdk0pH_ZNBMIMW%2F-MF-mnPm8VrgMx9ZClTP%2Fimage.png?alt=media\&token=8359bc6a-1c0e-4748-9090-5538e51a7e8b)

删除结束。

> B+树的优点在于：&#x20;
>
> 1. 由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。 因此访问叶子节点上关联的数据也具有更好的缓存命中率。&#x20;
> 2. B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。 而且由于数据顺序排列并且相连，所以便于区间查找和搜索。 而B树则需要进行每一层的递归遍历，相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
>
> 但是B树也有优点，其优点在于： 由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。



