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

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 to 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 时间成本，可能会考虑相关表中值的统计分布等信息，并选择最佳方法。