树（四）详解B+树与B树索引

小鱼儿 2023-07-10 15:52 57阅读 0赞

**目录**

1 从B树说起

1.1 B树的特点

1.2 一棵五叉B树会有哪些特点

2 构造一棵B树

2.1 准备数据

2.2 插入前四个元素

2.3 插入第五个元素

2.4 插入第六至第八的元素

2.5 插入第九个元素

2.6 插入第十至十三的元素

2.7 插入第十四元素

2.8 插入第十五个元素

2.9 插入第十六个元素

2.10 插入第十七个元素

2.11 插入最后两个元素

3 B+树

3.1 B+树的特点

3.2 构造一棵B+树

3.2 为什么Mysql使用B+树作为索引

--------------------

## 1 从B树说起 ##

Mysql有两种类型的索引，一种是HASH，一种是BTREE，大多数时候我们都选择BTREE索引。BTREE索引实际上是一个B+树，对于B+树的描述，先从B树说起。

### 1.1 B树的特点 ###

在写B+树之前先说B树。首先，B树不属于二叉树，它的节点可以拥有大于2的子节点。

B树是一种平衡的多叉树，也称为多路平衡搜索树，一棵m叉的B树具有如下特点。

（1）树中的每一个节点最多包含m个子节点；

（2）所有的叶子节点处于同一层；

（3）除根节点与叶子节点外，每个节点至少包含ceil(m/2)个子节点，这里ceil表示向上取整（比如一个7叉B树，每个节点至少包含ceil(7/2) = 4个子节点）；

（4）当根节点不是叶子节点时，根节点至少要有2个子节点；

（5）每个非叶子节点由n个key与n+1个指针组成，其中ceil(m/2)-1 <= n <= m-1。

### 1.2 一棵五叉B树会有哪些特点 ###

这里以一棵5叉B树举例。对于5叉B树，根据上面的定义，它会具有以下性质。

（1）树中的每一个节点最多包含5个子节点；

（2）所有的叶子节点处于同一层；

（3）除根节点与叶子节点外，每个节点至少包含3个子节点；

（4）当根节点不是叶子节点时，根节点至少要有2个子节点；

（5）每个非叶子节点由n个key与n+1个指针组成，这里的指针指向子节点，并且2 <= n <= 4。

## 2 构造一棵B树 ##

B树的构造与平衡二叉树不一样，平衡二叉树向下插入子节点并通过旋转等操作保持平衡，而B树以向上分裂的方式构造。

### 2.1 准备数据 ###

这里准备了19个元素元素，会以顺序插入的方式构造一棵5叉B树，数据如下。

2, 13, 6, 1, 7, 4, 10, 16, 12, 5, 14, 17, 11, 15, 3, 8, 9, 18, 19

### 2.2 插入前四个元素 ###

在插入前四个元素\[2, 13 , 6, 1\]后这棵树只有一个节点，在这个节点上有4个key，5个指针，4个key为一个节点的最大容量，下面为图示。

![20200304162411635.png][]

### 2.3 插入第五个元素 ###

上面的节点中已经有了四个元素，此时插入第五个元素\[7\]，发生向上分裂。以目前的\[1, 2, 6, 7, 13\]的中间元素向上分裂重写构造，比\[6\]小的元素作为左子树节点中的元素，比\[6\]大的元素作为右子树节点中的元素，下面为图示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70][]

### 2.4 插入第六至第八的元素 ###

接着插入第六至第八的元素\[4, 10, 16\]，此时根节点的右子树会达到单个节点的最大元素数量4个，下面为图示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 1][]

### 2.5 插入第九个元素 ###

插入第九个元素，也就是\[12\]，此时根节点的右子树节点向上分裂，将中间元素\[12\]放入根节点，并将\[7, 10\]两个元素放到同一个节点，\[13, 16\]放到另一个节点中，下面为图示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 2][]

### 2.6 插入第十至十三的元素 ###

插入第十至十三的元素\[5, 14, 17, 11\]四个元素，这四个元素插入后，依然是一棵B树，不会发生向上分裂，下面为图示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 3][]

### 2.7 插入第十四元素 ###

插入第十四个元素\[15\]，此时发生向上分裂，\[15\]这一个元素正好是\[13, 14, 15, 16, 17\]的中间元素。向上分裂之后，根节点的元素为\[6, 12, 15\]，该节点有四个子节点，下面为图示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 4][]

### 2.8 插入第十五个元素 ###

插入第十五个元素\[8\]，此时再次向上分裂，\[1, 2, 3, 4, 5\]的中间元素为\[3\]，因此将\[3\]拿到根节点，\[1, 2\]作为单独一个节点， \[4, 5\]为另一个节点，以下为图示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 5][]

### 2.9 插入第十六个元素 ###

插入第十六个元素\[8\]，不发生分裂，下面为图示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 6][]

### 2.10 插入第十七个元素 ###

插入第十七个元素\[9\]，\[7, 8, 9, 10, 11\]这个节点达到了五个元素向上分裂，取中间元素\[9\]向上分裂，此时\[3, 6, 9, 12, 15\]这个节点，也就是根节点元素数量到达五，需要将\[9\]这一个元素向上分裂，作为根节点，图示如下。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 7][]

### 2.11 插入最后两个元素 ###

插入最后两个元素，此时不发生分裂，完成B树的构造，下面为图示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 8][]

## 3 B+树 ##

从上面对B树的构造过程可以看到，B树的层级少，所以它的查询效率是比较高的；另外，在插入与删除数据的时候对于整棵树的结构影响较小，这也是它的优点。

接下来说B+树。

### 3.1 B+树的特点 ###

B+树衍生自B树，它的特点如下：

（1）一棵m叉B树的每个节点最多是有m-1个key，而B+树每个节点最多可以有m个key；

（2）B树的key在树中有序排列在每一个节点中，而B+树的所有key都在叶子节点中有序排列；

（3）B+树的所有非叶子节点都是为了查找到叶子节点。

（4）B+树的叶子节点处于同一层，并且相邻的叶子节点互相连接，使所有叶子节点形成一个链表。

### 3.2 构造一棵B+树 ###

这里我画了一棵四叉B+树，直接上图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 9][]

在这棵树中，可以通过索引（非叶子节点）找到叶子节点，叶子节点包含了这棵树的所有key，并且是有序的；另外，在每一个叶子节点也可以通过链表找到其他的叶子节点。

### 3.2 为什么Mysql使用B+树作为索引 ###

（1）选用B+树作为索引稳定且效率高，这是由于B+树所有数据都在叶子节点中，并且所有叶子节点处于同一层；

（2）B+树对于新增与修改节点的效率也是比较高的，这与B树相同；

（3）在叶子节点引入了链表，增加范围查询的效率，比如我要查询上图四叉B+树中\[11\]到\[24\]的数据，那么在根据索引（非叶子节点）找到\[11\]所在的叶子节点后，也可以根据链表找到其他叶子节点。

[20200304162411635.png]: https://img-blog.csdnimg.cn/20200304162411635.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200304163700379.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200304164438222.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200304165240690.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200304170654174.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200304171024164.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200304171554821.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/2020030417201973.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200304172955963.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/2020030417332019.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200305170128180.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3k1MDY3OTgyNzg=,size_16,color_FFFFFF,t_70