多路查找树：B树与B+树详解

一、B树定义

B树是一种自平衡的多路查找树，广泛应用于数据库和文件系统的索引结构。2-3树和2-3-4树可视为B树的特殊形式。B树的阶数定义为其节点所能拥有的最大子节点数，例如，2-3树是3阶B树，而2-3-4树则是4阶B树。

m阶B树的特点

• 每个节点最多拥有m个子节点。


• 除了根节点和叶节点外，其他每个节点至少有m/2个子节点。


• 根节点至少有两个子节点（除非整个B树仅由一个节点构成）。


• 所有的叶节点都位于同一层。


• 具有k个关键字的非叶节点恰好有k+1个子节点。


• 节点内部结构为P0, K1, P1, K2, P2, ..., Pn-1, Kn, Pn，其中P代表指向子节点的指针，Ki大于Pi指向的所有子节点中的关键字且小于Pi+1指向的所有子节点中的关键字。

t度B树的定义

t度B树是指满足以下条件的平衡多叉树：

• 每个节点最多包含2t-1个关键字；除根节点外，每个节点至少有t-1个关键字（t≥2），根节点至少有一个关键字。


• 节点内的关键字按非降序排列。


• 每个节点的关键字对其子树的范围进行分割。


• 所有叶子节点位于同一层次，确保了B树的平衡性。

二、B树的应用场景

B树设计用于内外存之间的高效数据交换。当数据量庞大，无法一次性加载到内存时，通过调整B树的阶数以适应磁盘存储页的大小，可以显著提高数据检索效率。例如，一棵1001阶的B树，高度为2时，能够存储超过10亿个关键字，只需两次磁盘访问即可完成大部分查询操作。

三、B树的性能分析

对于包含n个关键字的m阶B树，最坏情况下查找所需的最大层数可以通过公式计算得出。具体而言，从根节点到叶节点的路径长度不会超过log_((m/2))((n+1)/2)，这表明即使在最坏情况下，B树也能保持较高的查询效率。