是否有數據庫查詢在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往往會超出你在內存中做的任何事情，所以它們仍然是大多數實際應用的首選解決方案。更不用說他們提供廉價訪問值的範圍，這對於散列來說是不可能的。