database - 在自适应基数树中搜索字符串

Question

我一直在阅读“自适应基数树：主内存数据库的 ARTful 索引”的研究论文，我询问了如何将字符串与节点的键匹配。例如：如果我有一个词：Iota，它是我表中一个元组的主键（标识符）。而且我必须从从 A 开始的值中搜索它，例如 Alpha 到 Zeta。为简单起见，请仅考虑 10 个值：Alpha、Beta、Delta、Gamma、Kappa、Iota、Phi、Psi、Rho、Zeta。你会怎么做呢？

参考研究论文：https ://db.in.tum.de/~leis/papers/ART.pdf

Answer 1

在我看来，这篇论文只是描述了一个具有不同内部节点类型的常规Trie结构（包含 4、16 或 256 个条目，并且需要在较小的情况下进行二进制搜索）。作者似乎还以某种方式压缩了单个子节点的链。

我认为用您的示例键无法很好地描述结构，因为除了 Phi 和 Psi 之外，它们在根节点（本文中的类型为 16）上有所有单独的条目，其中“P " entry 将导致一个 4 节点，其中包含 "h" 和 "s" 的条目。所有剩余的条目都将是优化的单节点链。

请注意，在现实世界的案例中，与今天的堆内存大小相比，通常没有那么多不同的词，所以我会推迟考虑“异国情调”的数据结构，直到有一个很可能从中获利的真实案例。