做网站的有哪些,it培训机构排名前十,百家号查询排名数据查询,应用商城下载第十四章 B树与B树#xff1a;海量数据的守护者 “数据不是信息#xff0c;信息不是知识#xff0c;知识不是理解。” —— Clifford Stoll 在信息爆炸的时代#xff0c;我们需要高效管理海量数据的能力。B树家族作为数据库和文件系统的基石#xff0c;完美平衡了磁盘I/O效…第十四章 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树(t100)2-3层2-3次 #mermaid-svg-fLqw3UKJi2khGeNp {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-fLqw3UKJi2khGeNp .error-icon{fill:#552222;}#mermaid-svg-fLqw3UKJi2khGeNp .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-fLqw3UKJi2khGeNp .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-fLqw3UKJi2khGeNp .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-fLqw3UKJi2khGeNp .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-fLqw3UKJi2khGeNp .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-fLqw3UKJi2khGeNp .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-fLqw3UKJi2khGeNp .marker{fill:#333333;stroke:#333333;}#mermaid-svg-fLqw3UKJi2khGeNp .marker.cross{stroke:#333333;}#mermaid-svg-fLqw3UKJi2khGeNp svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-fLqw3UKJi2khGeNp .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-fLqw3UKJi2khGeNp .cluster-label text{fill:#333;}#mermaid-svg-fLqw3UKJi2khGeNp .cluster-label span{color:#333;}#mermaid-svg-fLqw3UKJi2khGeNp .label text,#mermaid-svg-fLqw3UKJi2khGeNp span{fill:#333;color:#333;}#mermaid-svg-fLqw3UKJi2khGeNp .node rect,#mermaid-svg-fLqw3UKJi2khGeNp .node circle,#mermaid-svg-fLqw3UKJi2khGeNp .node ellipse,#mermaid-svg-fLqw3UKJi2khGeNp .node polygon,#mermaid-svg-fLqw3UKJi2khGeNp .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-fLqw3UKJi2khGeNp .node .label{text-align:center;}#mermaid-svg-fLqw3UKJi2khGeNp .node.clickable{cursor:pointer;}#mermaid-svg-fLqw3UKJi2khGeNp .arrowheadPath{fill:#333333;}#mermaid-svg-fLqw3UKJi2khGeNp .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-fLqw3UKJi2khGeNp .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-fLqw3UKJi2khGeNp .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-fLqw3UKJi2khGeNp .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-fLqw3UKJi2khGeNp .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-fLqw3UKJi2khGeNp .cluster text{fill:#333;}#mermaid-svg-fLqw3UKJi2khGeNp .cluster span{color:#333;}#mermaid-svg-fLqw3UKJi2khGeNp div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-fLqw3UKJi2khGeNp :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} CPU L1缓存 1ns L2缓存 3ns L3缓存 10ns 主存 100ns SSD 100μs HDD 10ms 14.1.2 B树的设计哲学
1970年Rudolf Bayer和Edward M. McCreight发明了B树核心思想是
增大节点容量每个节点存储多个键值降低树高通过多路分支减少磁盘访问平衡操作节点分裂与合并保持平衡
14.2 B树的定义与性质
14.2.1 形式化定义
一棵B树T是具有以下性质的有根树
每个节点x包含 n[x]当前存储的键数key₁[x] ≤ key₂[x] ≤ … ≤ keyₙ[x]有序键值leaf[x]布尔值指示是否为叶节点 内部节点包含n[x]1个指针c₁[x], c₂[x], …, cₙ₊₁[x]指向子节点键值分隔子树范围∀k ∈ subtree(cᵢ[x]), keyᵢ₋₁[x] ≤ k ≤ keyᵢ[x]所有叶节点深度相同节点键数限制 根节点至少1个键除非树为空其他节点t-1 ≤ n ≤ 2t-1t为最小度数
#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树可视化示例(t2) #mermaid-svg-B7MqmpTXhjr1ABFt {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-B7MqmpTXhjr1ABFt .error-icon{fill:#552222;}#mermaid-svg-B7MqmpTXhjr1ABFt .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-B7MqmpTXhjr1ABFt .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-B7MqmpTXhjr1ABFt .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-B7MqmpTXhjr1ABFt .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-B7MqmpTXhjr1ABFt .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-B7MqmpTXhjr1ABFt .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-B7MqmpTXhjr1ABFt .marker{fill:#333333;stroke:#333333;}#mermaid-svg-B7MqmpTXhjr1ABFt .marker.cross{stroke:#333333;}#mermaid-svg-B7MqmpTXhjr1ABFt svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-B7MqmpTXhjr1ABFt .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-B7MqmpTXhjr1ABFt .cluster-label text{fill:#333;}#mermaid-svg-B7MqmpTXhjr1ABFt .cluster-label span{color:#333;}#mermaid-svg-B7MqmpTXhjr1ABFt .label text,#mermaid-svg-B7MqmpTXhjr1ABFt span{fill:#333;color:#333;}#mermaid-svg-B7MqmpTXhjr1ABFt .node rect,#mermaid-svg-B7MqmpTXhjr1ABFt .node circle,#mermaid-svg-B7MqmpTXhjr1ABFt .node ellipse,#mermaid-svg-B7MqmpTXhjr1ABFt .node polygon,#mermaid-svg-B7MqmpTXhjr1ABFt .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-B7MqmpTXhjr1ABFt .node .label{text-align:center;}#mermaid-svg-B7MqmpTXhjr1ABFt .node.clickable{cursor:pointer;}#mermaid-svg-B7MqmpTXhjr1ABFt .arrowheadPath{fill:#333333;}#mermaid-svg-B7MqmpTXhjr1ABFt .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-B7MqmpTXhjr1ABFt .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-B7MqmpTXhjr1ABFt .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-B7MqmpTXhjr1ABFt .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-B7MqmpTXhjr1ABFt .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-B7MqmpTXhjr1ABFt .cluster text{fill:#333;}#mermaid-svg-B7MqmpTXhjr1ABFt .cluster span{color:#333;}#mermaid-svg-B7MqmpTXhjr1ABFt div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-B7MqmpTXhjr1ABFt :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 20, 60 10, 15 30, 40 70, 80 5, 7 12, 13 17, 18 25, 26 35, 36 45, 50 65, 66 75, 76 85, 90 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);
}搜索路径示例在t3的B树中查找38
根节点: [20, 40, 60] → 选择第2子树(2038≤40)
子节点: [30, 35, 38] → 找到键3814.3.2 插入操作
插入操作需要防止节点溢出2t-1键通过分裂和提升保持平衡 #mermaid-svg-JuOInglReaHKjZgV {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-JuOInglReaHKjZgV .error-icon{fill:#552222;}#mermaid-svg-JuOInglReaHKjZgV .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-JuOInglReaHKjZgV .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-JuOInglReaHKjZgV .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-JuOInglReaHKjZgV .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-JuOInglReaHKjZgV .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-JuOInglReaHKjZgV .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-JuOInglReaHKjZgV .marker{fill:#333333;stroke:#333333;}#mermaid-svg-JuOInglReaHKjZgV .marker.cross{stroke:#333333;}#mermaid-svg-JuOInglReaHKjZgV svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-JuOInglReaHKjZgV .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-JuOInglReaHKjZgV .cluster-label text{fill:#333;}#mermaid-svg-JuOInglReaHKjZgV .cluster-label span{color:#333;}#mermaid-svg-JuOInglReaHKjZgV .label text,#mermaid-svg-JuOInglReaHKjZgV span{fill:#333;color:#333;}#mermaid-svg-JuOInglReaHKjZgV .node rect,#mermaid-svg-JuOInglReaHKjZgV .node circle,#mermaid-svg-JuOInglReaHKjZgV .node ellipse,#mermaid-svg-JuOInglReaHKjZgV .node polygon,#mermaid-svg-JuOInglReaHKjZgV .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-JuOInglReaHKjZgV .node .label{text-align:center;}#mermaid-svg-JuOInglReaHKjZgV .node.clickable{cursor:pointer;}#mermaid-svg-JuOInglReaHKjZgV .arrowheadPath{fill:#333333;}#mermaid-svg-JuOInglReaHKjZgV .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-JuOInglReaHKjZgV .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-JuOInglReaHKjZgV .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-JuOInglReaHKjZgV .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-JuOInglReaHKjZgV .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-JuOInglReaHKjZgV .cluster text{fill:#333;}#mermaid-svg-JuOInglReaHKjZgV .cluster span{color:#333;}#mermaid-svg-JuOInglReaHKjZgV div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-JuOInglReaHKjZgV :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 否 是 是 否 插入键K 节点是否已满? 直接插入 分裂节点 提升中间键到父节点 父节点是否已满? 完成 节点分裂实现
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键通过借键、合并和重分布保持平衡 #mermaid-svg-0r1SnZ70VgVDDOln {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-0r1SnZ70VgVDDOln .error-icon{fill:#552222;}#mermaid-svg-0r1SnZ70VgVDDOln .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-0r1SnZ70VgVDDOln .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-0r1SnZ70VgVDDOln .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-0r1SnZ70VgVDDOln .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-0r1SnZ70VgVDDOln .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-0r1SnZ70VgVDDOln .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-0r1SnZ70VgVDDOln .marker{fill:#333333;stroke:#333333;}#mermaid-svg-0r1SnZ70VgVDDOln .marker.cross{stroke:#333333;}#mermaid-svg-0r1SnZ70VgVDDOln svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-0r1SnZ70VgVDDOln .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-0r1SnZ70VgVDDOln .cluster-label text{fill:#333;}#mermaid-svg-0r1SnZ70VgVDDOln .cluster-label span{color:#333;}#mermaid-svg-0r1SnZ70VgVDDOln .label text,#mermaid-svg-0r1SnZ70VgVDDOln span{fill:#333;color:#333;}#mermaid-svg-0r1SnZ70VgVDDOln .node rect,#mermaid-svg-0r1SnZ70VgVDDOln .node circle,#mermaid-svg-0r1SnZ70VgVDDOln .node ellipse,#mermaid-svg-0r1SnZ70VgVDDOln .node polygon,#mermaid-svg-0r1SnZ70VgVDDOln .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-0r1SnZ70VgVDDOln .node .label{text-align:center;}#mermaid-svg-0r1SnZ70VgVDDOln .node.clickable{cursor:pointer;}#mermaid-svg-0r1SnZ70VgVDDOln .arrowheadPath{fill:#333333;}#mermaid-svg-0r1SnZ70VgVDDOln .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-0r1SnZ70VgVDDOln .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-0r1SnZ70VgVDDOln .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-0r1SnZ70VgVDDOln .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-0r1SnZ70VgVDDOln .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-0r1SnZ70VgVDDOln .cluster text{fill:#333;}#mermaid-svg-0r1SnZ70VgVDDOln .cluster span{color:#333;}#mermaid-svg-0r1SnZ70VgVDDOln div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-0r1SnZ70VgVDDOln :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 是 否 是 是 否 删除键K 是否在叶节点? 直接删除 用前驱/后继替换 节点是否下溢? 向兄弟借键 兄弟有富余? 借键 与兄弟合并 合并节点实现
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最小填充率最大填充率250%100%462.5%87.5%1081.8%90.9%10098.0%99.0%
14.4.2 树高与I/O次数
对于包含n个键、最小度数为t的B树
最小高度 h m i n ⌈ log t ( n 1 ) ⌉ − 1 h_{min} \lceil \log_t(n1) \rceil - 1 hmin⌈logt(n1)⌉−1最大高度 h m a x ⌊ log t n 1 2 ⌋ h_{max} \lfloor \log_t \frac{n1}{2} \rfloor hmax⌊logt2n1⌋
磁盘I/O次数操作复杂度 O ( h ) O ( log t n ) O(h) O(\log_t n) O(h)O(logtn)
14.5 B树数据库的引擎
14.5.1 B树与B树的区别
特性B树B树数据存储所有节点存储数据仅叶节点存储数据键重复无重复内部节点键重复叶节点链接无链接叶节点形成双向链表查找性能不稳定稳定(O(log n))范围查询低效高效空间利用率较低更高 #mermaid-svg-vnWpxYM3S3eCXvTC {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-vnWpxYM3S3eCXvTC .error-icon{fill:#552222;}#mermaid-svg-vnWpxYM3S3eCXvTC .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-vnWpxYM3S3eCXvTC .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-vnWpxYM3S3eCXvTC .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-vnWpxYM3S3eCXvTC .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-vnWpxYM3S3eCXvTC .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-vnWpxYM3S3eCXvTC .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-vnWpxYM3S3eCXvTC .marker{fill:#333333;stroke:#333333;}#mermaid-svg-vnWpxYM3S3eCXvTC .marker.cross{stroke:#333333;}#mermaid-svg-vnWpxYM3S3eCXvTC svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-vnWpxYM3S3eCXvTC .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-vnWpxYM3S3eCXvTC .cluster-label text{fill:#333;}#mermaid-svg-vnWpxYM3S3eCXvTC .cluster-label span{color:#333;}#mermaid-svg-vnWpxYM3S3eCXvTC .label text,#mermaid-svg-vnWpxYM3S3eCXvTC span{fill:#333;color:#333;}#mermaid-svg-vnWpxYM3S3eCXvTC .node rect,#mermaid-svg-vnWpxYM3S3eCXvTC .node circle,#mermaid-svg-vnWpxYM3S3eCXvTC .node ellipse,#mermaid-svg-vnWpxYM3S3eCXvTC .node polygon,#mermaid-svg-vnWpxYM3S3eCXvTC .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-vnWpxYM3S3eCXvTC .node .label{text-align:center;}#mermaid-svg-vnWpxYM3S3eCXvTC .node.clickable{cursor:pointer;}#mermaid-svg-vnWpxYM3S3eCXvTC .arrowheadPath{fill:#333333;}#mermaid-svg-vnWpxYM3S3eCXvTC .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-vnWpxYM3S3eCXvTC .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-vnWpxYM3S3eCXvTC .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-vnWpxYM3S3eCXvTC .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-vnWpxYM3S3eCXvTC .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-vnWpxYM3S3eCXvTC .cluster text{fill:#333;}#mermaid-svg-vnWpxYM3S3eCXvTC .cluster span{color:#333;}#mermaid-svg-vnWpxYM3S3eCXvTC div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-vnWpxYM3S3eCXvTC :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} B树结构 内部节点: 索引键 叶节点: 数据键记录指针 叶节点双向链表 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 数据库索引结构 #mermaid-svg-ZqlClGo1Yknd1B61 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-ZqlClGo1Yknd1B61 .error-icon{fill:#552222;}#mermaid-svg-ZqlClGo1Yknd1B61 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-ZqlClGo1Yknd1B61 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-ZqlClGo1Yknd1B61 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-ZqlClGo1Yknd1B61 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-ZqlClGo1Yknd1B61 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-ZqlClGo1Yknd1B61 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-ZqlClGo1Yknd1B61 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-ZqlClGo1Yknd1B61 .marker.cross{stroke:#333333;}#mermaid-svg-ZqlClGo1Yknd1B61 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-ZqlClGo1Yknd1B61 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-ZqlClGo1Yknd1B61 .cluster-label text{fill:#333;}#mermaid-svg-ZqlClGo1Yknd1B61 .cluster-label span{color:#333;}#mermaid-svg-ZqlClGo1Yknd1B61 .label text,#mermaid-svg-ZqlClGo1Yknd1B61 span{fill:#333;color:#333;}#mermaid-svg-ZqlClGo1Yknd1B61 .node rect,#mermaid-svg-ZqlClGo1Yknd1B61 .node circle,#mermaid-svg-ZqlClGo1Yknd1B61 .node ellipse,#mermaid-svg-ZqlClGo1Yknd1B61 .node polygon,#mermaid-svg-ZqlClGo1Yknd1B61 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-ZqlClGo1Yknd1B61 .node .label{text-align:center;}#mermaid-svg-ZqlClGo1Yknd1B61 .node.clickable{cursor:pointer;}#mermaid-svg-ZqlClGo1Yknd1B61 .arrowheadPath{fill:#333333;}#mermaid-svg-ZqlClGo1Yknd1B61 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-ZqlClGo1Yknd1B61 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-ZqlClGo1Yknd1B61 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-ZqlClGo1Yknd1B61 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-ZqlClGo1Yknd1B61 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-ZqlClGo1Yknd1B61 .cluster text{fill:#333;}#mermaid-svg-ZqlClGo1Yknd1B61 .cluster span{color:#333;}#mermaid-svg-ZqlClGo1Yknd1B61 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-ZqlClGo1Yknd1B61 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} SQL查询 查询解析器 查询优化器 存储引擎 B树索引 数据文件 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 索引优化实践
覆盖索引索引包含查询所需所有字段前缀索引对字符串前N字符建立索引索引下推在存储引擎层过滤数据MRR优化Multi-Range Read顺序访问磁盘
14.7 B树在文件系统中的应用
14.7.1 现代文件系统对比
文件系统索引结构最大文件大小特点NTFSB树16EBWindows主流ext4H树(B树变种)1EBLinux主流XFSB树8EB高性能BtrfsB树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树 #mermaid-svg-hhNPWz4Rg65SLEYC {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-hhNPWz4Rg65SLEYC .error-icon{fill:#552222;}#mermaid-svg-hhNPWz4Rg65SLEYC .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-hhNPWz4Rg65SLEYC .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-hhNPWz4Rg65SLEYC .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-hhNPWz4Rg65SLEYC .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-hhNPWz4Rg65SLEYC .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-hhNPWz4Rg65SLEYC .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-hhNPWz4Rg65SLEYC .marker{fill:#333333;stroke:#333333;}#mermaid-svg-hhNPWz4Rg65SLEYC .marker.cross{stroke:#333333;}#mermaid-svg-hhNPWz4Rg65SLEYC svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-hhNPWz4Rg65SLEYC .pieCircle{stroke:black;stroke-width:2px;opacity:0.7;}#mermaid-svg-hhNPWz4Rg65SLEYC .pieTitleText{text-anchor:middle;font-size:25px;fill:black;font-family:"trebuchet ms",verdana,arial,sans-serif;}#mermaid-svg-hhNPWz4Rg65SLEYC .slice{font-family:"trebuchet ms",verdana,arial,sans-serif;fill:#333;font-size:17px;}#mermaid-svg-hhNPWz4Rg65SLEYC .legend text{fill:black;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:17px;}#mermaid-svg-hhNPWz4Rg65SLEYC :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 14.10 总结与下一章预告
B树家族通过精心设计的节点结构和平衡算法在磁盘与内存之间架起了高效的数据桥梁
节点优化增大节点大小匹配磁盘块平衡策略分裂与合并保持树平衡高效查询对数时间复杂度保证性能范围优化B树叶节点链表加速范围查询 #mermaid-svg-xal2yPagxCep1ie2 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-xal2yPagxCep1ie2 .error-icon{fill:#552222;}#mermaid-svg-xal2yPagxCep1ie2 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-xal2yPagxCep1ie2 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-xal2yPagxCep1ie2 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-xal2yPagxCep1ie2 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-xal2yPagxCep1ie2 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-xal2yPagxCep1ie2 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-xal2yPagxCep1ie2 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-xal2yPagxCep1ie2 .marker.cross{stroke:#333333;}#mermaid-svg-xal2yPagxCep1ie2 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-xal2yPagxCep1ie2 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-xal2yPagxCep1ie2 .cluster-label text{fill:#333;}#mermaid-svg-xal2yPagxCep1ie2 .cluster-label span{color:#333;}#mermaid-svg-xal2yPagxCep1ie2 .label text,#mermaid-svg-xal2yPagxCep1ie2 span{fill:#333;color:#333;}#mermaid-svg-xal2yPagxCep1ie2 .node rect,#mermaid-svg-xal2yPagxCep1ie2 .node circle,#mermaid-svg-xal2yPagxCep1ie2 .node ellipse,#mermaid-svg-xal2yPagxCep1ie2 .node polygon,#mermaid-svg-xal2yPagxCep1ie2 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-xal2yPagxCep1ie2 .node .label{text-align:center;}#mermaid-svg-xal2yPagxCep1ie2 .node.clickable{cursor:pointer;}#mermaid-svg-xal2yPagxCep1ie2 .arrowheadPath{fill:#333333;}#mermaid-svg-xal2yPagxCep1ie2 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-xal2yPagxCep1ie2 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-xal2yPagxCep1ie2 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-xal2yPagxCep1ie2 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-xal2yPagxCep1ie2 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-xal2yPagxCep1ie2 .cluster text{fill:#333;}#mermaid-svg-xal2yPagxCep1ie2 .cluster span{color:#333;}#mermaid-svg-xal2yPagxCep1ie2 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-xal2yPagxCep1ie2 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 磁盘I/O瓶颈 B树设计哲学 节点大小优化 树高最小化 平衡操作 匹配磁盘块 减少I/O次数 分裂/合并 高效存储 下一章预告斐波那契堆 第十五章我们将探索斐波那契堆——这种神奇的数据结构将带来前所未有的操作效率 平摊常数时间的插入和合并高效减少键值操作图算法中的革命性应用懒惰操作与延迟合并的智慧 斐波那契堆如同数据结构领域的瑞士军刀在特定场景下展现出惊人的性能优势特别是Dijkstra最短路径算法和Prim最小生成树算法。 B树家族的创新永无止境从传统关系型数据库到现代分布式存储系统它们持续为海量数据管理提供可靠高效的解决方案。掌握B树不仅理解了一个数据结构更获得了处理大规模数据的核心思维模式。
