经典数据结构 [ B树，B+树 ]+B树的应用

逃离我推掉我的手 2022-05-25 02:08 167阅读 0赞

关于B树的原理和实现方法，我也是研究了好久才看明白的，没明白之前感觉一脸懵逼，看懂后才发现原来也很简单。所以同学们要是发现很难看懂的情况下，不要烦躁着急，可以先冷静冷静的思考一下，然后多看几篇文章，我也是看了好几篇的文章才看懂的，要是大家看完之后还是不大懂的话，可以再文章最后联系我，加油！

B 树是为了磁盘或其它存储设备而设计的一种多叉（下面你会看到，相对于二叉，B树每个内结点有多个分支，即多叉）平衡查找树。

B 树又叫平衡多路查找树。一棵m阶的B 树 (m叉树)的特性如下：

1.  树中每个结点最多含有m个孩子（m>=2）；
2.  除根结点和叶子结点外，其它每个结点至少有\[ceil(m / 2)\]个孩子（其中ceil(x)是一个取上限的函数）；
3.  若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；
4.  所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；
5.  每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：  
           a)   Ki (i=1...n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。   
           b)   Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。   
           c)   关键字的个数n必须满足： \[ceil(m / 2)-1\]<= n <= m-1。

**![8394323_13074405906V6Q.jpg][]**

来模拟下查找文件29的过程：

(1) 根据根结点指针找到文件目录的根磁盘块1，将其中的信息导入内存。【磁盘IO操作1次】

(2) 此时内存中有两个文件名17，35和三个存储其他磁盘页面地址的数据。根据算法我们发现17<29<35，因此我们找到指针p2。

(3) 根据p2指针，我们定位到磁盘块3，并将其中的信息导入内存。【磁盘IO操作2次】

(4) 此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据。根据算法我们发现26<29<30，因此我们找到指针p2。

(5) 根据p2指针，我们定位到磁盘块8，并将其中的信息导入内存。【磁盘IO操作3次】

(6) 此时内存中有两个文件名28，29。根据算法我们查找到文件29，并定位了该文件内存的磁盘地址。

插入操作

生成从空树开始，逐个插入关键字。但是由于B\_树节点关键字必须大于等于\[ceil(m/2)-1\],所以每次插入一个关键字不是在树中添加一个叶子结点，而是首先在最底层的某个非终端节点中添加一个“关键字”，该结点的关键字不超过m-1,则插入完成；否则要产生结点的“分裂”，将一半数量的关键字元素分裂到新的其相邻右结点中，中间关键字元素上移到父结点中。

1、咱们通过一个实例来逐步讲解下。插入以下字符字母到一棵空的B 树中（非根结点关键字数小了（小于2个）就合并，大了（超过4个）就分裂）：C N G A H E K Q M F W L T Z D P R X Y S，首先，结点空间足够，4个字母插入相同的结点中，如下图：

![8394323_1307525908RHSE.jpg][]

2、当咱们试着插入H时，结点发现空间不够，以致将其分裂成2个结点，移动中间元素G上移到新的根结点中，在实现过程中，咱们把A和C留在当前结点中，而H和N放置新的其右邻居结点中。如下图：

![8394323_1307525905BTbZ.jpg][]

3、当咱们插入E,K,Q时，不需要任何分裂操作

![8394323_1307525899vG17.jpg][]

4、插入M需要一次分裂，注意M恰好是中间关键字元素，以致向上移到父节点中

![8394323_1307525899h5rR.jpg][]

5、插入F,W,L,T不需要任何分裂操作

![8394323_1307525895Gzrw.jpg][]

6、插入Z时，最右的叶子结点空间满了，需要进行分裂操作，中间元素T上移到父节点中，注意通过上移中间元素，树最终还是保持平衡，分裂结果的结点存在2个关键字元素。

![8394323_13075258952zo1.jpg][]

