如何将数组索引（整数）存储为 B+树中的键？

Question

我查看了 B+tree in JavaScript on GitHub, and have tried simplifying one down to semi-readable code from this 的每个示例。但是我仍然不明白每个内部节点的 keys 数组的结构是什么。钥匙是什么样子的？你如何在 get/insert/remove 算法中使用它们？专门针对这道题，我想把B+树从外面看成一个数组，或者说是一个排序列表。所以我希望“键”是一个整数（数组中项目的索引）。我该怎么做呢？ JSON 展示简单 B+树在这种情况下的样子的示例是什么？

{
  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 个内部节点，每个内部节点都有一束叶子。内部节点中的键是什么？

我想在 JavaScript 中实现一个健壮的 B+树，目前很难理解 B+树的基础知识。

Answer 1

So I want the "key" to be an integer (the index of the item in the array). How do I do this?

不可以，不能使用item在整个结构中的绝对索引作为key。这意味着当 inserting/deleting 在数组的前面时，整个树中的所有节点都需要更新它们的索引。

相反，您需要存储子树的大小，以便在遍历树时可以将它们累积到相对索引中 - 您已经在中完成了此操作。除非节点本身（或其子节点之一）发生变化，否则这些大小永远不会改变，因此您将始终只需要更新 O(log n) 个节点。

What is an example JSON demo showing what a simple B+tree will look like in this case?

{ 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 就足够了，但这将需要将一个节点的所有子节点加载到内存中，只是为了累积大小以找到在一个节点中选择哪个子节点lookup/insert/delete操作，所以一般不会做。您可以将节点大小存储在它们的父节点中（如 childSizes）。或者您可能已经将累积大小存储在 B+ 树的 keys 数组中，这样您就不需要在搜索期间计算总和（但如果只有一个条目发生变化，则必须更新整个数组 -这是一个权衡）。与仅存储 k 个子节点之间的 k-1 “边界”键的经典 B+ 树不同，将完整的总和（= 节点的大小）存储在最后一个节点中可能是个好主意数组索引。

如何将数组索引（整数）存储为 B+树中的键？

How to store array index (an integer) as keys in a B+tree?

algorithm

data-structures

b-tree

b-plus-tree