「索引讓查詢變快」是我看過最基本的索引解釋。它很好地描述了索引最重要的作用，可惜對本書而言並不足夠。本章以較不流於表面的方式描述索引結構，但也不會鑽進太深的細節——只提供足以理解全書效能議題的洞見。

索引是純粹的冗餘#

索引是資料庫中一個獨立的結構，由 create index 敘述建立。它需要自己的磁碟空間，並持有一份被索引資料的副本。這代表索引是純粹的冗餘（redundancy）：

• 建立索引不會改變資料表的資料，只是額外建立一個指向該表的新資料結構。
• 資料庫索引其實非常像書末的索引：佔用自己的篇幅、高度冗餘、指向存放在別處的實際資訊。

SQL Server 與 MySQL（使用 InnoDB 時）對「索引」的定義更寬廣：它們把「只由索引結構構成的資料表」稱為叢集索引。在 Oracle 資料庫中，這種表叫做索引組織表（IOT, Index-Organized Table）。第 5 章「資料叢集化」會詳述它們的優缺點。

為什麼需要兩種資料結構#

在資料庫索引中搜尋，就像在紙本電話簿裡查號：關鍵在於所有條目都按明確定義的順序排列。在有序資料集中找資料既快又容易，因為排序本身就決定了每個條目的位置。

但資料庫索引比紙本目錄複雜得多，因為它處於持續變動中：

• 紙本目錄無法為每次異動改版——現有條目之間根本沒有插入新條目的空隙，只能把累積的更新留到下次印刷。
• SQL 資料庫等不了那麼久。它必須立即處理 insert、delete、update，同時維持索引順序，而且不能搬動大量資料。

資料庫結合兩種資料結構來應對這個挑戰：雙向鏈結串列（doubly linked list）與搜尋樹（search tree）。這兩者解釋了資料庫絕大部分的效能特性。