【数据结构】B+树

一、B树的基本概念1. 定义B 树是B 树的改良分支专为数据库、文件系统索引设计是 MySQL、PostgreSQL 等数据库的底层主键索引标准结构。 核心设计目标大幅优化区间范围查询、全量遍历查询同时保持极低磁盘 IO 次数。2. m 阶 B 树严格约束和 B 树最大区别阶数 m 定义节点最多存放m个子指针最多m-1个索引关键字非叶子节点索引层关键字仅做路由索引不存储完整业务数据除根节点外最少⌈m/2⌉个子节点最少⌈m/2⌉-1个 key关键字与子指针规则k₀ 子树1 k₁ 子树2 ...和 B 树逻辑一致。叶子节点数据层最核心区别所有真实完整数据记录只存在叶子节点非叶子只有索引叶子节点之间通过双向有序链表串联按 key 升序排列叶子节点 key 数量和数据记录一一对应区间查询只需顺着链表遍历全局平衡规则所有叶子节点严格在同一层树高度完全统一根节点特殊树高度 1 时至少 2 个子节点单节点树无限制。3. 和标准 B 树最直观差异对照表特性B 树B 树数据存储位置叶子、非叶子节点都存完整数据仅叶子节点存完整数据上层只有索引 key叶子节点关系无链表互相独立双向有序链表串联全局升序等值查询路径可能在非叶子节点命中提前结束无论查找任何 key必须走到叶子节点范围查询需要多次回溯父节点切换子树IO 多定位区间起点后顺着链表遍历IO 极少全表扫描整棵树深度遍历开销极大直接遍历叶子链表连续读取磁盘页节点填充上下层都存放数据空间分散上层纯索引一页能存更多路由树更低二、B 树节点结构拆解1. 非叶子节点索引页只用来导航[子指针0][key₀][子指针1][key₁][子指针2]...[keyₙ₋₁][子指针n]key真实主键 / 索引字段data完整行数据或磁盘行偏移地址尾部两个指针prev上一个叶子、next下一个叶子形成有序双向链表。结构示意图4 阶 B 树 m4所有叶子节点首尾相连全局升序。三、四大核心操作查找 / 插入 / 删除 / 分裂合并1. 查找操作等值查询流程从根索引节点逐层匹配分界 key找到对应下层子树一直向下遍历必然抵达叶子节点在叶子有序数组内二分查找目标 key匹配则取出 data无匹配则查找失败。示例查找 22根节点[10,30]→ 22 介于 10、30 之间进入中间子树[15,22]索引节点[15,22]→ 22 等于分界 key进入右侧叶子[20,22]叶子内找到 22读取对应数据。范围查询B 树碾压 B 树的核心场景需求查询12 ≤ key ≤ 35向下遍历找到区间起点12所在叶子顺着叶子节点的next链表依次读取[12,15] → [20,22] → [32,35]无需向上回溯、切换分支连续磁盘顺序读取性能极高。2. 插入操作节点分裂规则前置规则插入永远落在叶子节点上层索引节点仅同步分界 key叶子插入 key 后key 总数 ≤ m-1直接写入结束叶子 key 数量达到 m溢出执行叶子分裂分裂后向上更新父索引节点父节点溢出则递归向上分裂。4 阶 B 树分裂完整步骤m4最多 3 个 key叶子原有[20,22,32]插入 35满 4 个 key 溢出合并有序数组[20,22,32,35]从中间切割左叶子[20,22]右叶子[32,35]将右叶子第一个 key32提升到父索引节点作为分界值父节点新增 key32若父节点 key 数量达到 m重复分裂逻辑若分裂递归到根节点新建根索引树高度 1。关键区别 B 树B 树提升中间 keyB 树提升分裂后右叶子第一个 key。3. 删除操作借值 / 合并逻辑删除仅会直接修改叶子节点上层索引仅做同步更新分两类场景场景 1删除后叶子 key 数量 ≥ 最低下限⌈m/2⌉-1直接删除当前 key若删除的 key 是父节点分界值无需立刻修改上层索引允许存在已删除的 key仅作路由。场景 2删除后叶子 key 不足下限欠载方案 A优先向左右相邻叶子借关键字相邻叶子 key 数量充足取相邻的一个 key 移入当前叶子同时更新父节点分界 key。方案 B相邻叶子无多余 key执行节点合并当前叶子 相邻叶子合并为一个新叶子删除父节点对应的分界 key 若父节点因此欠载递归向上处理索引层。特殊索引层 key 冗余特性B 树上层索引的 key 可以在叶子不存在不影响查询正确性仅作为路由标记因此删除叶子数据后不会立刻同步清理上层索引减少修改开销。四、B 树的基本操作C代码完整实现本代码实现标准 m 阶 B 树完全采用工业 0 下标Base-0开发逻辑区分索引节点、叶子双向链表实现插入分裂、删除借键 / 合并、区间查询、双版本中序遍历等全套功能。一结构体与类成员变量1.struct BPlusNodeB 树节点struct BPlusNode { vectorint keys; // 关键字数组有序升序 vectorBPlusNode* children;// 子节点指针数组长度keys.size()1 bool leaf; // true叶子节点存完整数据false索引节点仅分界key BPlusNode *prev, *next; // 叶子节点双向链表前驱、后继指针索引节点无意义 BPlusNode(bool isLeaf true) : leaf(isLeaf), prev(nullptr), next(nullptr) {} };核心区别 B 树叶子节点额外维护prev/next双向指针串联全局有序链表索引节点仅存分界索引真实数据全部保存在叶子。2.class BPlusTree成员变量int m; // B树阶数 int max_keys; // 单节点最大关键字 m-1 int min_keys; // 非根节点最小关键字 ⌈m/2⌉-1 (m-1)/2 BPlusNode* root; // 根节点 BPlusNode* first_leaf;// 叶子链表头指针快速遍历全量数据构造函数BPlusTree(int order)BPlusTree(int order) { m order; max_keys m - 1; min_keys (m - 1) / 2; root new BPlusNode(true); first_leaf root; }初始化阶数、节点容量上下限创建空根初始为叶子first_leaf指向根作为叶子链表起点。二叶子链表工具函数B 树独有核心1.BPlusNode* get_leftmost(BPlusNode* n)获取最左叶子BPlusNode* get_leftmost(BPlusNode* n) { while (!n-leaf) n n-children[0]; return n; }功能输入任意节点一路向左遍历到最底层第一个叶子节点执行流程循环判断!n-leaf持续取children[0]直到抵达叶子返回该叶子指针。用途初始化、根分裂后刷新first_leaf头指针。2.void link_leaf(BPlusNode* left, BPlusNode* right)链接两个相邻叶子void link_leaf(BPlusNode* left, BPlusNode* right) { right-prev left; right-next left-next; if (left-next) left-next-prev right; left-next right; }场景叶子分裂时新建右叶子需要插入双向链表执行流程右叶子前驱 原左节点右叶子后继 原左节点原本的后继如果左节点原有后继修改其后继的前驱指向新右节点左节点后继指向新右节点 完成双向链表插入。3.void unlink_leaf(BPlusNode* node)从链表移除叶子void unlink_leaf(BPlusNode* node) { if (node-prev) node-prev-next node-next; if (node-next) node-next-prev node-prev; if (node first_leaf) first_leaf node-next; node-prev node-next nullptr; }场景叶子节点合并时删除其中一个叶子断开链表链接执行流程若存在前驱前驱后继指向 node 的后继若存在后继后继前驱指向 node 的前驱如果当前节点是链表头first_leaf更新头指针为下一个叶子清空 node 的 prev/next 指针脱离链表。三查询相关函数1.bool search(int key)等值查找bool search(int key) { BPlusNode* cur root; while (!cur-leaf) { int i 0; while ((size_t)i cur-keys.size() key cur-keys[i]) { i; } cur cur-children[i]; } auto it lower_bound(cur-keys.begin(), cur-keys.end(), key); return (it ! cur-keys.end() *it key); }B 树特性无论 key 是否匹配索引必须走到叶子节点才能判断是否存在执行流程cur root循环向下遍历索引层遍历当前节点 keys找到第一个≥key 的分界下标i进入children[i]子节点抵达叶子节点后lower_bound二分查找 key匹配成功返回 true否则 false。2.get_min() / get_max()全局最值int get_min() { return first_leaf-keys[0]; } int get_max() { BPlusNode* p first_leaf; while (p-next) p p-next; return p-keys.back(); }get_min()直接取first_leaf第一个 key全局最小值get_max()从链表头一路向后遍历到最后一个叶子取末尾 key。3.vectorint range_query(int low, int high)区间查询B 树优势vectorint range_query(int low, int high) { vectorint res; BPlusNode* cur root; while (!cur-leaf) { int i 0; while ((size_t)i cur-keys.size() low cur-keys[i]) { i; } cur cur-children[i]; } while (cur) { for (int k : cur-keys) { if (k high) return res; if (k low) res.push_back(k); } cur cur-next; } return res; }利用叶子有序链表无需递归回溯子树顺序遍历即可执行流程向下遍历索引层找到区间下限low所在的起始叶子循环遍历当前叶子所有 keykey 在[low,high]存入结果keyhigh 直接终止遍历返回切换到cur-next下一个叶子重复遍历。四插入核心split_child节点分裂B 树分裂规则和 B 树不同void split_child(BPlusNode* parent, int idx) { BPlusNode* node parent-children[idx]; BPlusNode* right new BPlusNode(node-leaf); int mid; int up_key; if (node-leaf) { mid (node-keys.size() 1) / 2; right-keys.assign(node-keys.begin() mid, node-keys.end()); node-keys.resize(mid); up_key right-keys[0]; link_leaf(node, right); } else { mid node-keys.size() / 2; up_key node-keys[mid]; right-keys.assign(node-keys.begin() mid 1, node-keys.end()); node-keys.resize(mid); right-children.assign(node-children.begin() mid 1, node-children.end()); node-children.resize(mid 1); } parent-keys.insert(parent-keys.begin() idx, up_key); parent-children.insert(parent-children.begin() idx 1, right); }函数区分两种节点分裂逻辑叶子节点 / 索引节点分支 1叶子节点分裂mid (node-keys.size() 1) / 20 下标整数除法原节点保留前 mid 个 key新右叶子复制后半段 key提升的 key 是右叶子第一个 keyB 树提升中间 key这是核心区别调用link_leaf把新右叶子插入双向链表父节点插入提升的分界 key新增右子节点指针。分支 2索引节点分裂和标准 B 树逻辑一致mid node-keys.size() / 2取中间 key 上移原节点保留前 mid 个 key 与 mid1 个子指针右索引节点复制后半段 key 与子指针父节点插入中间分界 key新增右子节点。2.void insert(int key)完整插入流程void insert(int key) { BPlusNode* cur root; vectorpairBPlusNode*, int stack; // 向下寻叶匹配规则 while (!cur-leaf) { int i 0; while ((size_t)i cur-keys.size() key cur-keys[i]) { i; } stack.emplace_back(cur, i); cur cur-children[i]; } auto it lower_bound(cur-keys.begin(), cur-keys.end(), key); if (it ! cur-keys.end() *it key) { cout 重复键\n; return; } cur-keys.insert(it, key); while ((int)cur-keys.size() max_keys) { if (stack.empty()) { BPlusNode* new_root new BPlusNode(false); new_root-children.push_back(cur); split_child(new_root, 0); root new_root; first_leaf get_leftmost(root); break; } pairBPlusNode*, int item stack.back(); stack.pop_back(); BPlusNode* p item.first; int idx item.second; split_child(p, idx); cur p; } first_leaf get_leftmost(root); }栈stack记录向下遍历路径父节点 子树下标用于向上回溯分裂向下遍历索引层找到目标叶子节点叶子有序插入 key重复 key 直接提示并退出循环判断当前节点是否溢出key 数量 max_keys栈为空根节点溢出新建上层索引根执行分裂更新全局 root栈不为空取出父节点与下标调用split_child分裂切换当前节点为父节点继续校验溢出插入完成后刷新first_leaf链表头。五删除全套函数叶子 / 索引分开借键、合并叶子节点专用操作void borrow_left_leaf(BPlusNode* parent, int idx) { BPlusNode* cur parent-children[idx]; BPlusNode* sib parent-children[idx - 1]; int val sib-keys.back(); sib-keys.pop_back(); cur-keys.insert(cur-keys.begin(), val); parent-keys[idx - 1] cur-keys[0]; } void borrow_right_leaf(BPlusNode* parent, int idx) { BPlusNode* cur parent-children[idx]; BPlusNode* sib parent-children[idx 1]; int val sib-keys[0]; sib-keys.erase(sib-keys.begin()); cur-keys.push_back(val); parent-keys[idx] sib-keys[0]; } void merge_leaf(BPlusNode* parent, int idx, bool left_side) { BPlusNode* cur parent-children[idx]; if (left_side) { BPlusNode* sib parent-children[idx - 1]; sib-keys.insert(sib-keys.end(), cur-keys.begin(), cur-keys.end()); unlink_leaf(cur); parent-keys.erase(parent-keys.begin() idx - 1); parent-children.erase(parent-children.begin() idx); } else { BPlusNode* sib parent-children[idx 1]; cur-keys.insert(cur-keys.end(), sib-keys.begin(), sib-keys.end()); unlink_leaf(sib); parent-keys.erase(parent-keys.begin() idx); parent-children.erase(parent-children.begin() idx 1); } }borrow_left_leaf当前叶子向左邻叶子借 key左叶子末尾 key 下沉到当前叶子头部更新父节点分界 key 为左叶子新末尾值。borrow_right_leaf当前叶子向右邻叶子借 key右叶子首 key 下沉到当前叶子尾部更新父节点分界 key 为右叶子新首值。merge_leaf两个叶子节点合并删除其中一个叶子并断开双向链表。索引节点专用操作void borrow_left_idx(BPlusNode* parent, int idx) { BPlusNode* cur parent-children[idx]; BPlusNode* sib parent-children[idx - 1]; int sep parent-keys[idx - 1]; cur-keys.insert(cur-keys.begin(), sep); parent-keys[idx - 1] sib-keys.back(); sib-keys.pop_back(); if (!cur-leaf) { cur-children.insert(cur-children.begin(), sib-children.back()); sib-children.pop_back(); } } void borrow_right_idx(BPlusNode* parent, int idx) { BPlusNode* cur parent-children[idx]; BPlusNode* sib parent-children[idx 1]; int sep parent-keys[idx]; cur-keys.push_back(sep); parent-keys[idx] sib-keys[0]; sib-keys.erase(sib-keys.begin()); if (!cur-leaf) { cur-children.push_back(sib-children[0]); sib-children.erase(sib-children.begin()); } } void merge_idx(BPlusNode* parent, int idx, bool left_side) { BPlusNode* cur parent-children[idx]; if (left_side) { BPlusNode* sib parent-children[idx - 1]; sib-keys.push_back(parent-keys[idx - 1]); sib-keys.insert(sib-keys.end(), cur-keys.begin(), cur-keys.end()); sib-children.insert(sib-children.end(), cur-children.begin(), cur-children.end()); parent-keys.erase(parent-keys.begin() idx - 1); parent-children.erase(parent-children.begin() idx); } else { BPlusNode* sib parent-children[idx 1]; cur-keys.push_back(parent-keys[idx]); cur-keys.insert(cur-keys.end(), sib-keys.begin(), sib-keys.end()); cur-children.insert(cur-children.end(), sib-children.begin(), sib-children.end()); parent-keys.erase(parent-keys.begin() idx); parent-children.erase(parent-children.begin() idx 1); } }borrow_left_idx索引节点向左兄弟借分界 key 子树borrow_right_idx索引节点向右兄弟借分界 key 子树merge_idx两个索引节点合并吸收父节点分隔 key 与全部子树。fix_underflow欠载修复主函数void fix_underflow(BPlusNode* node, vectorpairBPlusNode*, int stack) { while (node ! root (int)node-keys.size() min_keys) { pairBPlusNode*, int item stack.back(); stack.pop_back(); BPlusNode* p item.first; int idx item.second; BPlusNode* left_sib (idx 0) ? p-children[idx - 1] : nullptr; BPlusNode* right_sib ((size_t)(idx 1) p-children.size()) ? p-children[idx 1] : nullptr; if (node-leaf) { if (left_sib left_sib-leaf (int)left_sib-keys.size() min_keys) { borrow_left_leaf(p, idx); break; } else if (right_sib right_sib-leaf (int)right_sib-keys.size() min_keys) { borrow_right_leaf(p, idx); break; } else if (left_sib left_sib-leaf) { merge_leaf(p, idx, true); } else if (right_sib right_sib-leaf) { merge_leaf(p, idx, false); } } else { if (left_sib (int)left_sib-keys.size() min_keys) { borrow_left_idx(p, idx); break; } else if (right_sib (int)right_sib-keys.size() min_keys) { borrow_right_idx(p, idx); break; } else if (left_sib) { merge_idx(p, idx, true); } else { merge_idx(p, idx, false); } } node p; } if (root-keys.empty() !root-children.empty()) { root root-children[0]; root-prev root-next nullptr; first_leaf get_leftmost(root); } }删除后节点 key 数量低于min_keys时自下而上修复区分叶子 / 索引两套逻辑循环条件当前节点不是根、关键字不足下限取出父节点与当前子树下标判断左右兄弟叶子节点优先向左右叶子借 key无富余则合并叶子索引节点优先向左右索引兄弟借 key无富余则合并索引节点修复完成跳出循环否则将父节点设为当前节点继续向上修复特殊处理根节点根无 key 但存在子节点将第一个子节点设为新根刷新链表头。void del(int key)删除主流程void del(int key) { vectorpairBPlusNode*, int stack; BPlusNode* cur root; while (!cur-leaf) { int i 0; while ((size_t)i cur-keys.size() key cur-keys[i]) { i; } stack.emplace_back(cur, i); cur cur-children[i]; } auto it lower_bound(cur-keys.begin(), cur-keys.end(), key); if (it cur-keys.end() || *it ! key) { cout 不存在\n; return; } cur-keys.erase(it); fix_underflow(cur, stack); first_leaf get_leftmost(root); }栈记录遍历路径向下找到 key 所在叶子叶子内删除目标 key调用fix_underflow自下而上修复节点欠载、借键、合并刷新叶子链表头first_leaf。六四大遍历函数两套中序区分教学 / 业务场景1.traversal_in_business()业务中序真实数据数据库场景vectorint traversal_in_business() { vectorint res; BPlusNode* p first_leaf; while (p) { res.insert(res.end(), p-keys.begin(), p-keys.end()); p p-next; } return res; }B 树独有直接遍历叶子双向链表输出全部真实数据无索引冗余 keyBPlusNode* p first_leaf; while (p) { res.insert(res.end(), p-keys.begin(), p-keys.end()); p p-next; }对应 MySQL 全表扫描、范围查询的底层遍历逻辑。2.traversal_in_teaching()DFS 教学中序包含索引分界 keyvoid inorder_dfs(BPlusNode* n, vectorint res) { if (!n) return; if (n-leaf) { res.insert(res.end(), n-keys.begin(), n-keys.end()); return; } for (int i 0; (size_t)i n-keys.size(); i) { inorder_dfs(n-children[i], res); res.push_back(n-keys[i]); } inorder_dfs(n-children.back(), res); } vectorint traversal_in_teaching() { vectorint r; inorder_dfs(root, r); return r; }递归深度优先遍历整棵树索引节点 key 也会输出仅用于课堂画图、算法演示不对应真实数据库业务。3.traversal_pre()前序遍历void preorder(BPlusNode* n, vectorint res) { if (!n) return; res.insert(res.end(), n-keys.begin(), n-keys.end()); for (auto c : n-children) preorder(c, res); } vectorint traversal_pre() { vectorint r; preorder(root, r); return r; }先输出当前节点全部 key再依次递归所有子节点。4.traversal_post()后序遍历void postorder(BPlusNode* n, vectorint res) { if (!n) return; for (auto c : n-children) postorder(c, res); res.insert(res.end(), n-keys.begin(), n-keys.end()); } vectorint traversal_post() { vectorint r; postorder(root, r); return r; }先递归全部子节点再输出当前节点全部 key。5.traversal_level()层序遍历vectorint traversal_level() { vectorint r; queueBPlusNode* q; q.push(root); while (!q.empty()) { auto u q.front(); q.pop(); r.insert(r.end(), u-keys.begin(), u-keys.end()); for (auto c : u-children) q.push(c); } return r; }队列广度优先从上到下、每层从左到右输出节点关键字用于直观打印树分层结构。6.range_query区间遍历vectorint range_query(int low, int high) { vectorint res; BPlusNode* cur root; while (!cur-leaf) { int i 0; while ((size_t)i cur-keys.size() low cur-keys[i]) { i; } cur cur-children[i]; } while (cur) { for (int k : cur-keys) { if (k high) return res; if (k low) res.push_back(k); } cur cur-next; } return res; }利用叶子链表连续读取是 B 树相比 B 树性能碾压的核心函数。七C完整代码参考地址与运行结果完整展示1.参考地址GitCodeB-Tree-Visualizer/bplustree.cpp-代码预览-B-Tree-Visualizer:基于 PythonTkinterMatplotlib 的 B-树/B/B*树可视化工具项目 - AtomGitGitHubhttps://github.com/hongyuxu0/B-Tree-Visualizer/blob/main/bplustree.cpp2.运行结果完整展示四、B 树为什么是数据库标准索引四大核心优势1. 范围查询、分页、全表扫描性能碾压 B 树叶子双向有序链表区间查询只需顺序遍历链表磁盘连续 IOB 树需要频繁切换子树随机 IO 多。2. 树高度更低磁盘 IO 更少非叶子节点只存索引 key一页磁盘可以存放更多分界值同等数据量下树高度远小于 B 树百万级数据仅 2~3 次磁盘读取。3. 数据集中存储缓存友好所有真实数据集中在最下层叶子数据库可缓存上层全部索引页绝大多数等值查询只需要 1 次叶子磁盘 IO。4. 增删改维护成本更低上层索引存在冗余 key删除叶子数据不需要立刻同步修改上层索引减少多层节点更新操作。五、完整实操示例4 阶 Base-0 B 树 插入全过程初始空树依次插入5,15,25,35,45,10,8步骤 1初始空树依次插入 5、15、25初始根为叶子节点连续插入 3 个 key未达到上限 3无分裂叶子节点[5, 15, 25]链表[5,15,25]唯一叶子prev/nextnullptr树结构步骤 2插入 35叶子溢出执行叶子分裂原叶子 key 数组[5,15,25,35]size41.叶子分裂计算mid4/220 下标左叶子保留下标 0、1[5, 15]右叶子存放下标 2、3[25, 35]2.提升右叶子第一个 key25到父索引3.双向链表链接左叶子 next 指向右叶子右叶子 prev 指向左叶子4.新建非叶子根节点存放分界 key[25]两个子指针分别指向左、右叶子。当前完整树结构叶子链表顺序[5,15] - [25,35]步骤 3插入 45写入右侧叶子右叶子当前[25,35]插入 45 后变为[25,35,45]刚好 3 个 key未溢出无需分裂。 树结构不变仅修改右叶子叶子链表[5,15] - [25,35,45]步骤 4插入 10写入左侧叶子左叶子[5,15]插入 10有序重排为[5, 10, 15]刚好 3 个 key无溢出。叶子链表[5,10,15] - [25,35,45]步骤 5插入 8左侧叶子溢出叶子分裂左叶子原有[5,10,15]插入 8 后数组变为[5, 8, 10, 15]size4触发叶子分裂1.叶子分裂mid4/22左子叶子下标 0、1 →[5, 8]右子叶子下标 2、3 →[10, 15]2.提升右子叶子首 key10插入上层父索引节点3.链表更新原左叶子断开新两个叶子串联整体链表[5,8] - [10,15] - [25,35,45]4.父索引原有[25]插入分界 key10索引变为[10, 25]新增中间子指针指向[10,15]。最终完整 4 阶 B 树结构全部数字插入完成叶子链表完整串联[5,8] ↔ [10,15] ↔ [25,35,45]六、高频面试核心考点MySQL 为什么不用 B 树选择 B 树 ① 范围查询、分页、全表遍历效率极高② 树高度更低IO 更少③ 索引层体积小内存缓存友好④ 增删维护开销更低。B 树查找一定走到叶子吗 是上层只有索引分界真实数据仅存叶子哪怕 key 在索引层匹配也要下探叶子取数据。B 树叶子链表作用 支持高效区间查询、分页、统计 count、全表扫描。B 树删除时上层索引 key 不删除会不会出错 不会索引仅做路由标记即使 key 对应数据已删除只会导向空叶子查询逻辑不受影响。复合索引联合主键底层依旧是 B 树叶子 key 存储多字段组合有序值。七、总结B树是一种优化的多路平衡查找树专为数据库索引设计。其核心特点包括所有数据仅存储在叶子节点非叶子节点仅包含索引叶子节点通过双向链表连接支持高效范围查询通过分裂和合并操作保持平衡。相比B树B树在范围查询、全表扫描和磁盘IO效率上具有显著优势因此成为MySQL等数据库的标准索引结构。本文详细解析了B树的概念、结构、操作原理及C实现并对比了其与B树的性能差异突出了B树在数据库应用中的四大核心优势。