database - 亚线性时间中用于二阶查找的数据结构或算法？

有什么方法可以在不到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的索引条目。这适用于非常小的数据集。但是对于大型数据集，匹配任何可能的查询组合所需的索引数量将使索引呈指数增长。

最佳答案

对于大型数据集上的此类联接，现代RDBMS通常将使用称为列表合并的算法。使用您的示例:

准备一份居住在芝加哥的所有作者的列表A，并在O(Nlog(N))时间内按作者对它们进行排序。*

准备所有(作者，书名)对的列表B，并按作者在O(Mlog(M))的时间对它们进行排序。*

将这两个列表“并排”放置，并比较每堆中“top”(按字典顺序最小)元素的作者。

他们是一样的吗？如果是这样的话:

从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时间的方式估算成千上万种不同方法的成本，并可能考虑诸如相关表中值的统计分布之类的信息，并选择最佳方法。