database - 次线性时间内二次查找的数据结构或算法？

Question

有没有办法在 O(n) 时间内根据属性或谓词从一个大集合中选择一个子集？

举个简单的例子，假设我有一大群作者。每位作者与一套书籍之间存在一对多关系，与出生城市之间存在一对一关系。

有没有一种方法可以有效地执行诸如“获取出生在芝加哥的作者的所有书籍”之类的查询？我能想到的唯一方法是首先从城市中选择所有作者(快速且索引良好)，然后遍历他们并累积他们所有的书(O(n) 其中n 是来自芝加哥的作者数)。

我知道数据库在某些连接中会做类似的事情，Endeca 声称能够使用他们所谓的“记录关系导航”“快速”做到这一点，但我还没有找到任何关于实际算法的信息使用甚至他们的计算复杂性。

我并不是特别关心确切的数据结构...我很高兴在 RDBMS 中了解如何执行此操作，或键/值存储库，或任何东西。

此外，这种性质的三级或四级请求怎么办？ (把居住在移民人口大于10,000的城市的作者写的所有书给我...)是否有广义的n次算法，其性能特点是什么？

编辑:

我可能真的很笨，但我看不出倒排索引的建议有什么帮助。例如，假设我有以下数据:

DATA
1.  Milton        England
2.  Shakespeare   England
3.  Twain         USA

4.  Milton        Paridise Lost
5.  Shakespeare   Hamlet
6.  Shakespeare   Othello
7.  Twain         Tom Sawyer
8.  Twain         Huck Finn

INDEX
"Milton"         (1, 4)
"Shakespeare"    (2, 5, 6)
"Twain"          (3, 7, 8)
"Paridise Lost"  (4)
"Hamlet"         (5)
"Othello"        (6)
"Tom Sawyer"     (7)
"Huck Finn"      (8)
"England"        (1, 2)
"USA"            (3)

假设我查询了“英国作家的书”。很快，通过哈希表在 O(1) 时间内，我可以得到来自英国的作者列表:(1, 2)。但是，对于下一步，为了取回书籍，我必须为集合 {1, 2} 中的每一个做另一个 O(1) 查找:1 -> {4}, 2 -> {5, 6} 然后合并结果 {4, 5, 6}。

还是我遗漏了什么？也许你的意思是我应该明确存储一个索引条目，将 Book 链接到 Country。这适用于非常小的数据集。但是对于大型数据集，匹配任何可能的查询组合所需的索引数量会使索引呈指数级增长。

Answer 1

对于大型数据集上的这种连接，现代 RDBMS 通常会使用一种称为列表合并的算法。使用您的示例:

1. 准备一份所有住在芝加哥的作者的列表 A，并在 O(Nlog(N)) 时间内按作者排序。*
2. 准备所有(作者，书名)对的列表 B，并在 O(Mlog(M)) 时间内按作者排序。*
3. 将这两个列表“并排”放置，并比较每堆中“顶部”(按字典顺序排列的最小)元素的作者。
   • 它们相同吗？如果是这样的话:
     • 从top(B)
     输出(作者，书名)对
     • 移除B堆的顶元素
     • 转到 3。
   • 否则，是 top(A).author <top(B).author 吗？如果是这样的话:
     • 取出A堆的顶元素
     • 转到 3。
   • 否则，一定是top(A).author > top(B).author:
     • 移除B堆的顶元素
     • 转到 3。

*(或者 O(0) 时间，如果表已经按作者排序，或者有一个索引。)

循环继续一次移除一个项目，直到两堆都为空，因此需要 O(N + M) 步，其中 N 和 M 分别是堆 A 和 B 的大小。因为这两个“堆”是按作者排序的，所以该算法将发现每个匹配对。它不需要索引(尽管索引的存在可能会消除在开始时对一个或两个排序操作的需要)。

请注意，如果 RDBMS 估计这样做会更快，它可能会选择不同的算法(例如您提到的简单算法)。 RDBMS 的查询分析器通常根据磁盘访问和 CPU 时间来估计数千种不同方法的成本，可能会考虑相关表中值的统计分布等信息，并选择最佳方法。