在 PostgreSQL 中查找是否有 O(1) 复杂度的索引？

Question

PostgreSQL 中是否有任何索引类型为查找提供O(1) 复杂度？在字符串上？

Answer 1

您需要阅读您正在使用的版本的PostgresSQL 索引类型文档。我认为您正在寻找哈希索引，但正如文档所解释的那样，真实世界的性能和优缺点取决于您正在使用的特定版本的实现细节和建议。

Answer 2

我不认为任何东西，甚至是哈希索引，都可以保证 O(1)。

• 这只有在要求特定条目where x = 'a'或集合时才能实现where x in ('a','b')
• 哈希表通过每个“桶”对应一个哈希值的数组来实现 O(1)。另一方面，如果我们只讨论存储值，而不是空桶，那么这本质上与平衡 B 树具有相同的查找特性。
• 我在某处读到（在第 pg 中）散列索引查找“执行[不比] b 树索引”或类似的内容，这表明它没有存储在空桶中。
• O(log(N)) 相对于 O(1) 查找的惩罚很容易与将其发送到数据库并首先等待结果的开销相形见绌。

与 B 树索引相比，哈希索引可以提高性能的一种方法是将其哈希为较小的固定大小的数据块。

但是，从最新版本（9.1）的文档来看：

警告

哈希索引操作目前没有 WAL 日志记录，因此在数据库崩溃后可能需要使用 REINDEX 重建哈希索引。它们也不会通过流或基于文件的复制进行复制。由于这些原因，目前不鼓励使用哈希索引。