數據庫索引如何使搜索更快

Question

我正在通過rails教程進行閱讀（http://ruby.railstutorial.org/book/ruby-on-rails-tutorial#sidebar-database_indices），但對數據庫標記的解釋感到困惑，基本上筆者建議，而不是通過電子郵件列表（登錄）搜索O（n）時間，以創建索引的速度快得多，例如：

要理解數據庫索引，考慮書籍索引的類比 。在一本書中，要查找給定 字符串的所有匹配項，請說「foobar」，則必須掃描每個頁面以查找「foobar」。 另一方面，通過書籍索引，您可以在 索引中查找「foobar」，以查看包含「foobar」的所有頁面。 源： http://ruby.railstutorial.org/chapters/modeling-users#sidebar:database_indices **

所以我從例如明白的是，單詞可以用文字重複，因此，「索引頁」是由獨特的條目。但是，在railstutorial網站中，登錄設置爲每個電子郵件地址對於一個帳戶都是唯一的，那麼如果索引使得每個電子郵件最多隻有一個事件發生時，該如何加快索引？

由於

Answer 1

索引不是（很）重複。這是關於秩序。

當您進行搜索時，您希望有某種順序讓您（例如）在對數時間執行二分搜索以查找數據，而不是搜索每條記錄以找到您的關心（這不是唯一的索引類型，但它可能是最常見的）。

不幸的是，您只能按單一順序排列記錄本身。

索引只包含要用於搜索的數據（或其子集），以及指向包含實際數據的記錄的指針（或某種類型）。這允許您（例如）根據您關心的許多不同字段執行搜索，並且仍然可以對它們進行二分搜索，因爲每個索引都按該字段的順序排列。

Answer 2

因爲在DB和在給定的例子中，索引是排序字母順序。原始表/書不是。然後想：你如何搜索索引知道它被排序？我想你不會從「A」開始閱讀，直到你感興趣的地步。相反，您可以大致跳到POI並從那裏開始搜索。基本上DB可以與索引相同。

Answer 3

這樣做速度更快，因爲索引僅包含相關列中的值，因此它分佈在比整個表更少的頁面上。此外，索引通常還包含其他優化，如散列表，以限制所需的讀取次數。