資料庫索引工作原理

轉載至：http://www.ituring.com.cn/article/986

譯者按：今天在翻譯時無意中搜尋到StackOverflow中的這篇文章（問答），覺得有必要翻譯出來。不僅因為文章本身寫得精彩，更重要的是它昭示了一個寫文章（特别是技術文章）的重要法則——5W1H。 原文在此 How does database indexing work?（作者：Xenph Yan）

問：随着資料庫的增大，既然索引的作用那麼重要，有誰能抛開具體的資料庫來解釋一下索引的工作原理？

答：（我自己來回答這個問題，:o-)）

為什麼需要索引

資料在磁盤上是以塊的形式存儲的。為確定對磁盤操作的原子性，通路資料的時候會一并通路所有資料塊。磁盤上的這些資料塊與連結清單類似，即它們都包含一個資料段和一個指針，指針指向下一個節點（資料塊）的記憶體位址，而且它們都不需要連續存儲（即邏輯上相鄰的資料塊在實體上可以相隔很遠）。

鑒于很多記錄隻能做到按一個字段排序，是以要查詢某個未經排序的字段，就需要使用線性查找，即要通路N/2個資料塊，其中N指的是一個表所涵蓋的所有資料塊。如果該字段是非鍵字段（也就是說，不包含唯一值），那麼就要搜尋整個表空間，即要通路全部N個資料塊。

然而，對于經過排序的字段，可以使用二分查找，是以隻要通路log2 N個資料塊。同樣，對于已經排過序的非鍵字段，隻要找到更大的值，也就不用再搜尋表中的其他資料塊了。這樣一來，性能就會有實質性的提升。

什麼是索引

索引是對記錄按照多個字段進行排序的一種方式。對表中的某個字段建立索引會建立另一種資料結構，其中儲存着字段的值，每個值又指向與它相關的記錄。這種索引的資料結構是經過排序的，因而可以對其執行二分查找。

索引的缺點是占用額外的磁盤空間。因為索引儲存在MyISAM資料庫中，是以如果為同一個表中的很多字段都建立索引，那這個檔案可能會很快膨脹到檔案系統規定的上限。

索引的原理

首先，來看一個示例資料庫表的模式：

字段名              資料類型         在磁盤上的大小
id (Primary key)   Unsigned INT     4 位元組
firstName          Char(50)         50 位元組
lastName           Char(50)         50 位元組
emailAddress       Char(100)        100 位元組
           

注意：這裡用

char

而不用

varchar

是為了精确地描述資料占用磁盤的大小。這個示例資料庫中包含500萬行記錄，而且沒有建立索引。接下來我們就分析針對這個表的兩個查詢：一個查詢使用

id

（經過排序的鍵字段），另一個查詢使用

firstName

（未經排序的非鍵字段）。

示例分析一

對于這個擁有r = 5 000 000條記錄的示例資料庫，在磁盤上要為每條記錄配置設定 R = 204位元組的固定存儲空間。這個表儲存在MyISAM資料庫中，而這個資料庫預設的資料庫塊大小為 B = 1024位元組。于是，我們可計算出這個表的分塊因數為 bfr = (B/R) = 1024/204 = 5，即磁盤上每個資料塊儲存5條記錄。那麼，儲存整個表所需的資料塊數就是 N = (r/bfr) = 5000000/5 = 1 000 000。

使用線性查找搜尋id字段——這個字段是鍵字段（每個字段的值唯一），需要通路 N/2 ＝ 500 000個資料塊才能找到目标值。不過，因為這個字段是經過排序的，是以可以使用二分查找法，而這樣平均隻需要通路log2 1000000 = 19.93 = 20 個塊。顯然，這會給性能帶來極大的提升。

再來看看firstName字段，這個字段是未經排序的，是以不可能使用二分查找，況且這個字段的值也不是唯一的，是以要從表的開頭查找末尾，即要通路 N = 1 000 000個資料塊。這種情況通過建立索引就能得到改善。

如果一條索引記錄隻包含索引字段和一個指向原始記錄的指針，那麼這條記錄肯定要比它所指向的包含更多字段的記錄更小。也就是說，索引本身占用的磁盤空間比原來的表更少，是以需要周遊的資料塊數也比搜尋原來的表更少。以下是firstName字段索引的模式：

字段名         資料類型        在磁盤上的大小
firstName     Char(50)        50 位元組
（記錄指針）    Special         4 位元組
           

注意：在MySQL中，根據表的大小，指針的大小可能是2、3、4或5位元組。

示例分析二

對于這個擁有r = 5 000 000條記錄的示例資料庫，每條索引記錄要占用 R = 54位元組磁盤空間，而且同樣使用預設的資料塊大小 B = 1024位元組。那麼索引的分塊因數就是 bfr = (B/R) = 1024/54 = 18。最終這個表的索引需要占用 N = (r/bfr) = 5000000/18 = 277 778個資料塊。

現在，再搜尋firstName字段就可以使用索引來提高性能了。對索引使用二分查找，需要通路 log2 277778 = 18.09 = 19個資料塊。再加上為找到實際記錄的位址還要通路一個資料塊，總共要通路 19 + 1 = 20個資料塊，這與搜尋未索引的表需要通路277 778個資料塊相比，不啻于天壤之别。

什麼時候用索引

建立索引要額外占用磁盤空間（比如，上面例子中要額外占用277 778個資料塊），建立的索引太多可能導緻磁盤空間不足。是以，在建立索引時，一定要慎重選擇正确的字段。

由于索引隻能提高搜尋記錄中某個比對字段的速度，是以在執行插入和删除操作的情況下，僅為輸出結果而為字段建立索引，就純粹是浪費磁盤空間和處理時間了；這種情況下不用建立索引。另外，由于二分查找的原因，資料的基數性（cardinality）或唯一性也非常重要。對基數性為2的字段建立索引，會将資料一分為二，而對基數性為1000的字段，則同樣會傳回大約1000條記錄。在這麼低的基數性下，索引的效率将減低至線性查找的水準，而查詢優化器會在基數性大于記錄數的30%時放棄索引，實際上等于索引純粹隻會浪費空間。

查詢優化器的原理

查詢優化中最核心的問題就是精确估算不同查詢計劃的成本。優化器在估算查詢計劃的成本時，會使用一個數學模型，該模型又依賴于對每個查詢計劃中涉及的最大資料量的基數性（或者叫重數）的估算。而對基數性的估算又依賴于對查詢中謂詞選擇因數（selection factor of predicates）的估算。過去，資料庫系統在估算選擇性時，要使用每個字段中值的分布情況的詳盡統計資訊，比如直方圖。這種技術對于估算孤立謂詞的選擇符效果很好。然而，很多查詢的謂詞是互相關聯的，例如 

select count(*) from R where R.make='Honda' and R.model='Accord'

。查詢謂詞經常會高度關聯（比如，

model='Accord'

的前提條件是

make='Honda'

），而估計這種關聯的選擇性非常困難。查詢優化器之是以會選擇低劣的查詢計劃，一方面是因為對基數性估算不準，另一方面就是因為遺漏了很多關聯性。而這也是為什麼資料庫管理者應該經常更新資料庫統計資訊（特别是在重要的資料加載和解除安裝之後）的原因。（譯自維基百科：http://en.wikipedia.org/wiki/Query_optimizer。）