7、插入D时，导致最左边的叶子结点被分裂，D恰好也是中间元素，上移到父节点中，然后字母P,R,X,Y陆续插入不需要任何分裂操作（别忘了，树中至多5个孩子）。

![8394323_1307525895q8j1.jpg][]

8、最后，当插入S时，含有N,P,Q,R的结点需要分裂，把中间元素Q上移到父节点中，但是情况来了，父节点中空间已经满了，所以也要进行分裂，将父节点中的中间元素M上移到新形成的根结点中，注意以前在父节点中的第三个指针在修改后包括D和G节点中。这样具体插入操作的完成。

![8394323_1307525894XPqO.jpg][]

删除操作

首先查找B树中需删除的元素,如果该元素在B树中存在，则将该元素在其结点中进行删除，如果删除该元素后，首先判断该元素是否有左右孩子结点，如果有，则上移孩子结点中的某相近元素到父节点中，然后是移动之后的情况；如果没有，直接删除后，移动之后的情况。

删除元素，移动相应元素之后，如果某结点中元素数目（即关键字数）小于ceil(m/2)-1，则需要看其某相邻兄弟结点是否丰满（结点中元素个数大于ceil(m/2)-1）（还记得第一节中关于B树的第5个特性中的c点么?： c)除根结点之外的结点（包括叶子结点）的关键字的个数n必须满足： （ceil(m / 2)-1）<= n <= m-1。m表示最多含有m个孩子，n表示关键字数。在本小节中举的一颗B树的示例中，关键字数n满足：2<=n<=4），如果丰满，则向父节点借一个元素来满足条件；如果其相邻兄弟都刚脱贫，即借了之后其结点数目小于ceil(m/2)-1，则该结点与其相邻的某一兄弟结点进行“合并”成一个结点，以此来满足条件。那咱们通过下面实例来详细了解吧。

以上述插入操作构造的一棵5阶B树（树中最多含有m（m=5）个孩子，因此关键字数最小为ceil(m / 2)-1=2。还是这句话，关键字数小了（小于2个）就合并，大了（超过4个）就分裂）为例，依次删除H,T,R,E。

![8394323_1307525894XPqO.jpg][]

1、首先删除元素H，当然首先查找H，H在一个叶子结点中，且该叶子结点元素数目3大于最小元素数目ceil(m/2)-1=2，则操作很简单，咱们只需要移动K至原来H的位置，移动L至K的位置（也就是结点中删除元素后面的元素向前移动）

![8394323_1307525891j1B1.jpg][]

2、下一步，删除T,因为T没有在叶子结点中，而是在中间结点中找到，咱们发现他的继承者W(字母升序的下个元素)，将W上移到T的位置，然后将原包含W的孩子结点中的W进行删除，这里恰好删除W后，该孩子结点中元素个数大于2，无需进行合并操作。

![8394323_1307525890gB3b.jpg][]

3、下一步删除R，R在叶子结点中,但是该结点中元素数目为2，删除导致只有1个元素，已经小于最小元素数目ceil(5/2)-1=2,而由前面我们已经知道：如果其某个相邻兄弟结点中比较丰满（元素个数大于ceil(5/2)-1=2），则可以向父结点借一个元素，然后将最丰满的相邻兄弟结点中上移最后或最前一个元素到父节点中（有没有看到红黑树中左旋操作的影子?），在这个实例中，右相邻兄弟结点中比较丰满（3个元素大于2），所以先向父节点借一个元素W下移到该叶子结点中，代替原来S的位置，S前移；然后X在相邻右兄弟结点中上移到父结点中，最后在相邻右兄弟结点中删除X，后面元素前移。

![8394323_1307525887QhC3.jpg][]

4、最后一步删除E， 删除后会导致很多问题，因为E所在的结点数目刚好达标，刚好满足最小元素个数（ceil(5/2)-1=2）,而相邻的兄弟结点也是同样的情况，删除一个元素都不能满足条件，所以需要该节点与某相邻兄弟结点进行合并操作；首先移动父结点中的元素（该元素在两个需要合并的两个结点元素之间）下移到其子结点中，然后将这两个结点进行合并成一个结点。所以在该实例中，咱们首先将父节点中的元素D下移到已经删除E而只有F的结点中，然后将含有D和F的结点和含有A,C的相邻兄弟结点进行合并成一个结点。

