数据结构和算法分析：B树 B+树和B*树的总结

曾经终败给现在 2022-05-14 18:35 155阅读 0赞

# 1. 前言 #

动态查找树主要有：二叉查找树（Binary Search Tree），平衡二叉查找树（Balanced Binary Search Tree），红黑树(Red-Black Tree )，B-tree/B±tree/ B\*-tree (B~Tree)。前三者是典型的二叉查找树结构，其查找的时间复杂度O(log2N)与树的深度相关，那么降低树的深度自然会提高查找效率。

但是咱们有面对这样一个实际问题：就是大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构**由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下**。那么如何减少树的深度（当然是不能减少查询的数据量），一个基本的想法就是：采用多叉树结构（由于树节点元素数量是有限的，自然该节点的子树数量也就是有限的）。

# 2. B树 #

B-tree树（B是Balanced的意思，多路查找树）。B树被设计成平衡多路查找二叉树，它的各种操作能使B树保持较低的高度，从而达到有效避免磁盘过于频繁的查找存取操作，从而有效提高查找效率。

## 2.1 B树的定义 ##

B 树又叫平衡多路查找树。一棵m阶的B 树，满足的特性如下：

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。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_27_color_FFFFFF_t_70]

## 2.2 B树的类型和节点定义 ##

B树的类型和节点定义如下所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_27_color_FFFFFF_t_70 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_27_color_FFFFFF_t_70 2]

B树的关键字分布在整个树中，叶子节点不包含任何关键字信息。非叶子节点包括关键字的信息，以及子树指针向量和关键字表示的相应的数据项。

# 3. B+树 #

B+ 树是一种树数据结构，是一个n叉排序树，每个节点通常有多个孩子，一棵B+树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。

B+ 树通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入。

## 3.1 B+树的定义 ##

B+树是应文件系统所需而出的一种B树的变型树。一棵m阶的B+树和m阶的B-树的差异在于：

1.  有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。
2.  所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.  所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_27_color_FFFFFF_t_70 3]

a) 为什么说B+tree比B 树更适合实际应用中操作系统的文件索引和数据库索引？

1.  B+tree的磁盘读写代价更低

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

1.  B+tree的查询效率更加稳定

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

# 4. B\*树 #

B\*-tree是B±tree的变体，在B+树的基础上(所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针)，B树中非根和非叶子节点再增加指向兄弟的指针；B\*树定义了非叶子结点关键字个数至少为(2/3)\*M，即块的最低使用率为2/3（代替B+树的1/2）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_27_color_FFFFFF_t_70 4]

B\*树分配新结点的概率比B+树要低，空间使用率更高；

# 5. B树和B+树的区别和比较 #

**结构上**

*  B树中关键字集合分布在整棵树中，叶节点中不包含任何关键字信息，而B+树关键字集合分布在叶子结点中，非叶节点只是叶子结点中关键字的索引；
 *  B树中任何一个关键字只出现在一个结点中，而B+树中的关键字必须出现在叶节点中，也可能在非叶结点中重复出现；

**性能上**（也即为什么说B+树比B树更适合实际应用中操作系统的文件索引和数据库索引？）

*  不同于B树只适合随机检索，B+树同时支持**随机检索**和**顺序检索**；
 *  B+树的磁盘读写代价更低。**B+树的内部结点并没有指向关键字具体信息的指针**，其内部结点比B树小，盘块能容纳的结点中关键字数量更多，一次性读入内存中可以查找的关键字也就越多，相对的，IO读写次数也就降低了。而IO读写次数是影响索引检索效率的最大因素。
 *  B+树的查询效率更加稳定。B树搜索有可能会在非叶子结点结束，越靠近根节点的记录查找时间越短，只要找到关键字即可确定记录的存在，其性能等价于在关键字全集内做一次二分查找。而在B+树中，顺序检索比较明显，随机检索时，任何关键字的查找都必须走一条从根节点到叶节点的路，所有关键字的查找路径长度相同，导致每一个关键字的查询效率相当。
 *  （数据库索引采用B+树的主要原因是，）B-树在提高了磁盘IO性能的同时并没有**解决元素遍历的效率低下**的问题。B+树的叶子节点使用指针顺序连接在一起，**只要遍历叶子节点就可以实现整棵树的遍历**。而且**在数据库中基于范围的查询是非常频繁的**，而B树不支持这样的操作（或者说效率太低）。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_27_color_FFFFFF_t_70]: /images/20220503/339cd165fc6f4a2ea1ae9a817a338b3a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_27_color_FFFFFF_t_70 1]: /images/20220503/6ff59d483929498e802ce2798308880b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_27_color_FFFFFF_t_70 2]: /images/20220503/e922ce94c32b4f38a5d19d19169c5580.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_27_color_FFFFFF_t_70 3]: /images/20220503/283688c6638f4711b343fddce8e3034d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_27_color_FFFFFF_t_70 4]: /images/20220503/cdfd0a7a9beb4ecdb6f49d48500214b2.png