data-structures - B-Tree 键的值存储在哪里？

Question

我一直在研究用于存储大约 10k 字符串数据库的 B 树，每个字符串都有一个唯一的 ID，我认为它可以作为我的 key 。但是我看到的每个实现都只显示 B 树中的键而不是值。我确信 B-Tree 在充当映射时必须将值链接到键，但我无法理解它们是否与键一起存储在树的节点中。例如。

       ||key3|   |key6||
     /         |          \
    /   ||key4| |key5||    \
   /                        \
||key1| |key2||         ||key7| |key8||

---

       ||k3,v3| |k6,v6||
     /         |         \
    /   ||k4,v4||k5,v5||  \
   /                       \
||k1,v1| |k2,v2||         ||k7,v7| |k8,v8||

我不确定这些值的存储方式和位置。

Answer 1

在每个单个节点中，包括内部节点和叶节点，以及键。

在 B+-Tree 中，所有键都在叶节点中可用。因此，在拆分叶节点的情况下，您只能将键推送给父节点，并为自己保留值。然而，在 B 树中，键不会重复，因此您必须在内部节点中拥有值。

您可以使用键值映射并迭代它的键以实现特定于树的函数。由于您需要对键进行排序，因此您应该使用排序的映射，例如 Java 中的 TreeMap 或 C++ 中的简单 std::map。 (Python 在标准库中没有类似的东西。)它们还有助于轻松拆分节点并将内容推送到新节点。