对非索引列的查询将导致 O(n)，因为它必须搜索整个表。由于二分搜索，添加索引允许 O(log n)。如果您正在搜索唯一键，是否有一种方法可以让数据库使用哈希表使用的相同技术(或者可能是其他方式)来实现 O(1)？
最佳答案
在某些条件下，某些 RDBMS 支持基于哈希的索引。例如，MySQL支持语法CREATE INDEX indexname USING HASH ON tablename (cols…)但前提是指定的表存储在内存中，而不是存储在磁盘上。集群表是一种特殊情况。
我猜反对在 RDBMS 中广泛使用哈希索引的主要原因是它们的扩展性很差。由于磁盘 I/O 成本高昂，因此非常薄的索引将需要大量 I/O，但信息增益却很少。因此，您会更喜欢填充相当密集的索引(例如，始终将填充部分保持在 ⅓ 和 ⅔ 之间)，这在哈希冲突方面可能会出现问题。但问题更大:当您插入值时，这样的密集索引可能会变得太满，并且您必须经常增加哈希表的大小。这样做将意味着完全重建哈希表。这是一项昂贵的操作，需要大量磁盘 I/O，并且可能会阻止该表上的所有并发查询。不是什么值得期待的事情。
另一方面，B 树可以在没有太多开销的情况下进行扩展。即使增加其深度(这是与哈希表大小的扩展最接近的类似)，也可以更便宜地完成，并且需要的频率也更少。由于 B 树往往很浅，并且磁盘 I/O 往往超过在内存中执行的任何操作，因此它们仍然是大多数实际应用程序的首选解决方案。更不用说它们提供了对值范围的廉价访问，这是哈希不可能实现的。
关于database - 有没有办法让数据库查询以 O(1) 的速度执行，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19584878/