目录

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为一个节点的最大容量，下面为图示。

2.3 插入第五个元素

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

2.4 插入第六至第八的元素

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

2.5 插入第九个元素

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

2.6 插入第十至十三的元素

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

2.7 插入第十四元素

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

2.8 插入第十五个元素

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

2.9 插入第十六个元素

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

2.10 插入第十七个元素

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

2.11 插入最后两个元素

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

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+树，直接上图。

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

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

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

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

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

原文链接:https://blog.csdn.net/y506798278/article/details/104638155