![8394323_1307525886x2r2.jpg][]

5、也许你认为这样删除操作已经结束了，其实不然，在看看上图，对于这种特殊情况，你立即会发现父节点只包含一个元素G，没达标（因为非根节点包括叶子结点的关键字数n必须满足于2=<n<=4，而此处的n=1），这是不能够接受的。如果这个问题结点的相邻兄弟比较丰满，则可以向父结点借一个元素。假设这时右兄弟结点（含有Q,X）有一个以上的元素（Q右边还有元素），然后咱们将M下移到元素很少的子结点中，将Q上移到M的位置，这时，Q的左子树将变成M的右子树，也就是含有N，P结点被依附在M的右指针上。所以在这个实例中，咱们没有办法去借一个元素，只能与兄弟结点进行合并成一个结点，而根结点中的唯一元素M下移到子结点，这样，树的高度减少一层。

![8394323_1307525883hHW0.jpg][]

为了进一步详细讨论删除的情况，再举另外一个实例：

这里是一棵不同的5序B树，那咱们试着删除C

![8394323_1307525877xDde.jpg][]

于是将删除元素C的右子结点中的D元素上移到C的位置，但是出现上移元素后，只有一个元素的结点的情况。

又因为含有E的结点，其相邻兄弟结点才刚脱贫（最少元素个数为2），不可能向父节点借元素，所以只能进行合并操作，于是这里将含有A,B的左兄弟结点和含有E的结点进行合并成一个结点。

![8394323_13075258778uzj.jpg][]

这样又出现只含有一个元素F结点的情况，这时，其相邻的兄弟结点是丰满的（元素个数为3>最小元素个数2），这样就可以想父结点借元素了，把父结点中的J下移到该结点中，相应的如果结点中J后有元素则前移，然后相邻兄弟结点中的第一个元素（或者最后一个元素）上移到父节点中，后面的元素（或者前面的元素）前移（或者后移）；注意含有K，L的结点以前依附在M的左边，现在变为依附在J的右边。这样每个结点都满足B树结构性质。

![8394323_1307525873GgD4.jpg][]

从以上操作可看出：除根结点之外的结点（包括叶子结点）的关键字的个数n满足：（ceil(m / 2)-1）<= n <= m-1，即2<=n<=4。这也佐证了咱们之前的观点。删除操作完。

在B\_树中关键字分布在整个B\_树，并且在上层结点中出现过的关键字不再出现在最底层的结点中。顺序链中所有的关键字不能连接在一起。

一颗m阶的B+树和m阶的B\_树的差异在于：

1.有n棵子树的结点中含有n个关键字； (而B树是n棵子树有n-1个关键字)

2.所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。(而B树的叶子节点并没有包括全部需要查找的信息)

3.所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)

![8394323_1307440587b6WG.jpg][]

1) B\+\-tree的磁盘读写代价更低

B\+\-tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B\+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B\+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

2) B\+\-tree的查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

# 分析 #

对B树和B+树的分析和对前面讲解的2-3树的分析类似，

对于一颗节点为N度为M的子树，查找和插入需要logM-1N ~ logM/2N次比较。这个很好证明，对于度为M的B树，每一个节点的子节点个数为M/2 到 M-1之间，所以树的高度在logM-1N至logM/2N之间。

这种效率是很高的，对于N=62\*1000000000个节点，如果度为1024，则logM/2N <=4，即在620亿个元素中，如果这棵树的度为1024，则只需要小于4次即可定位到该节点，然后再采用二分查找即可找到要找的值。

# 应用 #

B树和B+广泛应用于文件存储系统以及数据库系统中，在讲解应用之前，我们看一下常见的存储结构：

