如何将数组索引(整数)作为键存储在B+tree中？

Question

我查看了B+tree在JavaScript on GitHub中的每一个示例，并尝试了这的将一个代码简化为半可读的代码。但我仍然不明白每个内部节点的keys数组的结构是什么。钥匙是什么样子的？如何在get/insert/remove算法中使用它们？特别针对这个问题，我想把B+tree看作是一个来自外部的数组，或者是一个排序列表。因此，我希望“键”是一个整数(数组中项的索引)。我该怎么做？在本例中，JSON演示示例是什么，展示了一个简单的B+tree将是什么样子？

{
  type: 'tree',
  keys: [?],
  children: [
    {
      type: 'internal',
      keys: [?],
      children: [
        {
          type: 'leaf',
          value: { foo: '123' }
        },
        {
          type: 'leaf',
          value: { foo: '234' }
        }
      ]
    },
    {
      type: 'internal',
      keys: [?],
      children: [
        {
          type: 'leaf',
          value: { foo: '345' }
        },
        {
          type: 'leaf',
          value: { foo: '456' }
        }
      ]
    }
  ]
}

钥匙是用来做什么的？我知道他们是用来查的，但怎么查的？

假设从底部有32个内部节点，每个内部节点都有32个内部节点，每个内部节点都有一串叶子。内部节点中的密钥是什么？

我希望在B+tree中实现一个健壮的JavaScript，并且现在很难理解B+tree的基本知识。

Answer 1

因此，我希望“键”是一个整数(数组中项的索引)。我该怎么做？

不，不能使用项目在整个结构中的绝对索引作为键。这意味着在数组前面插入/删除时，整个树中的所有节点都需要更新它们的索引。

相反，您需要存储子树的大小，以便在遍历树时将它们累加到相对索引中--您已经在当树节点有子树大小时，如何按索引返回树节点？中这样做了。除非节点本身(或它的一个子节点)发生变化，否则这些大小永远不会改变，因此您总是必须只更新O(log n)节点。

在本例中，JSON演示示例是什么，展示了一个简单的B+tree将是什么样子？

{ type: 'internal',
  // size: 8,
  // childSizes: [2, 3, 3],
  keys: [2, 5],
  children: [
    { type: 'leaf',
      // size: 2
      // childSizes: [1, 1]
      keys: [1],
      values: [ {…}, {…} ]
    },
    { type: 'leaf',
      // size: 3,
      // childSizes: [1, 1, 1],
      keys: [1, 2],
      values: [ {…}, {…}, {…} ]
    },
    { type: 'internal',
      // size: 3
      // childSizes: [1, 2]
      keys: [1],
      chilren: [
        { type: 'leaf',
          // size: 1
          // childSizes: [1]
          keys: [],
          values: [ {…} ]
        },
        { type: 'leaf',
          // size: 2
          // childSizes: [1, 1]
          keys: [1],
          values: [ {…}, {…} ]
        },
      ]
    },
  ]
}

如果每个节点在一个字段中只有它的size，那么就足够了，但这需要将节点的所有子节点加载到内存中，只为了积累大小，以便在查找/插入/删除操作中找到选择哪个子节点，所以通常不会这样做。您可以将节点大小存储在其父节点中(作为childSizes)。或者，您可能已经将累积的大小存储在B+树的那个B+数组中，这样就不需要在搜索期间计算总和(但如果只有一个条目更改，则必须更新整个数组--这是一种权衡)。与传统的B+树不同，它只存储k子级之间的k-1“边界”键，在最后一个数组索引中存储完整和(=节点大小)可能是个好主意。