深入探究 B 树、B + 树、B * 树：数据结构的平衡与高效

创作时间:

作者:

@小白创作中心

深入探究 B 树、B + 树、B * 树：数据结构的平衡与高效

引用

CSDN

https://blog.csdn.net/qq_51626216/article/details/145857566

在数据结构的庞大体系中，B 树及其变体 B + 树、B * 树占据着举足轻重的地位，尤其是在大规模数据存储和检索场景中，它们凭借独特的结构和性质发挥着关键作用。今天，就让我们深入探索这三种数据结构的奥秘。

一、B 树：多路平衡查找树的基石

1. 结构特点

B 树是一种自平衡的多路搜索树。其每个节点包含多个键值对以及指向子节点的指针。具体来说，对于一个 m 阶的 B 树（m 被称为 B 树的阶数，它表示一个节点最多能包含的子树个数），有以下关键特性：

每个非叶子节点至少有个键，最多有个键。
每个非叶子节点的子树数量比键的数量多 1。
所有叶子节点都在同一层，且叶子节点不包含指向子节点的指针。

例如，在一个 5 阶 B 树中，每个非叶子节点最少有 2 个键，最多有 4 个键，相应地，子树数量最少 3 个，最多 5 个。这种结构设计使得 B 树在保持平衡的同时，能够高效地存储和检索数据。

2. 操作原理

查找：从根节点开始，通过比较键值确定要访问的子节点，递归地进行查找，直到找到目标键或到达叶子节点（未找到）。
插入：新键总是插入到叶子节点。若叶子节点已满（键的数量达到上限），则进行节点分裂，将中间键提升到父节点，原节点分裂为两个。如果父节点也因此满了，继续向上分裂，直到根节点。
删除：从叶子节点删除键。若删除后叶子节点键数过少（小于下限），则尝试从兄弟节点借键；若兄弟节点也无法借键，则与兄弟节点合并，同时调整父节点的键和指针。

3. 应用场景

B 树常用于数据库索引和文件系统元数据管理。在数据库中，由于其能够减少磁盘 I/O 操作（一次 I/O 操作读取一个节点的数据），对于单个数据的精确查找性能表现出色。例如，在关系型数据库中，根据主键查找某条记录时，B 树索引可以快速定位到目标数据所在的磁盘块。

二、B + 树：B 树的进化，范围查询的利器

1. 结构特点

B + 树是 B 树的一种变体，它在 B 树的基础上进行了优化，以适应更复杂的查询需求。B + 树的结构特点如下：

所有数据都存储在叶子节点，非叶子节点仅存储键，用于索引。
叶子节点之间通过双向链表连接，形成一个有序的序列。

2. 操作原理

查找：与 B 树类似，从根节点开始向下查找，但必须到达叶子节点才能找到目标数据。
插入：新键插入到叶子节点，若叶子节点满了，进行分裂，将一半的键和数据移到新的叶子节点，并在父节点添加新叶子节点的最小键作为索引。如果父节点也满了，继续向上分裂。
删除：从叶子节点删除键，若删除后叶子节点键数过少，尝试从兄弟节点借键或与兄弟节点合并，并相应调整父节点的索引。

3. 应用场景

B + 树在数据库中应用极为广泛，尤其适用于范围查询。例如，在 SQL 查询中，当使用
WHERE column BETWEEN value1 AND value2
这样的条件时，B + 树可以通过叶子节点的链表结构，快速定位到范围内的所有数据，大大提高查询效率。同时，由于其插入和删除操作主要集中在叶子节点，对于频繁更新的数据也能很好地适应，如电商平台的订单表。