【数据结构】B树家族详解：B树、B+树、B*

一、B树（B-Tree）

1. 定义

B树是一种平衡多路查找树，自平衡的树，能够保持数据有序，设计目标是为减少磁盘I/O次数。适用于需要频繁读写磁盘的场景（如数据库、文件系统）。

2、B树基本性质

节点键值数量限制：

对于 m 阶 B 树，根节点至少有 1 个键值，最多有 m - 1 个键值；非根非叶子节点至少有⌈m/2⌉ - 1 个键值，最多有 m - 1 个键值。比如 5 阶 B 树，根节点最少有 1 个键值，最多 4 个；非根非叶子节点最少有 2 个键值，最多 4 个。这种限制保证了 B 树在数据增加或减少时，通过节点的分裂与合并来维持树的平衡和结构稳定性。

子树数量与键值关系：

每个节点的子树数量等于键值数量加 1。例如一个包含 3 个键值的节点，必然有 4 个子树。每个子树包含的键值范围由该节点的键值界定，左边子树的所有键值小于该节点的第一个键值，中间子树的键值介于相邻两个键值之间，右边子树的键值大于该节点的最后一个键值。

所有叶子节点在同一层：

这是 B 树保持平衡的重要特征。无论数据如何插入或删除，B 树通过一系列操作，如节点分裂、合并和键值转移，保证所有叶子节点处于同一层次。这使得 B 树在进行查询操作时，查找路径的长度基本一致，从而保证查询效率的稳定性，时间复杂度稳定在 O (log n)，n 为节点数。

3、B树特点

数据分布：

B 树的数据既可以存储在叶子节点，也可以存储在非叶子节点。在某些查询场景下，可能需要在非叶子节点和叶子节点之间多次查找才能获取完整数据。

平衡特性：

B 树同样是自平衡的，通过插入和删除操作时的节点分裂与合并，保证树的高度相对平衡，使得查询操作的时间复杂度稳定在 O (log n)，其中 n 为节点数。这确保了无论数据量大小，B 树都能保持较好的查询性能。

多路查找：