You need to enable JavaScript to run this app. JS实现B+tree时如何将数组索引作为键并理解其节点结构?
优惠活动
大模型
产品
解决方案
定价
更多

JS实现B+tree时如何将数组索引作为键并理解其节点结构?

Internal节点keys的核心结构规则

所有非叶子的internal节点,自身不存储实际业务数据,仅存路由用的分隔键,有两个硬性规则:

  • 节点的children数组长度为n时,keys数组的长度固定为n-1,keys本身是严格从小到大排序的。
  • 每个分隔键的路由含义:keys[i]是划分范围的边界——当前节点下,children[0]到children[i]对应的所有子树中,存储的所有叶子键值全部小于keys[i];children[i+1]及之后的子树中,存储的所有叶子键值全部大于等于keys[i]。
    对应每个子节点的键值范围可以直接推导:
    • children[0]的键范围:负无穷 ~ keys[0]
    • 中间的children[i](0 < i < n-1)的键范围:keys[i-1] ~ keys[i]
    • 最后一个children[n-1]的键范围:keys[n-2] ~ 正无穷

keys在核心操作中的使用逻辑

三个核心操作的路由逻辑完全统一,都是从根节点逐层向下匹配:

  • 查找(get):在当前internal节点的有序keys中,找到第一个大于目标查找键的位置索引i,直接进入children[i]对应的子树,重复判断直到到达叶子节点。
    举个例子:当前节点keys为[10,20,30],对应children为[c0,c1,c2,c3],查找键25,第一个比25大的key是30,索引为2,因此进入children[2]继续判断。
  • 插入:先走和查找完全相同的路径定位到目标叶子节点,插入新键值。如果当前叶子节点的键数超过预设的最大阈值,就将叶子拆分为两个,把拆分位置的中间键提升到父节点的keys数组中作为新的分隔键,同时父节点的children数组新增一个指向新拆分叶子的指针。如果父节点也超过容量阈值,就递归向上拆分,直到根节点被拆出两个子节点时,创建新的根节点,树高加1。
  • 删除:先走查找路径定位到存储目标键的叶子节点,删掉对应键值。如果当前叶子节点的键数低于预设的最小阈值,就尝试从相邻兄弟节点借键,或者和相邻兄弟合并。合并过程中需要把父节点里对应的分隔键删除,同步调整父节点的keys和children数组长度,递归向上处理直到根节点的children长度收敛为1,就删除当前根节点,树高减1。

整数键(数组索引形态)的实现逻辑

如果要让B+树对外表现为有序数组,所有的键就是对应数组项的整数索引,实现上不需要做额外特殊处理:

  • 叶子节点按从小到大的顺序存储所有整数键和对应的值,节点之间用指针串联成有序链表,从第一个叶子遍历到最后一个叶子就能按索引顺序读出整个数组的内容。
  • 所有internal节点的分隔键,直接取对应右子树存储的最小整数键值即可,完全复用上面提到的路由规则。

对应你提供的JSON结构的填充示例

你给出的初始结构缺少叶子节点自身的keys字段(internal节点的路由键最终要和叶子的实际键对应),补全后填充的完整结构如下,我们假设叶子节点分别存储整数键0、1、2、3,对应你写的四个值对象:

{
  "type": "tree",
  "keys": [2],
  "children": [
    {
      "type": "internal",
      "keys": [1],
      "children": [
        {
          "type": "leaf",
          "keys": [0],
          "value": { "foo": "123" }
        },
        {
          "type": "leaf",
          "keys": [1],
          "value": { "foo": "234" }
        }
      ]
    },
    {
      "type": "internal",
      "keys": [3],
      "children": [
        {
          "type": "leaf",
          "keys": [2],
          "value": { "foo": "345" }
        },
        {
          "type": "leaf",
          "keys": [3],
          "value": { "foo": "456" }
        }
      ]
    }
  ]
}

这个结构的路由是自洽的:

  • 根节点的keys为[2]:第一个internal子树负责所有小于2的键(0、1),第二个internal子树负责所有大于等于2的键(2、3)。
  • 第一个internal节点的keys为[1]:第一个叶子负责所有小于1的键(0),第二个叶子负责所有大于等于1的键(1)。
  • 第二个internal节点的keys为[3]:第一个叶子负责所有小于3的键(2),第二个叶子负责所有大于等于3的键(3)。

大规模层级场景下的keys构成

如果结构是「根节点下32个internal节点、每个internal节点下再挂32个internal节点、最下层internal节点连接叶子」,所有层的keys遵循完全相同的规则:

  • 最顶层的根节点:因为有32个children,keys数组长度为31。每个key是对应右侧子树覆盖的最小整数键,比如第一个子树覆盖01023(32*32个索引位置),第二个子树覆盖10242047,那么根的第一个key就是1024,第二个是2048,以此类推。
  • 根下的32个第二层internal节点:每个节点有32个children,keys数组长度同样为31。比如某个节点负责覆盖01023的范围,它的第一个子节点负责031,第二个负责32~63,那么这个节点的第一个key就是32,第二个是64,以此类推。
  • 最下层直接连接叶子的internal节点:每个节点32个children,keys长度31,每个key就是右侧相邻叶子存储的最小整数键,逻辑和最开始的简单示例完全一致。

内容的提问来源于stack exchange,提问作者Lance Pollard

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.10 01:15:10