[![File System][]][File System 1]

我们计算机的主存基本都是随机访问存储器(Random-Access Memory，RAM)，他分为两类：静态随机访问存储器（SRAM）和动态随机访问存储器（DRAM）。SRAM比DRAM快，但是也贵的多，一般作为CPU的高速缓存，DRAM通常作为内存。这类存储器他们的结构和存储原理比较复杂，基本是使用电信号来保存信息的，不存在机器操作，所以访问速度非常快，具体的访问原理可以查看CSAPP，另外，他们是易失的，即如果断电，保存DRAM和SRAM保存的信息就会丢失。

我们使用的更多的是使用磁盘，磁盘能够保存大量的数据，从GB一直到TB级，但是 他的读取速度比较慢，因为涉及到机器操作，读取速度为毫秒级，从DRAM读速度比从磁盘度快10万倍，从SRAM读速度比从磁盘读快100万倍。下面来看下磁盘的结构：

[![Disk geometry][]][Disk geometry 1]

如上图，磁盘由盘片构成,每个盘片有两面，又称为盘面(Surface)，这些盘面覆盖有磁性材料。盘片中央有一个可以旋转的主轴(spindle)，他使得盘片以固定的旋转速率旋转，通常是5400转每分钟(Revolution Per Minute,RPM)或者是7200RPM。磁盘包含一个多多个这样的盘片并封装在一个密封的容器内。上图左，展示了一个典型的磁盘表面结构。每个表面是由一组成为磁道(track)的同心圆组成的，每个磁道被划分为了一组扇区(sector).每个扇区包含相等数量的数据位，通常是（512）子节。扇区之间由一些间隔(gap)隔开,不存储数据。

以上是磁盘的物理结构，现在来看下磁盘的读写操作：

[![Disk dynamic][]][Disk dynamic 1]

如上图，磁盘用读/写头来读写存储在磁性表面的位，而读写头连接到一个传动臂的一端。通过沿着半径轴前后移动传动臂，驱动器可以将读写头定位到任何磁道上，这称之为寻道操作。一旦定位到磁道后，盘片转动，磁道上的每个位经过磁头时，读写磁头就可以感知到位的值，也可以修改值。对磁盘的访问时间分为 寻道时间，旋转时间，以及传送时间。

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，因此为了提高效率，要尽量减少磁盘I/O，减少读写操作。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：

每次新建一个节点的同时，直接申请一个页的空间( 512或者1024)，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。如，将B树的度M设置为1024，这样在前面的例子中，600亿个元素中只需要小于4次查找即可定位到某一存储位置。

同时在B+树中，内节点只存储导航用到的key，并不存储具体值，这样内节点个数较少，能够全部读取到主存中，外接点存储key及值，并且顺序排列，具有良好的空间局部性。所以B及B+树比较适合与文件系统的数据结构。下面是一颗B树，用来进行内容存储。

[![build a large B tree][]][build a large B tree 1]

另外B/B+树也经常用做数据库的索引，这方面推荐您直接看张洋的[MySQL索引背后的数据结构及算法原理][MySQL] 这篇文章，这篇文章对MySQL中的如何使用B+树进行索引有比较详细的介绍，推荐阅读。

# 总结 #

在前面两篇文章介绍了平衡查找树中的[2-3树][2-3]，[红黑树][Link 1]之后，本文介绍了文件系统和数据库系统中常用的B/B+ 树，他通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。他广泛用于文件系统及数据库中，如：

*  Windows：HPFS文件系统
 *  Mac：HFS，HFS+文件系统
 *  Linux：ResiserFS，XFS，Ext3FS，JFS文件系统
 *  数据库：ORACLE，MYSQL，SQLSERVER等中

