时间戳

首页 > 解决方案 > 如何将数组索引（整数）存储为 B+树中的键？

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

问题描述

我查看了GitHub 上 JavaScript 中B+树的每个示例，并尝试将其中的一个简化为半可读的代码。但是我仍然不明白keys每个内部节点的数组结构是什么。钥匙长什么样？您如何在 get/insert/remove 算法中使用它们？特别是对于这个问题，我想将 B+tree 视为外部数组或排序列表。所以我希望“键”是一个整数（数组中项目的索引）。我该怎么做呢？什么是示例 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+树的基础知识。

标签： algorithmdata-structuresb-treeb-plus-tree

解决方案

所以我希望“键”是一个整数（数组中项目的索引）。我该怎么做呢？

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

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

什么是示例 JSON 演示，显示在这种情况下简单的 B+树会是什么样子？

{ 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一个字段就足够了，但这需要将节点的所有子节点加载到内存中，仅用于累积大小以在查找/插入/删除操作中找到要选择的子节点，所以通常是尚未完成。您可以将节点大小存储在其父节点（as childSizes）中。或者您可能已经将累积的大小存储在keysB+ 树的该数组中，这样您就不需要在搜索期间计算总和（但如果只有一个条目发生更改，则必须更新整个数组 - 这是一种权衡）。与仅存储子节点k-1之间的“边界”键的经典 B+ 树不同k，将完整的总和（= 节点的大小）存储在最后一个数组索引中可能是个好主意。

推荐阅读