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

Question

我已经阅读了“自适应基数树:用于主存数据库的ARTful索引”的研究论文，我有一个关于如何将字符串与节点的键匹配的查询。例如:如果我有一个单词: Iota，它是表中一个元组的主键(标识符)。我必须从A到Zeta这样的值中搜索它。为了简单起见，请只考虑10个值: Alpha、Beta、Delta、Gamma、Kappa、Iota、Phi、Psi、Rho、Zeta。你会怎么做呢？

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

Answer 1

在我看来，本文只描述了一个具有不同内部节点类型的常规特瑞结构(包含4、16或256个条目，在较小的情况下需要进行二进制搜索)。作者们似乎也在某种程度上压缩了单个子节点的链。

我认为用示例键来很好地描述结构是不可能的，因为它们将在根节点上有所有单独的条目(本文中的类型为16 )，但Phi和Psi除外，其中"P“条目将导致一个包含"h”和"s“条目的4个节点。所有剩余的条目都将是优化的单节点链。

请注意，在实际情况下，与现在的堆内存大小相比，通常没有那么多不同的单词，所以我会推迟考虑“外来的”数据结构，直到有一个非常可能从中受益的真实情况。