算法导论第十四章 B树与B+树：海量数据的守护者

第十四章 B树与B+树：海量数据的守护者

“数据不是信息，信息不是知识，知识不是理解。” —— Clifford Stoll
在信息爆炸的时代，我们需要高效管理海量数据的能力。B树家族作为数据库和文件系统的基石，完美平衡了磁盘I/O效率和内存利用率，成为处理大规模数据的首选数据结构。

14.1 B树的诞生背景

14.1.1 磁盘与内存的速度鸿沟

现代计算机系统中，磁盘访问速度比内存慢10万倍以上。当数据量超过内存容量时，传统二叉搜索树因树高过大导致磁盘I/O次数激增：

数据结构	100万数据树高	磁盘I/O次数
二叉搜索树	~20层	20次
AVL树	~18层	18次
B树(t=100)	2-3层	2-3次

14.1.2 B树的设计哲学

1970年，Rudolf Bayer和Edward M. McCreight发明了B树，核心思想是：

1. 增大节点容量：每个节点存储多个键值
2. 降低树高：通过多路分支减少磁盘访问
3. 平衡操作：节点分裂与合并保持平衡

14.2 B树的定义与性质

14.2.1 形式化定义

一棵B树T是具有以下性质的有根树：

1. 每个节点x包含：
   • n[x]：当前存储的键数
   • key₁[x] ≤ key₂[x] ≤ … ≤ keyₙ[x]：有序键值
   • leaf[x]：布尔值，指示是否为叶节点
2. 内部节点包含n[x]+1个指针c₁[x], c₂[x], …, cₙ₊₁[x]指向子节点
3. 键值分隔子树范围：∀k ∈ subtree(cᵢ[x]), keyᵢ₋₁[x] ≤ k ≤ keyᵢ[x]
4. 所有叶节点深度相同
5. 节点键数限制：
   • 根节点：至少1个键（除非树为空）
   • 其他节点：t-1 ≤ n ≤ 2t-1（t为最小度数）

#define B_TREE_MIN_DEGREE 3
#define MAX_KEYS (2 * B_TREE_MIN_DEGREE - 1)
#define MIN_KEYS (B_TREE_MIN_DEGREE - 1)
#define MAX_CHILDREN (2 * B_TREE_MIN_DEGREE)typedef struct BTreeNode {int n;                          // 当前键数int keys[MAX_KEYS];             // 键数组struct BTreeNode *children[MAX_CHILDREN]; // 子节点指针bool is_leaf;                   // 是否为叶节点
} BTreeNode;typedef struct {BTreeNode *root;int t; // 最小度数
} BTree;

14.2.2 B树可视化示例(t=2)

14.3 B树的核心操作

14.3.1 搜索操作

B树搜索是二叉搜索树的多路推广：

BTreeNode* b_tree_search(BTreeNode *node, int key) {int i = 0;while (i < node->n && key > node->keys[i]) i++;if (i < node->n && key == node->keys[i])return node;if (node->is_leaf)return NULL;// 从磁盘读取子节点return b_tree_search(node->children[i], key);
}

搜索路径示例：在t=3的B树中查找38

根节点: [20, 40, 60] → 选择第2子树(20<38≤40)
子节点: [30, 35, 38] → 找到键38

14.3.2 插入操作

插入操作需要防止节点溢出（>2t-1键），通过分裂和提升保持平衡：

节点分裂实现

void b_tree_split_child(BTree *tree, BTreeNode *parent, int index) {BTreeNode *full_child = parent->children[index];BTreeNode *new_child = b_tree_create_node(full_child->is_leaf);// 新节点获取后半部分键new_child->n = tree->t - 1;for (int j = 0; j < tree->t - 1; j++) {new_child->keys[j] = full_child->keys[j + tree->t];}// 若非叶节点，复制子指针if (!full_child->is_leaf) {for (int j = 0; j < tree->t; j++) {new_child->children[j] = full_child->children[j + tree->t];}}full_child->n = tree->t - 1;// 调整父节点for (int j = parent->n; j >= index + 1; j--) {parent->children[j + 1] = parent->children[j];}parent->children[index + 1] = new_child;for (int j = parent->n - 1; j >= index; j--) {parent->keys[j + 1] = parent->keys[j];}parent->keys[index] = full_child->keys[tree->t - 1];parent->n++;
}

