引言在前面的树系列中我们学习的 BST、AVL 树、红黑树都是二叉树——每个节点最多两个子节点。当数据量小、能全部放进内存时二叉树足够高效。但现实是数据库和文件系统的索引数据动辄几十 GB远远超出内存容量必须存储在磁盘上。磁盘 I/O 的速度比内存慢了几十万倍传统的二叉树高度太高一次查找需要访问几十个磁盘页完全不可接受。B 树正是为此而生。它是一种多路平衡搜索树每个节点可以存储多个键、拥有多个子节点通过矮胖的结构大幅降低树的高度从而减少磁盘 I/O 次数。第一部分B 树的基本概念一、什么是 B 树B 树B-Tree是一种自平衡的多路搜索树由 Rudolf Bayer 和 Edward McCreight 于 1971 年提出。B 树的定义m 阶 B 树二、B 树节点的内部结构三、B 树 vs 二叉树的高度对比第二部分B 树的查找一、查找过程B 树的查找和 BST 类似区别在于每个节点内有多个键需要在节点内找到正确的区间。二、查找代码#define M 5 // B 树的阶 typedef struct BTreeNode { int keys[M - 1]; // 键数组最多 M-1 个键 struct BTreeNode* children[M]; // 子节点指针数组最多 M 个 int n; // 当前键的数量 int isLeaf; // 是否为叶子节点1叶子0内部节点 } BTreeNode; // 在节点 node 内查找 key // 找到返回 1 并设置 *pos 为 key 的下标 // 未找到返回 0 并设置 *pos 为应该进入的子节点下标 int searchInNode(BTreeNode* node, int key, int* pos) { int i 0; while (i node-n key node-keys[i]) { i; } if (i node-n key node-keys[i]) { *pos i; return 1; // 找到了 } *pos i; // 没找到返回应进入的子节点下标 return 0; } // 在 B 树中查找 key BTreeNode* search(BTreeNode* root, int key) { if (root NULL) return NULL; int pos; if (searchInNode(root, key, pos)) { return root; // 在当前节点找到了 } if (root-isLeaf) { return NULL; // 叶子节点不存在 } return search(root-children[pos], key); // 进入子节点继续找 }第三部分B 树的插入一、插入策略B 树的插入比二叉树复杂很多因为节点有容量上限。核心策略始终插入到叶子节点如果节点满了就分裂。二、分裂过程5 阶 B 树M5每节点最多 4 键三、插入代码// 分裂节点 node 的第 childIndex 个子节点该子节点已满 void splitChild(BTreeNode* parent, int childIndex) { BTreeNode* child parent-children[childIndex]; BTreeNode* newChild (BTreeNode*)malloc(sizeof(BTreeNode)); newChild-isLeaf child-isLeaf; int mid (M - 1) / 2; // 中间键的位置 // 右半部分的键复制到新节点 newChild-n child-n - mid - 1; for (int j 0; j newChild-n; j) { newChild-keys[j] child-keys[mid 1 j]; } // 如果不是叶子复制子指针 if (!child-isLeaf) { for (int j 0; j newChild-n; j) { newChild-children[j] child-children[mid 1 j]; } } child-n mid; // 左半部分保留在原节点 // 父节点腾出位置插入中间键 for (int j parent-n; j childIndex; j--) { parent-keys[j] parent-keys[j - 1]; parent-children[j 1] parent-children[j]; } parent-keys[childIndex] child-keys[mid]; parent-children[childIndex 1] newChild; parent-n; } // 向非满节点插入 key递归辅助函数 void insertNonFull(BTreeNode* node, int key) { int i node-n - 1; if (node-isLeaf) { // 叶子节点找到位置直接插入 while (i 0 key node-keys[i]) { node-keys[i 1] node-keys[i]; i--; } node-keys[i 1] key; node-n; } else { // 内部节点找到应该进入的子节点 while (i 0 key node-keys[i]) i--; i; // 子节点下标 // 如果子节点满了先分裂 if (node-children[i]-n M - 1) { splitChild(node, i); if (key node-keys[i]) i; // 确定分裂后进入哪个子节点 } insertNonFull(node-children[i], key); } } // B 树插入主函数 BTreeNode* insert(BTreeNode* root, int key) { if (root NULL) { BTreeNode* node (BTreeNode*)malloc(sizeof(BTreeNode)); node-keys[0] key; node-n 1; node-isLeaf 1; return node; } if (root-n M - 1) { // 根满了创建新根 BTreeNode* newRoot (BTreeNode*)malloc(sizeof(BTreeNode)); newRoot-isLeaf 0; newRoot-n 0; newRoot-children[0] root; splitChild(newRoot, 0); insertNonFull(newRoot, key); return newRoot; } insertNonFull(root, key); return root; }第四部分B 树的删除B 树的删除是最复杂的操作核心原则是删除后每个节点仍满足最少键数的要求根除外内部节点至少 ⌈M/2⌉-1 个键。一、删除的三种情况二、删除后的借与合并当节点删除后键数不足最少要求时第五部分B 树的性能分析操作时间复杂度说明查找O(log n)每层在节点内二分查找 O(log m) 树高 O(logₘ n) O(log n)插入O(log n)可能向上分裂最坏到根删除O(log n)可能借键或合并最坏到根空间O(n)每节点有 M-1 个键和 M 个指针总结一、B 树核心要点要点内容核心思想多路搜索矮胖结构减少磁盘 I/O节点结构键 子指针键在节点内有序插入总是插入叶子满了就分裂可能向上递归删除删内部节点用前后继替代删叶子可能借或合并平衡性所有叶子在同一层应用数据库索引B 树变体、文件系统二、B 树 vs 二叉树对比二叉树B 树子节点数2M 个树高高log₂n矮logₘn磁盘 I/O多少适用场景内存磁盘三、一句话记忆B 树是多路平衡搜索树每个节点存多个键、有多个子节点通过矮胖结构大幅降低树高从而减少磁盘 I/O 次数是数据库和文件系统索引的底层基石。
