relly 节点分裂机制图解 B树如何保持平衡附源码解读【免费下载链接】rellyRDBMS のしくみを学ぶための小さな RDBMS 実装项目地址: https://gitcode.com/gh_mirrors/re/rellyrelly 是一个用 Rust 编写、专为学习 RDBMS 内部机制而设计的小型关系型数据库实现其 B树索引模块完整呈现了节点分裂的经典算法。本文通过图解的方式一步步拆解B树节点分裂机制讲清楚B树如何保持平衡这一核心问题非常适合想入门数据库内核的开发者阅读。为什么 B树需要节点分裂先理解页的容量在 relly 中B树的每个节点都存放在固定大小的页Page里页内数据用槽页Slotted Page方式组织见 slotted.rs。页的空间是有限的当不断插入数据、页内空间不足时就发生了溢出overflow。节点分裂正是解决溢出的唯一手段把装满的节点一分为二让两个新节点各容纳约一半的数据从而保证每个节点都不会过满——这就是 B树平衡性的基础。B树节点分裂的三个关键场景根据溢出发生在哪一层节点分裂分为三种场景这也是理解relly 节点分裂机制的完整路径。场景一叶节点分裂最常用的分裂叶节点保存真正的键值对。当向已满的叶节点插入新键时relly 会创建一个新叶页然后调用 leaf.rs 中的split_insert把旧叶节点中较小的一半数据转移到新叶节点新键按大小插入到合适的一侧返回溢出键overflow key作为父节点需要记录的分界键同时通过prev_page_id/next_page_id把相邻叶节点串成链表保证范围查询range scan仍然高效。 叶节点分裂后左右两半仍然有序链表关系也保持完整这就是 B树叶子有序 链表遍历设计的精髓。场景二分支节点分裂让分裂向上传递如果分裂发生在叶层父节点就需要插入一个指向新叶的分界键当父节点分支节点也满了就触发分支节点分裂见 branch.rs 中的split_insert与fill_right_child。分支节点里存放的是键 指向子节点的指针。分裂时 relly 会将一半的键值对转移给新分支把原来最右侧的子指针提升为right_child最右子指针再次向上返回新的溢出键继续让祖父节点处理。 关键点分裂会沿着树向上逐层传递直到某一层还有空位可以插入为止。场景三根节点分裂树长高的唯一途径如果连根节点都满了relly 会创建一个全新的根分支节点把原来的根降级为子树见 btree.rs 中的insert// 思路示意溢出到达根部时新建根节点并提升树高 branch.initialize(key, child_page_id, root_page_id);这正是 B树保持平衡的奥秘树只会从根部长高一层所有叶节点的深度始终一致。无论插入多少数据从根到任意叶子的路径长度都相等查询性能因此稳定在 O(log n)。relly 中分裂代码在哪里一目了然的源码地图想对照源码学习 B树节点分裂可按下面路径快速定位功能文件核心方法叶节点分裂leaf.rssplit_insert、transfer分支节点分裂branch.rssplit_insert、fill_right_child、transfer节点类型定义node.rsLEAF/BRANCH头标记递归插入与分裂btree.rsinsert_internal根节点元信息meta.rsroot_page_id其中 btree.rs 的insert_internal是递归核心先下钻到叶层插入若子节点分裂返回溢出键则尝试在当前分支插入满则再分裂直到根。配合单元测试如branch.rs里的test_split、leaf.rs里的test_leaf_split_insert阅读效果最佳。分裂之后B树如何保持平衡你可能会问分裂会不会让树歪掉答案是不会原因有三半满原则每次分裂都把节点拆成约一半保证节点不会过空或过满只升根、不降层所有叶节点始终在同一深度深度差永远不会出现向上传播分裂逐层传递最终总能在某个祖先节点找到容纳新键的空间。正因为这套机制relly 的 B树索引才能长期保持矮胖形态层数少、每次查询只需访问极少的页。想亲手验证可以参考 examples/ 下的btree-*.rs示例观察插入大量数据后树的结构变化。小结从分裂看懂数据库索引的本质通过 relly 的源码我们直观理解了B树节点分裂机制叶节点溢出 → 分裂成兄弟 → 分支节点记录分界键 → 必要时向上分裂 → 根节点分裂则树高加一。这一连串动作环环相扣最终保证了B树如何保持平衡的终极答案——让每个节点都不超过容量上限让树只从根部长高。如果你是数据库初学者强烈建议把 relly 源码下载下来仓库地址https://gitcode.com/gh_mirrors/re/relly对照本文的图解逐行阅读你会发现 RDBMS 的底层原理其实并不神秘。【免费下载链接】rellyRDBMS のしくみを学ぶための小さな RDBMS 実装项目地址: https://gitcode.com/gh_mirrors/re/relly创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考