14.3.3 删除操作

删除需要防止节点下溢（<t-1键），通过借键、合并和重分布保持平衡：

合并节点实现

void b_tree_merge(BTree *tree, BTreeNode *node, int index) {BTreeNode *child = node->children[index];BTreeNode *sibling = node->children[index + 1];// 将父节点键下移child->keys[tree->t - 1] = node->keys[index];// 复制兄弟键for (int i = 0; i < sibling->n; i++) {child->keys[i + tree->t] = sibling->keys[i];}// 复制兄弟子指针if (!child->is_leaf) {for (int i = 0; i <= sibling->n; i++) {child->children[i + tree->t] = sibling->children[i];}}// 调整父节点for (int i = index + 1; i < node->n; i++) {node->keys[i - 1] = node->keys[i];}for (int i = index + 2; i <= node->n; i++) {node->children[i - 1] = node->children[i];}child->n += sibling->n + 1;node->n--;free(sibling);
}

14.4 B树的性能分析

14.4.1 空间利用率

最小度数t	最小填充率	最大填充率
2	50%	100%
4	62.5%	87.5%
10	81.8%	90.9%
100	98.0%	99.0%

14.4.2 树高与I/O次数

对于包含n个键、最小度数为t的B树：

• 最小高度：$h_{min}=\lceil {\log }_t(n+1)\rceil -1$
• 最大高度：$h_{max}=\lfloor {\log }_t\frac{n+1}{2}\rfloor$

磁盘I/O次数：操作复杂度 $O(h)=O({\log }_{t}n)$

14.5 B+树：数据库的引擎

14.5.1 B+树与B树的区别

特性	B树	B+树
数据存储	所有节点存储数据	仅叶节点存储数据
键重复	无重复	内部节点键重复
叶节点链接	无链接	叶节点形成双向链表
查找性能	不稳定	稳定(O(log n))
范围查询	低效	高效
空间利用率	较低	更高

14.5.2 B+树节点结构

