【数据结构】B树、B+树的知识点学习总结

目录

1、B树

1.1 定义

1.2 特性

1.3 查找操作

1.4 插入操作

1.5 删除操作 

2、B+树

2.1 定义 

2.2 特性

3、B树与B+树的对比

---

1、B树

1.1 定义

        B树是一种平衡树数据结构，用于存储和访问大量数据。B树的每个节点可以存储多个键值，节点中的键值按照大小顺序排列。B树的特点是具有多个关键字，且每个节点中关键字的数目通常介于m/2和m之间，其中m称为B树的阶数。B树的根节点至少有两个子节点，且每个非根节点至少有m/2个子节点。所有叶子节点都在同一层，即具有相同的深度，从而保证B树的平衡性。B树被广泛应用于文件系统、数据库索引和其他数据存储领域中。

1.2 特性

B树是一种自平衡的数据结构，主要特点包括：

1. B树是一种多路搜索树，每个节点可以拥有多个子节点。
2. B树的每个节点最多可以包含m个孩子（子节点），其中m>=2。这也就意味着B树的高度相对较小。
3. B树的每个节点都可以包含多个关键字，且关键字按照升序排列。这也就保证了B树的查找效率。
4. B树的所有叶子节点都位于同一层。这也就保证了B树的平衡性。
5. B树的插入、删除、查找操作都具有较好的平均时间复杂度，通常为O(logn)。

1.3 查找操作

        B树查找是一种常见的数据结构，用于快速查找一个键值对应的值。B树是一种平衡树，能够有效地支持数据的插入、删除和查找操作。与二叉查找树不同，B树每个节点可以拥有多个子节点，从而可以存储更多的数据。

B树的查找操作可以分为以下几步：

1. 从根节点开始，依次比较键值和每个节点中的键值，找到一个最合适的子节点。
2. 如果该子节点是叶子节点，则根据键值找到相应的值并返回。
3. 如果该子节点不是叶子节点，则重复第1步直到找到叶子节点或者遍历完整棵树。

        由于B树的节点通常比较大，所以通常需要从磁盘中读取数据，而不是从内存中读取。因此，B树的查找过程通常需要进行磁盘访问，而磁盘访问的速度通常比内存访问慢得多。为了减少磁盘访问的次数，B树通常具有较小的高度，每个节点存储更多的关键字，同时尽可能保持节点的平衡性。

1.4 插入操作

B树的插入操作包括两个步骤：

1.找到要插入的位置：

        首先，需要遍历B树找到插入位置。在遍历过程中，比较当前结点的关键字和插入关键字的大小，如果插入关键字小于当前结点的最小关键字，就继续往左子树遍历；如果插入关键字大于当前结点的最大关键字，就继续往右子树遍历；如果插入关键字在当前结点的关键字范围内，就说明插入位置就在当前结点，直接向该结点插入关键字即可。

2.插入新结点：

        插入新关键字的方法和二叉搜索树类似，将新插入结点的关键字和指针插入到对应位置。如果插入该关键字后，该结点的关键字个数超过了B树的阶数，就需要进行分裂操作。分裂的方法是将该结点分成两个子结点，并将中间的关键字提升到父结点。如果父结点的关键字个数超过了B树的阶数，就需要继续分裂父结点，直到所有父结点的关键字个数都不超过B树的阶数。

1.5 删除操作 

B树的删除操作包含以下步骤：

1. 在B树中搜索需要删除的关键字K。

2. 如果K位于叶子节点上，直接删除K，然后进行必要的调整，使树仍然满足B树的性质。如果K不在叶子节点上，则转到步骤3。

3. 如果K位于非叶子节点上，则找到其后继节点S。S一定在K的右子树中，并且是右子树中关键字最小的节点。将S的关键字复制到K中，并将S删除。

4. 如果S的子树中的节点数小于B树的最小度数，则需要进行必要的操作来保证树仍然满足B树的性质。这些操作可能包括以下三种情况：

   1. 如果S的右兄弟节点有足够的子节点，则将S的一个关键字移到K的位置上，并将S的右兄弟节点的一个关键字移到S的位置上。
   2. 如果S的左兄弟节点有足够的子节点，则将S的一个关键字移到K的位置上，并将S的左兄弟节点的一个关键字移到S的位置上。
   3. 如果S的左兄弟节点和右兄弟节点都只有最小的子节点数，则将S与其左或右兄弟节点合并，并将K的一个关键字移到新节点中以保证树仍然满足B树的性质。

5. 重复步骤3和4，直到K被删除，并树仍然满足B树的性质。

2、B+树

2.1 定义 

        B+树是一种数据结构，属于B树的一种特殊形式。B+树的每个节点通常包含多个关键字，每个关键字对应一个指针指向子树节点。B+树通常被用来实现关系数据库的索引，因为B+树的叶节点包含了所有的数据，可以支持快速的范围查询操作。

2.2 特性

B+树的特点如下：

1. 所有关键字都在叶节点中出现，且叶节点按关键字大小排序；
2. 非叶节点存储的仅是其子节点的最大/小关键字值，而不是真正的数据；
3. 所有叶节点都有一个指向相邻叶节点的指针，因此可以支持区间查找等操作；
4. B+树的高度通常比B树低，因为非叶节点存储的是子节点的最大/小关键字值，可以减少树高度，提高查询效率。

 

3、B树与B+树的对比

B树和B+树都是常见的数据结构，用于实现关系型数据库中的索引。它们有以下主要区别：

1. 结构不同：B树的每个节点既可以存储数据，又可以存储下级节点的指针；而B+树的所有数据都只存储在叶子节点上，同时内部节点只存储指向叶子节点的指针。

2. 特性不同：B树的所有节点都可以用于查询，而B+树只有叶子节点存储数据，内部节点只用于索引。因此，在进行范围查询的时候，B+树更加适合，因为只需要遍历叶子节点即可。

3. 存储性质不同：由于B+树所有数据都存储在叶子节点上，因此，它具有更加顺序存储的特点，可以提高磁盘预读取的效率。而B树的数据分散在各个节点上，因此存储效率不如B+树。

4. 指针数量不同：B+树每个节点存储的指针数量比B树少，因为B+树的节点只存储指向叶子节点的指针。

综上，B树适用于随机查询，而B+树适用于范围查询；B树指针较多，存储不太紧凑，而B+树指针少，存储更加顺序。