PostgreSQL HASH索引

Question

有没有人知道在什么情况下应该使用PostgreSQL的HASH而不是B-TREE，因为对我来说，这些东西很容易让人上当。它们创建或维护所需的时间比B-TREE要多得多（至少10倍），它们还占用更多的空间（对于我的表格中的一列，B-TREE占用240 MB，而HASH将占用4 GB）。从我的谷歌搜索中得出的结论是，它们不比B-TREE的选择更快；然而，HASH可能最近已经进行了优化，或者谷歌是错的。

无论如何，我想知道你们的意见和经验。如果这些HASH是邪恶的，人们应该知道。

谢谢 另外：MySQL的HASH呢？

- Nicholas Leonard

Answer 1

哈希表在已知键值，尤其是已知唯一值的情况下比B树更快。

如果涉及的列永远不会与<或>命令进行比较扫描，则应使用哈希表。

哈希表具有O（1）的复杂度，而B树具有O（log n）的复杂度（如果我没记错的话），因此，在具有唯一条目的大表中获取一个ITEM="foo"时，哈希表将是查找它的最有效方式。

当这些唯一字段用于连接条件时，这种方法尤其实用。

- Kent Fredric

---

在查看了PostgreSQL开发者的观点之前，我的想法与您所述基本相同。但是，似乎即使对于您所描述的情况，哈希表在效率和有效性方面也没有超越B树，因为理论算法并不是那么实用。谢谢。 - Nicholas Leonard

需要注意的是，从8.4版本开始，哈希索引效率低下且比B树索引慢的问题已得到解决。http://www.postgresql.org/docs/8.4/static/release-8-4.html#AEN95616 - heycarsten

只有一个问题，据我所知，二叉树搜索的时间复杂度是O(logn)，而不是O(n*logn)，我是正确的吗？ - Juan Antonio Gomez Moriano

哈希在内存中是O(1)的，但是在数据库中，数据通常存储在磁盘上，索引也可能存在于磁盘上，磁盘访问时间 >> RAM访问时间。我不太记得数据库课程中具体如何工作，但在某些情况下它并不是O(1)。我仍然期望哈希比较快，但是在Postgres 9.5中，据报道哈希只比b-tree略快，并且它并不完全安全。 - sudo

是的。事实上，你很少能获得“真实世界”的常数时间性能，总会有一些现实因素让事情变得困难。例如，内存访问可能是O(1)，但根据你所讨论的内存是哪一个，它可能是非常大或非常小的值；）。 L1/L2/L3/RAM/Swap不都是相同的速度，但算法本身仍被认为是O(1)。 - Kent Fredric

Answer 2

对于仅使用 = 运算符搜索的文本列，最好使用哈希索引。例如需要索引查找的 URL 列。

对于像 URL 这样的内容，哈希索引的大小约为 B-Tree 索引的 30%。

缩小的大小使得 PostgreSQL 能够更有效地使用其缓存内存（也称为 shared_buffers）。

- Clive Paterson

Answer 3

根据http://www.postgresql.org/docs/9.2/static/sql-createindex.html，哈希索引仍不支持WAL（Write-Ahead Logging）安全性，这意味着在崩溃时它们并不是100％可靠的（需要重建索引，并且在复制期间可能会出现错误响应）。请参阅http://www.postgresql.org/docs/9.1/static/wal-intro.html。

- Diego Andrés Díaz Espinoza

---

这也适用于流式复制或基于文件的复制，并且在9.5版本中仍然有效。http://www.postgresql.org/docs/9.5/static/indexes-types.html - gillesB

截至版本10，这个说法已不再正确。https://www.enterprisedb.com/blog/postgresqls-hash-indexes-are-now-cool - soupdog

Answer 4

我没有尝试过这种方法，但正在考虑在非日志临时表上使用哈希索引的方法。

我的理解是，它们建立得更快，占用空间更少，并且查询比B树略快。

根据这个基准测试，哈希索引比B树索引稍微快一些，而且体积较小。然而，你不能用它们创建唯一的哈希索引，此外它们也没有进行WAL日志记录。

- L. Rodgers