参考地址：[https://www.cnblogs.com/vincently/p/4526560.html][https_www.cnblogs.com_vincently_p_4526560.html]

如果关于原理不懂的同学可以看看这篇文章：[https://blog.csdn.net/cangchen/article/details/44817807][https_blog.csdn.net_cangchen_article_details_44817807]

对文章有什么疑问或者想要看更多文章可以加我订阅号，欢迎大家的踩踩~

![70][]

[8394323_13074405906V6Q.jpg]: /images/20220525/bb0420bc7f224a3bb5523206f6c85319.png
[8394323_1307525908RHSE.jpg]: /images/20220525/0677c8f2883d46d5ba0dbe273e1254e5.png
[8394323_1307525905BTbZ.jpg]: /images/20220525/cfe5eae651fa438f95bbf2f19eb3e64c.png
[8394323_1307525899vG17.jpg]: /images/20220525/2542f6aa9a8247f1af4cbbbf7ce34bf5.png
[8394323_1307525899h5rR.jpg]: /images/20220525/161a465e4a144a91babb4ab37e10df38.png
[8394323_1307525895Gzrw.jpg]: /images/20220525/ce47a20a9c204c79896088bfb5a6e8ec.png
[8394323_13075258952zo1.jpg]: /images/20220525/79e8bd11f29347abbc6bc4194861c909.png
[8394323_1307525895q8j1.jpg]: /images/20220525/f49e89cae7734b8287ba41a9fd2617c7.png
[8394323_1307525894XPqO.jpg]: /images/20220525/d62d3bab7b23481ab7ca63de5262d4a3.png
[8394323_1307525891j1B1.jpg]: /images/20220525/b344650d613b4c03b0aaae5e5d4f8fa7.png
[8394323_1307525890gB3b.jpg]: /images/20220525/c7d0671a412b43889f9e686214b7736e.png
[8394323_1307525887QhC3.jpg]: /images/20220525/acb4542a0738433ba8d64b7494976d9b.png
[8394323_1307525886x2r2.jpg]: /images/20220525/5861620818f14c3b9c4f9f24b342a7f9.png
[8394323_1307525883hHW0.jpg]: /images/20220525/1cb64335dfe74b84a5a1f85f9b73ddb7.png
[8394323_1307525877xDde.jpg]: /images/20220525/c6e2ff68817d428589fef8fe893be551.png
[8394323_13075258778uzj.jpg]: /images/20220525/fd23cd8bae6e4cac8f066041c6aeeb7e.png
[8394323_1307525873GgD4.jpg]: /images/20220525/ede886e28abc4e9cbccd2d9641a28599.png
[8394323_1307440587b6WG.jpg]: /images/20220525/a2ec867e452e480b81e4bd4f65ade651.png
[File System]: /images/20220525/0a8e489847424d9297a03ccb6ea6f5e5.png
[File System 1]: https://images0.cnblogs.com/blog/94031/201403/290050109225145.png
[Disk geometry]: /images/20220525/98da204efbc643288590859a4ba18a5a.png
[Disk geometry 1]: https://images0.cnblogs.com/blog/94031/201403/290050156091613.png
[Disk dynamic]: /images/20220525/6ca34dd7301246bcba84b29acfd7cd13.png
[Disk dynamic 1]: https://images0.cnblogs.com/blog/94031/201403/290050192666197.png
[build a large B tree]: /images/20220525/53cddc846a224185bfdd6e3bd4fd3831.png
[build a large B tree 1]: https://images0.cnblogs.com/blog/94031/201403/290050241097149.png
[MySQL]: http://blog.codinglabs.org/articles/theory-of-mysql-index.html
[2-3]: http://www.cnblogs.com/yangecnu/p/Introduce-2-3-Search-Tree.html
[Link 1]: http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html
[https_www.cnblogs.com_vincently_p_4526560.html]: https://www.cnblogs.com/vincently/p/4526560.html
[https_blog.csdn.net_cangchen_article_details_44817807]: https://blog.csdn.net/cangchen/article/details/44817807
[70]: /images/20220525/594f923bb6224a78ab219dfe4cbe32c8.png