database - 有没有办法让数据库查询在 O(1) 处执行

Question

对非索引列的查询将导致 O(n)，因为它必须搜索整个表。由于二进制搜索，添加索引允许 O(log n)。如果您正在搜索唯一键，那么数据库是否可以使用与哈希表相同的技术（或者可能是另一种方式）来实现 O(1)？

Answer 1

在某些条件下，某些 rdbms 支持基于哈希的索引。例如，MySQL 支持这种语法CREATE INDEX indexname USING HASH ON tablename (cols…)，但前提是命名表存储在内存中，而不是存储在磁盘上。聚簇表是一种特殊情况。

我想反对在 rdbms 中广泛使用哈希索引的主要原因是它们的扩展性很差。由于磁盘 I/O 非常昂贵，因此非常薄的索引将需要大量 I/O，而信息增益很少。因此，您更喜欢一个相当密集的索引（例如，始终将填充部分保持在 ⅓ 和 ⅔ 之间），这在哈希冲突方面可能会出现问题。但更成问题的是：当您插入值时，如此密集的索引可能会变得太满，并且您必须经常增加哈希表的大小。这样做将意味着完全重建哈希表。这是一项昂贵的操作，需要大量磁盘 I/O，并且可能会阻塞该表上的所有并发查询。没有什么值得期待的。

另一方面，可以在没有太多开销的情况下扩展 B 树。即使增加它的深度（最接近于哈希表大小的扩展）也可以更便宜地完成，并且需要的频率也更低。由于 B 树往往很浅，并且由于磁盘 I/O 往往超过您在内存中所做的任何事情，因此它们仍然是大多数实际应用程序的首选解决方案。更不用说他们提供了对值范围的廉价访问这一事实，而这对于散列是不可能的。