如何最大化唯一键B-Tree每个节点的存储键数量？

我之前在实现B-Tree的时候也碰到过一模一样的问题——尤其是顺序插入场景下，左侧节点永远卡在t-1个键的最小状态，空间利用率特别低。结合我踩过的坑和优化经验，来聊聊怎么完善你的方案：

核心问题分析 #

当t=3时，每个节点最多存5个键（2t-1），最少存2个键（t-1）。顺序插入时，每次都是右侧节点被填满分裂，分裂后左节点固定为2个键，后续新键只会往右侧节点堆，导致左节点永远没机会接收新数据，空间利用率只有40%（2/5），这确实很浪费。

完善「向相邻节点借键」的具体方案 #

借键（也叫节点旋转）确实是解决空间利用率的关键，但要明确它的适用场景和执行逻辑——它主要用于节点即将溢出但兄弟节点还有空闲空间的情况，能避免不必要的分裂：

借键操作的步骤（以叶子节点插入为例） #

当你要插入新键到已满的叶子节点时，按以下顺序处理：

• 第一步：检查左兄弟是否有空闲
  如果左兄弟存在，且键数小于2t-1（没满）：
  1. 取出父节点中分隔当前节点和左兄弟的分界键k
  2. 把左兄弟的最大键移到父节点，替换掉原来的k
  3. 把父节点原来的k移到当前节点的最左侧
  4. 现在当前节点腾出了一个位置，直接插入新键即可
• 第二步：检查右兄弟是否有空闲
  如果左兄弟没空间，就看右兄弟：
  1. 取出父节点中分隔当前节点和右兄弟的分界键k
  2. 把当前节点的最小键移到父节点，替换掉k
  3. 把父节点原来的k移到右兄弟的最左侧
  4. 当前节点腾出位置，插入新键
• 第三步：如果兄弟都没空间，再执行分裂
  这时候只能按标准B-Tree分裂逻辑处理：把当前节点的键+新键合并排序，分成左半t-1个键、中间键、右半t-1个键，中间键插入父节点，递归处理父节点可能的溢出。

借键的优势 #

这种操作能在非极端顺序插入的场景下，大幅减少分裂次数，让节点尽可能存满键。比如如果插入是随机的，或者偶尔往左侧补插数据，左兄弟有多余空间时，就能通过借键避免分裂，提升空间利用率。

极端顺序插入场景的额外优化 #

如果你的B-Tree主要处理顺序插入的业务，还可以加个顺序插入检测的小逻辑：

• 当检测到连续N次（比如N=t）往同一方向（比如最右侧）插入键时，直接创建一个新的叶子节点，把后续的键批量插入到新节点，直到新节点满了再分裂。
• 这种方式虽然没法让左侧节点填满，但能减少分裂的次数，提升整体插入效率，同时让右侧节点尽可能保持满的状态。

注意事项 #

• 借键操作要保证父节点和兄弟节点的键数始终符合B-Tree的性质：每个节点至少t-1个键，最多2t-1个键，千万别违规。
• 实现时要注意指针（或引用）的调整，尤其是父节点和子节点之间的关联关系，别搞混了。

内容的提问来源于stack exchange，提问作者user3421425