typedef struct BPlusTreeNode {int n;int keys[MAX_KEYS];union {struct BPlusTreeNode *children[MAX_CHILDREN]; // 内部节点使用struct {void *data_ptrs[MAX_KEYS]; // 叶节点使用struct BPlusTreeNode *next; // 下一个叶节点struct BPlusTreeNode *prev; // 上一个叶节点};};bool is_leaf;
} BPlusTreeNode;

14.5.3 B+树范围查询

void b_plus_tree_range_query(BPlusTree *tree, int start, int end) {BPlusTreeNode *start_node = b_plus_tree_find_leaf(tree, start);BPlusTreeNode *current = start_node;int index = 0;while (current) {// 找到当前节点中≥start的键while (index < current->n && current->keys[index] < start)index++;// 遍历当前节点while (index < current->n && current->keys[index] <= end) {printf("键: %d, 数据地址: %p\n", current->keys[index], current->data_ptrs[index]);index++;}if (index >= current->n) {current = current->next; // 跳转到下一个叶节点index = 0;} else {break;}}
}

14.6 B树在数据库中的应用

14.6.1 数据库索引结构

14.6.2 InnoDB存储引擎

MySQL的InnoDB使用B+树组织数据：

• 聚簇索引：主键索引，叶节点包含完整行数据
• 二级索引：辅助索引，叶节点存储主键值

// InnoDB索引项结构
typedef struct {uint32_t page_no;   // 页号uint16_t page_offset; // 页内偏移uint8_t record_type; // 记录类型uint8_t info_bits;   // 信息位uint16_t n_fields;   // 字段数// 字段数据...
} innodb_index_entry;

14.6.3 索引优化实践

1. 覆盖索引：索引包含查询所需所有字段
2. 前缀索引：对字符串前N字符建立索引
3. 索引下推：在存储引擎层过滤数据
4. MRR优化：Multi-Range Read顺序访问磁盘

14.7 B树在文件系统中的应用

14.7.1 现代文件系统对比

文件系统	索引结构	最大文件大小	特点
NTFS	B+树	16EB	Windows主流
ext4	H树(B+树变种)	1EB	Linux主流
XFS	B+树	8EB	高性能
Btrfs	B树	16EB	写时复制

14.7.2 ext4文件系统目录索引

// ext4目录项结构
struct ext4_dir_entry {__le32 inode;         // Inode号__le16 rec_len;       // 目录项长度__le16 name_len;      // 文件名长度char name[EXT4_NAME_LEN]; // 文件名
};// 目录索引节点
struct dx_root {struct dx_countlimit countlimit; // 限制信息struct dx_entry entries[];       // 索引项
};

14.8 完整B+树实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>#define ORDER 4
#define MAX_KEYS (ORDER - 1)
#define MIN_KEYS (ORDER / 2 - 1)typedef struct BPlusTreeNode {int keys[MAX_KEYS + 1]; // 多出一个用于临时存储void *pointers[ORDER + 1];struct BPlusTreeNode *parent;bool is_leaf;int num_keys;struct BPlusTreeNode *next; // 仅叶节点使用
} BPlusTreeNode;typedef struct {BPlusTreeNode *root;
} BPlusTree;BPlusTreeNode* create_node(bool is_leaf) {BPlusTreeNode *node = (BPlusTreeNode*)malloc(sizeof(BPlusTreeNode));node->is_leaf = is_leaf;node->num_keys = 0;node->parent = NULL;node->next = NULL;memset(node->keys, 0, sizeof(node->keys));memset(node->pointers, 0, sizeof(node->pointers));return node;
}BPlusTree* create_b_plus_tree() {BPlusTree *tree = (BPlusTree*)malloc(sizeof(BPlusTree));tree->root = create_node(true); // 初始为叶节点return tree;
}BPlusTreeNode* find_leaf(BPlusTreeNode *node, int key) {if (node == NULL) return NULL;while (!node->is_leaf) {int i = 0;while (i < node->num_keys && key >= node->keys[i]) {i++;}node = (BPlusTreeNode*)node->pointers[i];}return node;
}void insert_into_leaf(BPlusTreeNode *leaf, int key, void *value) {int i = 0;while (i < leaf->num_keys && leaf->keys[i] < key) {i++;}// 移动键和指针for (int j = leaf->num_keys; j > i; j--) {leaf->keys[j] = leaf->keys[j - 1];leaf->pointers[j] = leaf->pointers[j - 1];}leaf->keys[i] = key;leaf->pointers[i] = value;leaf->num_keys++;
}void insert_into_parent(BPlusTree *tree, BPlusTreeNode *left, int key, BPlusTreeNode *right) {if (left->parent == NULL) {// 创建新根BPlusTreeNode *new_root = create_node(false);new_root->keys[0] = key;new_root->pointers[0] = left;new_root->pointers[1] = right;new_root->num_keys = 1;left->parent = new_root;right->parent = new_root;tree->root = new_root;return;}BPlusTreeNode *parent = left->parent;int insert_index = 0;while (insert_index < parent->num_keys && parent->pointers[insert_index] != left) {insert_index++;}if (parent->num_keys < MAX_KEYS) {// 父节点有空间for (int j = parent->num_keys; j > insert_index; j--) {parent->keys[j] = parent->keys[j - 1];parent->pointers[j + 1] = parent->pointers[j];}parent->keys[insert_index] = key;parent->pointers[insert_index + 1] = right;parent->num_keys++;right->parent = parent;} else {// 父节点分裂// 简化实现：省略分裂代码printf("父节点分裂未实现\n");}
}void b_plus_tree_insert(BPlusTree *tree, int key, void *value) {// 1. 找到应插入的叶节点BPlusTreeNode *leaf = find_leaf(tree->root, key);// 2. 检查叶节点是否有空间if (leaf->num_keys < MAX_KEYS) {insert_into_leaf(leaf, key, value);} else {// 叶节点分裂BPlusTreeNode *new_leaf = create_node(true);int temp_keys[MAX_KEYS + 1];void *temp_pointers[MAX_KEYS + 1];// 复制原始键和指针for (int i = 0; i < MAX_KEYS; i++) {temp_keys[i] = leaf->keys[i];temp_pointers[i] = leaf->pointers[i];}// 插入新键int i = 0;while (i < MAX_KEYS && key > temp_keys[i]) {i++;}for (int j = MAX_KEYS; j > i; j--) {temp_keys[j] = temp_keys[j - 1];temp_pointers[j] = temp_pointers[j - 1];}temp_keys[i] = key;temp_pointers[i] = value;// 分裂叶节点leaf->num_keys = MIN_KEYS + 1;new_leaf->num_keys = MIN_KEYS + 1;for (i = 0; i < leaf->num_keys; i++) {leaf->keys[i] = temp_keys[i];leaf->pointers[i] = temp_pointers[i];}for (i = 0; i < new_leaf->num_keys; i++) {new_leaf->keys[i] = temp_keys[i + leaf->num_keys];new_leaf->pointers[i] = temp_pointers[i + leaf->num_keys];}// 更新叶节点链表new_leaf->next = leaf->next;leaf->next = new_leaf;new_leaf->parent = leaf->parent;// 提升新叶节点的第一个键int promote_key = new_leaf->keys[0];insert_into_parent(tree, leaf, promote_key, new_leaf);}
}void print_b_plus_tree(BPlusTreeNode *node, int level) {if (node == NULL) return;printf("Level %d: ", level);for (int i = 0; i < node->num_keys; i++) {printf("%d ", node->keys[i]);}printf("\n");if (!node->is_leaf) {for (int i = 0; i <= node->num_keys; i++) {print_b_plus_tree(node->pointers[i], level + 1);}}
}int main() {BPlusTree *tree = create_b_plus_tree();// 插入示例数据int data[] = {10, 20, 5, 15, 30, 25, 35, 40, 45, 50, 55};int n = sizeof(data)/sizeof(data[0]);for (int i = 0; i < n; i++) {b_plus_tree_insert(tree, data[i], NULL);}printf("B+树结构:\n");print_b_plus_tree(tree->root, 0);// 模拟范围查询printf("\n范围查询[25, 45]:\n");BPlusTreeNode *leaf = find_leaf(tree->root, 25);while (leaf) {for (int i = 0; i < leaf->num_keys; i++) {if (leaf->keys[i] >= 25 && leaf->keys[i] <= 45) {printf("%d ", leaf->keys[i]);}}leaf = leaf->next;}return 0;
}

14.9 B树变种与创新

14.9.1 现代B树变种

变种	创新点	应用场景
B*树	节点满时先尝试重新分配	数据库系统
Blink树	无锁并发控制	高并发数据库
LSM树	日志结构合并	NoSQL数据库
Fractal树	消息缓冲减少磁盘I/O	高性能存储系统
Bε树	缓冲区优化	流数据处理

14.9.2 LSM树 vs B+树

14.10 总结与下一章预告

B树家族通过精心设计的节点结构和平衡算法，在磁盘与内存之间架起了高效的数据桥梁：

1. 节点优化：增大节点大小匹配磁盘块
2. 平衡策略：分裂与合并保持树平衡
3. 高效查询：对数时间复杂度保证性能
4. 范围优化：B+树叶节点链表加速范围查询

下一章预告：斐波那契堆

第十五章我们将探索斐波那契堆——这种神奇的数据结构将带来前所未有的操作效率：

• 平摊常数时间的插入和合并
• 高效减少键值操作
• 图算法中的革命性应用
• 懒惰操作与延迟合并的智慧

斐波那契堆如同数据结构领域的"瑞士军刀"，在特定场景下展现出惊人的性能优势，特别是Dijkstra最短路径算法和Prim最小生成树算法。

B树家族的创新永无止境，从传统关系型数据库到现代分布式存储系统，它们持续为海量数据管理提供可靠高效的解决方案。掌握B树不仅理解了一个数据结构，更获得了处理大规模数据的核心思维模式。