B树与B+树
概述
B树（B-Tree）和B+树（B+ Tree）是**多路平衡查找树**，专为**磁盘存储**设计，能够显著减少磁盘 I/O 次数。它们是现代数据库索引和文件系统的核心数据结构。
核心价值：B树和B+树通过增大节点分支因子（每个节点存储多个关键字），降低树的高度，使得每次查找只需很少的磁盘 I/O 操作。B+树进一步将所有数据存储在叶子节点，并连接成链表，极大优化了范围查询性能。
为什么需要B树？
传统二叉树的问题
二叉搜索树在磁盘存储的问题:
- 树高度大: n个节点高度约 log₂ n
- 每层一个节点: 每次查找需要多次磁盘 I/O
- 节点分散: 无法利用磁盘块预读
示例: 存储 100万 条记录
- 二叉树高度: log₂(1000000) ≈ 20
- 查找需要: 20 次磁盘 I/O
- 假设每次 I/O 10ms: 总时间 200ms
B树的解决方案:
- 多路分支: 每个节点存储多个关键字
- 树高度小: 大幅减少磁盘 I/O 次数
- 节点对齐磁盘块: 一次 I/O 读取整个节点
示例: 100阶 B树存储 100万 条记录
- B树高度: log₁₀₀(1000000) ≈ 3
- 查找需要: 3 次磁盘 I/O
- 总时间: 30ms（提升 6 倍！）
B树特点
B树的定义（m阶B树）
m阶B树的定义:
1. 节点关键字数量:
- 根节点: 1 ~ m-1 个关键字
- 非根非叶子节点: ⌈m/2⌉-1 ~ m-1 个关键字
- 叶子节点: ⌈m/2⌉-1 ~ m-1 个关键字
5. 子树值域:
- 节点关键字 K₁, K₂, ..., Kₖ₋₁
- 子树 P₀ 中的所有值 < K₁
- Kᵢ < 子树 Pᵢ 中的所有值 < Kᵢ₊₁
- Kₖ₋₁ < 子树 Pₖ 中的所有值
B树结构示意
| Text Only |
|---|
| 4阶B树（每个节点最多3个关键字，4个子节点）:
根节点
┌───────────────┐
│ 30 │ 60 │
└───────┬───────┘
┌──────────┼──────────┐
↓ ↓ ↓
┌─────────┐ ┌─────────┐ ┌─────────┐
│10│20 │ │40│50 │ │70│80│90│
└────┬────┘ └────┬────┘ └─────────┘
叶子节点 叶子节点 叶子节点
验证B树性质:
─────────────────────────────────────────────────────────────────
性质 验证 结果
─────────────────────────────────────────────────────────────────
根节点关键字数 2个 (30, 60), 1 ≤ 2 ≤ 3 ✓
非根节点关键字数 2-3个, 1 ≤ 2,3 ≤ 3 ✓
叶子节点同层 都在第3层 ✓
节点内有序 [10,20], [40,50], [70,80,90] ✓
子树值域 左子树值 < 30 < 中子树值 < 60 ✓
< 右子树值 ✓
─────────────────────────────────────────────────────────────────
|
B树节点结构
| Text Only |
|---|
| m = 4 的B树节点结构:
关键字数组: keys[0..m-2] = keys[0..2]
子节点指针: children[0..m-1] = children[0..3]
节点结构:
┌─────────────────────────────────────┐
│ K₁ │ K₂ │ K₃ │ │
└────────┬────────┬────────┬──────────┘
↓ ↓ ↓ ↓
P₀ P₁ P₂ P₃
关键字关系:
- K₁ < K₂ < K₃
- P₀ 中所有 key < K₁
- K₁ < P₁ 中所有 key < K₂
- K₂ < P₂ 中所有 key < K₃
- K₃ < P₃ 中所有 key
实际存储示例:
┌─────────────────────────────────────┐
│ 20 │ 40 │ 60 │ │
└────────┬────────┬────────┬──────────┘
↓ ↓ ↓ ↓
[1-19] [21-39] [41-59] [61-100]
|
B+树特点
B+树与B树的区别
| Text Only |
|---|
| ┌─────────────────────────────────────────────────────────────────────┐
│ B树 vs B+树 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ B树: │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ - 数据存储在所有节点 │ │
│ │ - 查找可能在非叶子节点终止 │ │
│ │ - 叶子节点之间无连接 │ │
│ │ - 范围查询需要中序遍历 │ │
│ └─────────────────────────────────────────────────────────────┘ │
│ │
│ [30|60] ← 数据可能在这里 │
│ / | \ │
│ [10|20] [40|50] [70|80] ← 叶子节点 │
│ │
│ B+树: │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ - 数据只存储在叶子节点 │ │
│ │ - 查找必须到达叶子节点 │ │
│ │ - 叶子节点连接成链表 │ │
│ │ - 范围查询只需遍历叶子链表 │ │
│ └─────────────────────────────────────────────────────────────┘ │
│ │
│ [30|60] ← 只有索引，无数据 │
│ / | \ │
│ [10|20]←→[40|50]←→[70|80] ← 叶子节点存储数据 │
│ 叶子链表连接 │
│ │
└─────────────────────────────────────────────────────────────────────┘
|
B+树节点结构
| Text Only |
|---|
| B+树内部节点（只存索引）:
┌─────────────────────────────────────┐
│ 20 │ 40 │ 60 │ │ ← 索引值
└────────┬────────┬────────┬──────────┘
↓ ↓ ↓ ↓
指向 指向 指向 指向
叶子节点 叶子节点 叶子节点 叶子节点
B+树叶子节点（存数据+指针）:
┌─────────────────────────────────────────────────────────────────┐
│ prev │ 10 │data│ 20 │data│ 30 │data│ ... │ next │ │
└─────────────────────────────────────────────────────────────────┘
↑ ↑
槽向前一个 指向下一个
叶子节点 叶子节点
关键特点:
- 内部节点只存储索引（复制的键值）
- 叶子节点存储实际数据
- 叶子节点通过指针连接成双向链表
|
原理详解
B树的查找
| Text Only |
|---|
| B树查找算法:
目标: 查找关键字 key
步骤:
1. 从根节点开始
2. 在当前节点中找第一个 ≥ key 的关键字位置 i
3. 如果 keys[i] == key，找到，返回
4. 如果是叶子节点，未找到，返回失败
5. 否则，进入 children[i] 子树继续查找
示例: 在 4 阶 B树中查找 50
[30|60]
/ | \
[10|20] [40|50] [70|80|90]
步骤1: 从根节点 [30|60] 开始
50 > 30, 50 < 60, 进入中间子树
步骤2: 进入节点 [40|50]
50 > 40, 50 == 50, 找到！
查找路径: [30|60] → [40|50]
磁盘 I/O: 2 次
|
B树的插入
| Text Only |
|---|
| B树插入算法:
步骤:
1. 找到应该插入的叶子节点
2. 如果叶子节点未满，直接插入
3. 如果叶子节点已满，分裂节点:
a. 将中间关键字上移到父节点
b. 将节点分裂为两个节点
c. 如果父节点也满，递归分裂
示例: 向 4 阶 B树插入 25
初始状态:
[30|60]
/ | \
[10|20] [40|50] [70|80|90]
步骤1: 找到插入位置 - 叶子节点 [10|20]
步骤2: 插入 25，节点变为 [10|20|25]
未超过最大关键字数 3，直接插入
结果:
[30|60]
/ | \
[10|20|25] [40|50] [70|80|90]
─────────────────────────────────────────────────────────────────
示例: 继续插入 5，导致分裂
插入前:
[10|20|25] ← 已满 (3个关键字)
步骤1: 插入 5，节点变为 [5|10|20|25] (临时，超过容量)
步骤2: 分裂
- 中间关键字: 10 (第2个)
- 左节点: [5]
- 右节点: [20|25]
- 10 上移到父节点
分裂后:
[10|30|60] ← 10 上移
/ | | \
[5] [20|25] [40|50] [70|80|90]
|
B树的分裂
| Text Only |
|---|
| 节点分裂过程（m=4，最多3个关键字）:
分裂前（节点已满）:
┌─────────────────────────────────────┐
│ 10 │ 20 │ 30 │ │ ← 3个关键字（已满）
└────────┬────────┬────────┬──────────┘
↓ ↓ ↓ ↓
P₀ P₁ P₂ P₃
插入新关键字 25 后（临时状态）:
┌───────────────────────────────────────────┐
│ 10 │ 20 │ 25 │ 30 │ │ ← 4个关键字（超容量）
└────────┬────────┬────────┬────────┬───────┘
↓ ↓ ↓ ↓ ↓
P₀ P₁ P₂ P₃ P₄
分裂过程:
1. 找中间关键字: mid = keys[m/2] = keys[2] = 20
2. 创建新节点
3. 左节点保留 keys[0..mid-1] = [10]
4. 右节点保留 keys[mid+1..] = [25, 30]
5. 中间关键字上移到父节点
分裂后:
父节点: [... | 20 | ...] ← 中间关键字上移
/ \
左节点: [10] 右节点: [25|30]
/ \ / \ \
P₀ P₁ P₂ P₃ P₄
|
B+树的范围查询
| Text Only |
|---|
| B+树范围查询优势:
查询: 查找 [40, 80] 范围内的所有数据
B树方式:
- 需要中序遍历整棵树
- 访问多个非叶子节点
- 效率较低
[30|60]
/ | \
[10|20] [40|50] [70|80|90]
↑ ↑ ↑
访问 访问 访问
B+树方式:
- 找到范围起点叶子节点
- 沿着叶子链表遍历
- 只访问叶子节点
- 效率极高
[30|60]
/ | \
[10|20]←→[40|50]←→[70|80|90]
↑ 沿链表遍历 →
起点 终点
步骤:
1. 查找起点 40: 到达叶子节点 [40|50]
2. 输出 40, 50
3. 沿 next 指针到 [70|80|90]
4. 输出 70, 80
5. 遇到 90 > 80，停止
结果: [40, 50, 70, 80]
|
可视化演示
B树完整操作演示
| Text Only |
|---|
| 4阶B树操作演示（最多3个关键字）
═══════════════════════════════════════════════════════════════
初始状态: 空树
═══════════════════════════════════════════════════════════════
NULL
═══════════════════════════════════════════════════════════════
插入 10, 20, 30
═══════════════════════════════════════════════════════════════
插入 10: 根节点 [10]
插入 20: 根节点 [10|20]
插入 30: 根节点 [10|20|30] ← 已满
状态:
[10|20|30]
═══════════════════════════════════════════════════════════════
插入 40: 触发分裂
═══════════════════════════════════════════════════════════════
临时状态: [10|20|30|40] (超容量)
分裂:
- 中间关键字 20 上移
- 左节点: [10]
- 右节点: [30|40]
分裂后:
[20]
/ \
[10] [30|40]
═══════════════════════════════════════════════════════════════
插入 5, 15
═══════════════════════════════════════════════════════════════
插入 5: 到左节点 [10]，变为 [5|10]
插入 15: 到左节点 [5|10]，变为 [5|10|15]
状态:
[20]
/ \
[5|10|15] [30|40]
═══════════════════════════════════════════════════════════════
插入 25: 到右节点 [30|40]，变为 [25|30|40]
═══════════════════════════════════════════════════════════════
状态:
[20]
/ \
[5|10|15] [25|30|40]
═══════════════════════════════════════════════════════════════
插入 35: 触发右节点分裂
═══════════════════════════════════════════════════════════════
临时状态: 右节点 [25|30|35|40] (超容量)
分裂:
- 中间关键字 35 上移
- 左节点: [25|30]
- 右节点: [40]
父节点变为 [20|35]
状态:
[20|35]
/ | \
[5|10|15] [25|30] [40]
═══════════════════════════════════════════════════════════════
插入 50, 60, 70
═══════════════════════════════════════════════════════════════
插入 50: [40|50]
插入 60: [40|50|60]
插入 70: 触发分裂
分裂 [40|50|60|70]:
- 中间关键字 60 上移
- 左节点: [40|50]
- 右节点: [70]
父节点变为 [20|35|60] ← 已满
状态:
[20|35|60]
/ | | \
[5|10|15] [25|30] [40|50] [70]
═══════════════════════════════════════════════════════════════
插入 80: 触发多层分裂
═══════════════════════════════════════════════════════════════
插入 80 到 [70]，变为 [70|80]
状态:
[20|35|60]
/ | | \
[5|10|15] [25|30] [40|50] [70|80]
═══════════════════════════════════════════════════════════════
最终B树
═══════════════════════════════════════════════════════════════
[20|35|60]
/ | | \
[5|10|15] [25|30] [40|50] [70|80]
|
B+树结构演示
| Text Only |
|---|
| B+树完整结构（数据只在叶子节点）
═══════════════════════════════════════════════════════════════
B+树结构
═══════════════════════════════════════════════════════════════
第1层（根节点，只有索引）:
[30|60]
/ | \
第2层（中间节点，只有索引）:
[10|20] [40|50] [70|80]
/ \ / \ / \
第3层（叶子节点，存储数据）:
[1|5|10]←→[15|20]←→[30|35|40]←→[45|50]←→[60|65|70]←→[75|80]
↑ 叶子节点双向链表连接 ↑
关键特点:
- 内部节点只存储索引（复制的键值）
- 叶子节点存储实际数据
- 叶子节点通过指针连接
范围查询示例: 查找 [20, 50]
1. 从根节点开始，20 < 30，进入左子树
2. 在 [10|20] 节点，20 == 20，进入右子树
3. 到达叶子节点 [15|20]
4. 输出 20
5. 沿 next 指针遍历: [30|35|40] → [45|50]
6. 输出 30, 35, 40, 45, 50
7. 遇到 > 50 的值，停止
结果: [20, 30, 35, 40, 45, 50]
|
代码实现
B树节点定义
| C |
|---|
| #define M 4 // B树阶数
typedef struct BTreeNode {
int keys[M - 1]; // 关键字数组（最多M-1个）
struct BTreeNode *children[M]; // 子节点指针数组（最多M个）
int keyCount; // 当前关键字数量
int isLeaf; // 是否为叶子节点
} BTreeNode;
// 创建新节点
BTreeNode* createNode(int isLeaf) {
BTreeNode *node = (BTreeNode*)malloc(sizeof(BTreeNode));
node->keyCount = 0;
node->isLeaf = isLeaf;
for (int i = 0; i < M; i++) {
node->children[i] = NULL;
}
return node;
}
|
B树查找操作
| C |
|---|
| // 在节点中查找关键字位置
int findKey(BTreeNode *node, int key) {
int idx = 0;
while (idx < node->keyCount && node->keys[idx] < key) {
idx++;
}
return idx;
}
// B树查找
BTreeNode* search(BTreeNode *root, int key, int *pos) {
if (root == NULL) return NULL;
// 在当前节点找关键字位置
int idx = findKey(root, key);
// 如果找到关键字
if (idx < root->keyCount && root->keys[idx] == key) {
*pos = idx;
return root;
}
// 如果是叶子节点，查找失败
if (root->isLeaf) return NULL;
// 递归查找子树
return search(root->children[idx], key, pos);
}
|
B树分裂节点
| C |
|---|
| // 分裂已满的子节点
void splitChild(BTreeNode *parent, int index) {
BTreeNode *fullChild = parent->children[index];
BTreeNode *newNode = createNode(fullChild->isLeaf);
int mid = M / 2; // 中间位置
newNode->keyCount = mid - 1;
// 复制后半部分关键字到新节点
for (int i = 0; i < mid - 1; i++) {
newNode->keys[i] = fullChild->keys[mid + 1 + i];
}
// 如果不是叶子节点，复制子节点指针
if (!fullChild->isLeaf) {
for (int i = 0; i < mid; i++) {
newNode->children[i] = fullChild->children[mid + 1 + i];
}
}
// 更新原节点关键字数量
fullChild->keyCount = mid - 1;
// 在父节点中插入新子节点指针
for (int i = parent->keyCount; i > index; i--) {
parent->children[i + 1] = parent->children[i];
}
parent->children[index + 1] = newNode;
// 在父节点中插入中间关键字
for (int i = parent->keyCount - 1; i >= index; i--) {
parent->keys[i + 1] = parent->keys[i];
}
parent->keys[index] = fullChild->keys[mid];
parent->keyCount++;
}
|
B树插入操作
| C |
|---|
| // 向非满节点插入关键字
void insertNonFull(BTreeNode *node, int key) {
int i = node->keyCount - 1;
if (node->isLeaf) {
// 叶子节点：直接插入
while (i >= 0 && node->keys[i] > key) {
node->keys[i + 1] = node->keys[i];
i--;
}
node->keys[i + 1] = key;
node->keyCount++;
} else {
// 非叶子节点：找到子树位置
while (i >= 0 && node->keys[i] > key) {
i--;
}
i++;
// 如果子节点已满，先分裂
if (node->children[i]->keyCount == M - 1) {
splitChild(node, i);
if (node->keys[i] < key) {
i++;
}
}
insertNonFull(node->children[i], key);
}
}
// B树插入
BTreeNode* insert(BTreeNode *root, int key) {
if (root == NULL) {
root = createNode(1);
root->keys[0] = key;
root->keyCount = 1;
return root;
}
// 如果根节点已满，需要分裂
if (root->keyCount == M - 1) {
BTreeNode *newRoot = createNode(0);
newRoot->children[0] = root;
splitChild(newRoot, 0);
insertNonFull(newRoot, key);
return newRoot;
}
insertNonFull(root, key);
return root;
}
|
B树遍历
| C |
|---|
| // 中序遍历B树
void traverse(BTreeNode *root) {
if (root == NULL) return;
int i;
for (i = 0; i < root->keyCount; i++) {
if (!root->isLeaf) {
traverse(root->children[i]);
}
printf("%d ", root->keys[i]);
}
if (!root->isLeaf) {
traverse(root->children[i]);
}
}
|
B+树节点定义
| C |
|---|
| typedef struct BPlusTreeNode {
int keys[M]; // 关键字数组
struct BPlusTreeNode *children[M + 1]; // 子节点指针
struct BPlusTreeNode *next; // 叶子节点链表指针
int keyCount; // 当前关键字数量
int isLeaf; // 是否为叶子节点
} BPlusTreeNode;
// 创建B+树节点
BPlusTreeNode* createBPlusNode(int isLeaf) {
BPlusTreeNode *node = (BPlusTreeNode*)malloc(sizeof(BPlusTreeNode));
node->keyCount = 0;
node->isLeaf = isLeaf;
node->next = NULL;
for (int i = 0; i <= M; i++) {
node->children[i] = NULL;
}
return node;
}
|
B+树范围查询
| C |
|---|
| // B+树范围查询
void rangeQuery(BPlusTreeNode *root, int low, int high) {
BPlusTreeNode *leaf = root;
// 找到包含 low 的叶子节点
while (!leaf->isLeaf) {
int i = 0;
while (i < leaf->keyCount && leaf->keys[i] <= low) {
i++;
}
leaf = leaf->children[i];
}
// 沿叶子链表遍历
while (leaf != NULL) {
for (int i = 0; i < leaf->keyCount; i++) {
if (leaf->keys[i] >= low && leaf->keys[i] <= high) {
printf("%d ", leaf->keys[i]);
} else if (leaf->keys[i] > high) {
return; // 超出范围，停止
}
}
leaf = leaf->next; // 移到下一个叶子节点
}
}
|
复杂度分析
时间复杂度
| 操作 |
时间复杂度 |
磁盘I/O |
说明 |
| 查找 |
O(log n) |
O(log_m n) |
从根到叶子的路径 |
| 插入 |
O(log n) |
O(log_m n) |
查找 + 分裂 |
| 删除 |
O(log n) |
O(log_m n) |
查找 + 合并 |
| 范围查询(B+) |
O(k + log n) |
O(log_m n + k) |
k为结果数量 |
| Text Only |
|---|
| 磁盘I/O分析:
B树高度:
h = log_m(n) 其中 m 是阶数，n 是记录数
示例:
- n = 100万条记录
- m = 100（节点大小约4KB，每个关键字8字节）
- h = log₁₀₀(1,000,000) ≈ 3
每次查找需要 3 次磁盘 I/O！
对比二叉树:
- h = log₂(1,000,000) ≈ 20
- 需要 20 次磁盘 I/O
B树优势: 减少 85% 的磁盘 I/O！
|
空间复杂度
- O(n)：存储 n 个记录
- B+树由于索引复用，空间利用率更高
B树 vs B+树详细对比
| Text Only |
|---|
| ┌─────────────────────────────────────────────────────────────────────┐
│ B树 vs B+树 详细对比 │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ 数据存储位置: │
│ ┌─────────────────────┬─────────────────────┐ │
│ │ B树 │ B+树 │ │
│ ├─────────────────────┼─────────────────────┤ │
│ │ 所有节点都可能存储 │ 只有叶子节点存储 │ │
│ │ 数据 │ 数据 │ │
│ └─────────────────────┴─────────────────────┘ │
│ │
│ 查找路径长度: │
│ ┌─────────────────────┬─────────────────────┐ │
│ │ B树 │ B+树 │ │
│ ├─────────────────────┼─────────────────────┤ │
│ │ 可能在非叶子节点终止 │ 必须到达叶子节点 │ │
│ │ 平均稍短 │ 稍长但稳定 │ │
│ └─────────────────────┴─────────────────────┘ │
│ │
│ 范围查询效率: │
│ ┌─────────────────────┬─────────────────────┐ │
│ │ B树 │ B+树 │ │
│ ├─────────────────────┼─────────────────────┤ │
│ │ 需要中序遍历 │ 叶子链表遍历 │ │
│ │ 效率较低 │ 效率极高 │ │
│ │ O(n) 访问内部节点 │ 只访问叶子节点 │ │
│ └─────────────────────┴─────────────────────┘ │
│ │
│ 节点空间利用率: │
│ ┌─────────────────────┬─────────────────────┐ │
│ │ B树 │ B+树 │ │
│ ├─────────────────────┼─────────────────────┤ │
│ │ 内部节点存储数据 │ 内部节点只存索引 │ │
│ │ 分支因子较小 │ 分支因子较大 │ │
│ │ 树较高 │ 树更矮 │ │
│ └─────────────────────┴─────────────────────┘ │
│ │
│ 典型应用: │
│ ┌─────────────────────┬─────────────────────┐ │
│ │ B树 │ B+树 │ │
│ ├─────────────────────┼─────────────────────┤ │
│ │ 文件系统元数据 │ 数据库索引 │ │
│ │ MongoDB │ MySQL InnoDB │ │
│ │ │ PostgreSQL │ │
│ └─────────────────────┴─────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────┘
|
| 特性 |
B树 |
B+树 |
| 数据存储 |
所有节点 |
仅叶子节点 |
| 查找终止位置 |
可能在内部节点 |
必须到叶子节点 |
| 范围查询 |
中序遍历 |
叶子链表遍历 |
| 节点利用率 |
较低（内部存数据） |
较高（内部只存索引） |
| 树高度 |
较高 |
较低 |
| 空间开销 |
较大 |
较小 |
| 查找稳定性 |
不稳定 |
稳定 |
| 适用场景 |
随机查找、文件系统 |
范围查询、数据库 |
数据库索引应用
MySQL InnoDB 索引结构
| Text Only |
|---|
| InnoDB B+树索引:
聚簇索引（主键索引）:
┌─────────────────────────────────────────────────────────────────────┐
│ - 叶子节点存储完整的行数据 │
│ - 数据按主键顺序存储 │
│ - 每张表只有一个聚簇索引 │
└─────────────────────────────────────────────────────────────────────┘
[主键: 30|60]
/ | \
[10|行数据] [40|行数据] [70|行数据]
叶子节点 叶子节点 叶子节点
二级索引（辅助索引）:
┌─────────────────────────────────────────────────────────────────────┐
│ - 叶子节点存储索引列值 + 主键值 │
│ - 查找需要回表（用主键查聚簇索引） │
│ - 每张表可以有多个二级索引 │
└─────────────────────────────────────────────────────────────────────┘
[索引列: 30|60]
/ | \
[10|主键=5] [40|主键=8] [70|主键=9]
叶子节点 叶子节点 叶子节点
查询流程:
SELECT * FROM table WHERE index_col = 40;
1. 在二级索引 B+树中查找 40
2. 获取主键值 8
3. 在聚簇索引 B+树中查找主键 8
4. 返回完整行数据（回表操作）
|
索引优化示例
| SQL |
|---|
| -- 创建索引
CREATE INDEX idx_name ON employees(name);
CREATE INDEX idx_dept_salary ON employees(dept_id, salary); -- 联合索引
-- 利用索引的查询
SELECT * FROM employees WHERE name = 'John'; -- 使用 idx_name
-- 联合索引（最左前缀原则）
SELECT * FROM employees WHERE dept_id = 10; -- 使用 idx_dept_salary
SELECT * FROM employees WHERE dept_id = 10 AND salary > 5000; -- 使用 idx_dept_salary
SELECT * FROM employees WHERE salary > 5000; -- 不使用 idx_dept_salary（违反最左前缀）
-- 范围查询（B+树叶子链表遍历）
SELECT * FROM employees WHERE salary BETWEEN 5000 AND 10000;
|
联合索引结构
| Text Only |
|---|
| 联合索引 (dept_id, salary):
B+树结构（按 (dept_id, salary) 排序）:
[(10, 5000) | (20, 3000)]
/ \
[(5, 1000) | (8, 2000) | (10, 3000)] [(15, 4000) | (20, 5000)]
叶子节点 叶子节点
排序规则:
先按 dept_id 排序，dept_id 相同再按 salary 排序
最左前缀原则:
- WHERE dept_id = 10: 使用索引 ✓
- WHERE dept_id = 10 AND salary > 5000: 使用索引 ✓
- WHERE salary > 5000: 不使用索引 ✗
- WHERE dept_id > 10 AND salary > 5000: 部分使用（只用于 dept_id）
|
性能优化
节点大小选择
| Text Only |
|---|
| 节点大小设计原则:
目标: 一次磁盘 I/O 读取整个节点
计算:
- 磁盘块大小: 通常 4KB 或 8KB
- 每个关键字大小: 假设 8 字节（64位整数）
- 每个子节点指针: 8 字节
节点大小 ≈ (关键字数量 × 关键字大小) + (子节点数量 × 指针大小)
= (m-1) × 8 + m × 8
= 16m - 8 字节
如果磁盘块 4KB:
16m - 8 ≤ 4096
m ≤ 256
所以阶数 m 可以设为 200-256，每个节点存储约 200 个关键字！
这意味着:
- 树高度极低: log₂₅₆(1,000,000) ≈ 2.5
- 查找只需 2-3 次磁盘 I/O
|
缓冲区管理
| C |
|---|
| typedef struct {
BTreeNode *node; // 节点指针
int isDirty; // 是否被修改
time_t lastAccess; // 最后访问时间
int nodeId; // 节点ID（磁盘位置）
} BufferSlot;
BufferSlot buffer[BUFFER_SIZE]; // 缓冲池
// 读取节点（带缓冲）
BTreeNode* readNode(int nodeId) {
// 检查缓冲池
if (inBuffer(nodeId)) {
updateAccessTime(nodeId); // 更新访问时间
return getFromBuffer(nodeId);
}
// 缓冲池满，淘汰
if (bufferFull()) {
evictLRU(); // 淘汰最近最少使用
}
// 从磁盘读取
BTreeNode *node = readFromDisk(nodeId);
addToBuffer(nodeId, node);
return node;
}
// LRU 淘汰策略
void evictLRU() {
int oldest = findOldestAccess();
if (buffer[oldest].isDirty) {
writeToDisk(buffer[oldest].node); // 写回脏页
}
removeFromBuffer(oldest);
}
|
应用场景
1. 数据库索引
| Text Only |
|---|
| 主流数据库 B+树索引:
MySQL InnoDB:
- 聚簇索引: 叶子存储行数据
- 二级索引: 叶子存储主键值
PostgreSQL:
- B-tree 索引: 标准 B+树实现
- 支持唯一索引、部分索引
Oracle:
- B-tree 索引: 类似 B+树
- 位图索引: 用于低基数列
SQL Server:
- 聚集索引: 类似 InnoDB 聚簇索引
- 非聚集索引: 二级索引
|
2. 文件系统
| Text Only |
|---|
| 文件系统 B树应用:
NTFS (Windows):
- MFT (Master File Table) 使用 B+树
- 目录索引使用 B+树
ext4 (Linux):
- Htree 目录索引
- 使用类似 B树的结构
HFS+ (macOS):
- 目录文件使用 B树
- 属性文件使用 B树
作用:
- 快速查找文件
- 高效目录遍历
- 支持大目录
|
3. 键值存储
| Text Only |
|---|
| 键值存储引擎:
LevelDB / RocksDB:
- 使用 LSM-Tree (Log-Structured Merge Tree)
- 但内部排序使用类似 B树的机制
Berkeley DB:
- Btree 访问方法
- 支持事务、并发
WiredTiger (MongoDB 存储引擎):
- B+树作为底层索引结构
- 支持压缩、检查点
|
4. 搜索引擎
| Text Only |
|---|
| 搜索引擎倒排索引:
倒排索引结构:
词项 → 文档ID列表
使用 B+树存储词项索引:
- 词项按字典序排列
- 叶子节点存储词项 + 倒排列表指针
- 范围查询: 前缀匹配、范围词项
示例:
B+树叶子节点:
┌─────────────────────────────────────────────────────────────────┐
│ "apple" → [doc1, doc5, doc10] │
│ "apply" → [doc2, doc8] │
│ "banana" → [doc3, doc7] │
└─────────────────────────────────────────────────────────────────┘
前缀查询 "app%":
1. 查找 "app" 位置
2. 沿叶子链表遍历
3. 返回所有 "app" 开头的词项
|
参考资料
- 《算法导论》第18章 - B树
- 《数据库系统概念》第11章 - 索引与散列
- MySQL 技术内幕：InnoDB 存储引擎
- PostgreSQL B-tree 索引实现文档
- "The Ubiquitous B-Tree" - Comer (1979)