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”条目将导致带有“h”和“s”条目的 4 节点。所有剩余的条目都将是优化的单节点链。

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