c - 如何在 B+ Tree 中实现字符串键？

Question

许多 b+ 树示例是使用整数键实现的，但我见过其他一些同时使用整数键和字符串键的示例，我学习了 b+ 树的基础，但我不明白字符串键是如何工作的？

Answer 1

我还使用了多级 B-Tree。有一个字符串可以说 test 可以看作是 [t,e,s,t] 的数组。现在想想一棵树。每个节点只能为某个位置保存一个字符。您还需要考虑某个键/值数组实现，例如不断增长的数组、树或其他链接列表。它还可以使节点大小动态化（字母数量有限）。

如果所有键都适合叶子，则将其存储在叶子中。如果叶子变大，您可以添加新节点。

现在，由于每个节点都知道它的字母和位置，您可以从叶子中的键中删除这些字符，并在搜索时重建它们，或者如果您知道叶子 + 在叶子中的位置。

如果您现在在创建树之后以某种格式编写树，那么您最终会进行字符串压缩，其中每个字母组合（前缀）仅存储一次，即使它由 1000 个字符串共享。

简单压缩通常会导致普通文本（任何语言！）的压缩率为 1:10，内存中的压缩率为 1:4。您还可以搜索任何给定的单词（这是您使用 B+Tree 的字典中的字符串。

这是您可以使用多级的一个极端。

数据库通常使用特定的前缀树（前 x 个字符并将其余字符存储在叶子中，并在叶子中使用二分查找）。还有一些实现使用基于实际密度的可变前缀长度。所以最后它是非常具体的实现，并且存在很多选项。

如果树应该有助于找到确切的字符串。通常添加长度并使用每个字符的低位哈希就可以了。例如，您可以生成一个长度为（8 位）+ 4 位 * 6 个字符 = 32 位的哈希 -> 它是您的哈希码。或者你可以使用第一个、最后一个和中间的字符。由于长度是最具选择性的长度之一，因此您在搜索字符串时不会发现很多冲突。

此解决方案非常适合查找特定字符串，但会破坏字符串的自然顺序，因此您没有机会回答范围查询等。但是对于您搜索特定用户名/电子邮件或地址的时候，这些树会更好（但问题是为什么不使用哈希图）。

Answer 2

字符串键可以是指向字符串的指针（很可能）。

或者键的大小可以适合大多数字符串。64 位包含 8 个字节的字符串，即使是 16 个字节的密钥也不是太荒谬。

选择密钥实际上取决于您打算如何使用它。