B树和B+树简介

旧城等待， 2022-05-18 10:28 88阅读 0赞

一.B树

一种平衡的多叉树，称为B树（或B-树、B\_树）。

一棵m阶B树是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：

1、根结点至少有两个子女；

2、每个非根节点所包含的关键字个数 j 满足：m/2 - 1 <= j <= m - 1；

3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故**内部子树**个数 k 满足：m/2 <= k <= m ；

4、所有的叶子结点都位于同一层。

在B树中，每个结点中关键字从小到大排列，并且当该结点的孩子是非叶子结点时，该k-1个关键字正好是k个孩子包含的关键字的值域的分划。

因为叶子结点不包含关键字，所以可以把叶子结点看成在树里实际上并不存在外部结点，指向这些外部结点的指针为空，叶子结点的数目正好等于树中所包含的关键字总个数加1。

B-树中的一个包含n个关键字，n+1个指针的结点的一般形式为： （n,P0,K1,P1,K2,P2,…,Kn,Pn）

其中，Ki为关键字，K1<K2<…<Kn, Pi 是指向包括Ki到Ki+1之间的关键字的子树的指针。

![70][]

先简单对上图说明一下：

*  图中的小红方块表示对应关键字所代表的文件的存储位置，实际上可以看做是一个地址，比如根节点中17旁边的小红块表示的就是关键字17所对应的文件在硬盘中的存储地址。
 *  P是指针，不用多说了，需要注意的是：指针，关键字，以及关键字所代表的文件地址这三样东西合起来构成了B树的一个节点，这个节点存储在一个磁盘块上

下面，看看搜索关键字的29的文件的过程：

1.  从根节点开始，读取根节点信息，根节点有2个关键字：17和35。因为17 < 29 < 35，所以找到指针P2指向的子树，也就是磁盘块3（1次I/0操作）
2.  读取当前节点信息，当前节点有2个关键字：26和30。26 < 29 < 30，找到指针P2指向的子树，也就是磁盘块8（2次I/0操作）
3.  读取当前节点信息，当前节点有2个关键字：28和29。找到了！（3次I/0操作）

由上面的过程可见，同样的操作，如果使用平衡二叉树，那么需要至少4次I/O操作，B树比之二叉树的这种优势，还会随着节点数的增加而增加。另外，因为B树节点中的关键字都是排序好的，所以，在节点中的信息被读入内存之后，可以采用二分查找这种快速的查找方式，更进一步减少了读入内存之后的计算时间，由此更能说明对于外存数据结构来说，I/O次数是其查找信息中最大的时间消耗，而我们要做的所有努力就是尽量在搜索过程中减少I/O操作的次数。

二.B+树

B+树是B树的一种变形，它更适合实际应用中操作系统的文件索引和数据库索引。定义如下：（为和大多资料保持一致，这里使用阶数mm来定义B+树，而不像之前的B树中，使用的是最小度tt来定义）

1.  除根节点外的内部节点，每个节点最多有m个关键字，最少有m/2个关键字。其中每个关键字对应一个子树（也就是最多有m棵子树，最少有m/2棵子树）；
2.  根节点要么没有子树，要么至少有2棵子树；
3.  所有的叶子节点包含了全部的关键字以及这些关键字指向文件的指针，并且：
    
     *  所有叶子节点中的关键字按大小顺序排列
     *  相邻的叶子节点顺序链接（相当于是构成了一个顺序链表）
     *  所有叶子节点在同一层
4.  所有分支节点的关键字都是对应子树中关键字的最大值

比如，下图就是一个非常典型的B+树的例子。

![70 1][]

B+树和B树相比，主要的不同点在以下3项：

*  内部节点中，关键字的个数与其子树的个数相同，不像B树中，子树的个数总比关键字个数多1个
 *  所有指向文件的关键字及其指针都在叶子节点中，不像B树，有的指向文件的关键字是在内部节点中。换句话说，B+树中，内部节点仅仅起到索引的作用，
 *  在搜索过程中，如果查询和内部节点的关键字一致，那么搜索过程不停止，而是继续向下搜索这个分支。

根据B+树的结构，我们可以发现B+树相比于B树，在文件系统，数据库系统当中，更有优势，原因如下：

1.  B+树的磁盘读写代价更低   
    B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说I/O读写次数也就降低了。
2.  B+树的查询效率更加稳定   
    由于内部结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
3.  B+树更有利于对数据库的扫描   
    B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题，而B+树只需要遍历叶子节点就可以解决对全部关键字信息的扫描，所以对于数据库中频繁使用的range query，B+树有着更高的性能。

ps:一棵含有N个总关键字数的m阶的B树的最大高度是 ![\\log\_\{M\}\\frac\{N+1\}\{2\}][log_M_frac_N_1_2]

证明:

设最大高度为h，根据B树定义，深度为1至少有两个结点，2(m-1)个关键字，深度为2至少有2m个节点2m(m-1)个关键字，深度为3至少2m\*m=2![m^\{2\}][m_2]个节点，2![m^\{2\}][m_2](m-1)个关键字，以此类推，深度为h的，至少有2![m^\{h-1\}][m_h-1]个节点，2![m^\{h-1\}][m_h-1]（m-1）个关键字。因此，关键字个数N满足：

![N>=1+(m-1)\\sum\_\{i=1\}^\{h\}2m^\{i-1\}][N_1_m-1_sum_i_1_h_2m_i-1],得出h<=![\\log\_\{M\}\\frac\{N+1\}\{2\}][log_M_frac_N_1_2]

转载自：[B树与B+树][B_B]

关于B树和B+树的详细介绍详细介绍：[从B树、B+树、B\*树谈到R 树][B_B_B_R]

[70]: /images/20220518/4efd20e43ac54a7f955c1f46be0ba134.png
[70 1]: /images/20220518/808064616c4d487885a34b018e6a74ae.png
[log_M_frac_N_1_2]: https://private.codecogs.com/gif.latex?%5Clog_%7BM%7D%5Cfrac%7BN&plus;1%7D%7B2%7D
[m_2]: https://private.codecogs.com/gif.latex?m%5E%7B2%7D
[m_h-1]: https://private.codecogs.com/gif.latex?m%5E%7Bh-1%7D
[N_1_m-1_sum_i_1_h_2m_i-1]: https://private.codecogs.com/gif.latex?N%3E%3D1&plus;%28m-1%29%5Csum_%7Bi%3D1%7D%5E%7Bh%7D2m%5E%7Bi-1%7D
[B_B]: https://blog.csdn.net/guoziqing506/article/details/64122287
[B_B_B_R]: https://blog.csdn.net/v_july_v/article/details/6530142