最小度

概述

最小度 $t$ 是B树的核心参数，控制每个节点的关键字数量范围和分支因子。最小度 $t$ 越大，B树越”矮胖”，高度越低，磁盘I/O次数越少；但单次磁盘读取的数据量也越大。选择合适的 $t$ 是B树工程实现的关键。

定义

最小度

一棵B树的最小度 $t$（minimum degree）是一个整数，满足 $t\ge 2$。它决定了B树节点的关键字数量和子树数量的上下界：

属性	根节点	非根内部节点	叶子节点
最少关键字数	$1$	$t-1$	$0$（不携带信息）
最多关键字数	$2t-1$	$2t-1$	$0$
最少子树数	$2$	$t$	$0$
最多子树数	$2t$	$2t$	$0$

关键字数量范围

对于任意非根节点 $x$，设其关键字数为 $n_x$，则：

$t-1\le n_x\le 2t-1$

对于根节点 $r$（树非空时）：

$1\le n_r\le 2t-1$

子树数量范围

对于任意内部节点 $x$，设其子树数为 $\text{children}(x)$，则：

$\text{children}(x)=n_x+1$

因此：

$t\le \text{children}(x)\le 2t\text{（非根内部节点）}$

$2\le \text{children}(x)\le 2t\text{（根节点）}$

核心性质

1. 最小度与节点”满”的定义

• 一个节点被称为满的（full），当且仅当它恰好包含 $2t-1$ 个关键字
• 满节点无法再插入新关键字，必须通过分裂操作（见B树的插入操作）来处理

2. 最小度与下溢

• 一个非根节点被称为发生下溢（underflow），当且仅当它的关键字数少于 $t-1$
• 下溢必须通过借关键字或合并操作（见B树的删除操作）来修复

3. 最小度与树高度的关系

由B树高度定理，最小度 $t$ 直接决定了B树高度的上界：

$h\le {\log }_t\frac{n+1}{2}$

$t$ 越大，对数底数越大，高度上界越低。

与阶数 $m$ 的关系

在一些教材和工程文献中，B树使用阶数 $m$（order）而非最小度 $t$ 来定义。两者的对应关系为：

$t=\lceil m/2\rceil$

即一棵 $m$ 阶B树等价于最小度 $t=\lceil m/2\rceil$ 的B树。

阶数 $m$	最小度 $t$	最多关键字数 $2t-1$	最多子树数 $2t$
3	2	3	4
4	2	3	4
5	3	5	6
100	50	99	100
200	100	199	200

注意

CLRS采用最小度 $t$ 的定义方式，而部分国内教材采用阶数 $m$ 的定义方式。阅读不同文献时需注意区分，两者本质描述的是同一结构。

最小度的工程选择

在实际数据库系统中，最小度 $t$ 的选择取决于磁盘页大小：

• 磁盘页大小通常为 4KB 或 16KB
• 每个B树节点应恰好填满一个磁盘页
• $t$ 越大 $\Rightarrow$ 树越矮 $\Rightarrow$ I/O次数越少
• 但 $t$ 过大 $\Rightarrow$ 节点内线性搜索变慢

典型值：MySQL InnoDB 使用 16KB 页，每个节点约可存储数百到上千个索引项。

参见

• B树 — 最小度所定义的核心数据结构
• B树高度定理 — 最小度如何决定树的高度上界
• B树节点的磁盘表示 — 最小度与磁盘页大小的工程对应关系