索引的本質是排序

索引是經常用到的技術，但有些程式設計師對索引的原理了解不深，發現數據查詢效能有問題立刻就想起建索引，但效果常常也不盡人意。那麼到底什麼時候該用索引以及該怎麼用？我們來分析索引清理背後的技術原理就知道了。

基本原理

索引技術的初衷是為了快速從一個大資料集中找出某個欄位等於確定值（比如按身份證號找出某個人）的記錄。一個規模（行數）為N的資料集，用遍歷查詢則需要比較N次，而如果資料是按該欄位值（在索引中稱為鍵值）有序的，那麼就可以建立二叉樹用二分法查詢，只要比較logN（以2為底）次，比如10億行資料只要比較30次（10億約是2^30），這顯然能大大提高效能。有時可能還會有鍵值有重複的情況（按出生日期找人）或按鍵值區間的查詢需求（按出生日期區間找人），比較次數就會比logN大一些，但基本仍是這個數量級的。

索引的本質就是排序。

當然，我們一般不會把原始資料集排序，而是把每條記錄的鍵值和這條記錄在資料集中的位置，按鍵值次序做成一個規模較小的資料集，這也就是索引表了。如果還有其它欄位也要用於鍵值查詢，則可以再建立別的索引。原始資料集只有一份，索引可以有多個，如果每個索引都把原始資料集排序，則會使資料集被複制很多遍，佔用空間過大。

另外，資料庫在建立索引時還要考慮資料會插入刪除，簡單排序的索引會導致插入刪除的成本非常高，這時一般會使用B樹以方便快速更新。B樹相當於把二叉樹擴充套件成n叉樹，本質上仍然是鍵值有序。（索引如何建立的話題內容不少，我們將另找機會討論，這裡只研討索引使用）

還有一種引申出來的方法是HASH索引，計算記錄鍵值的某種HASH值，雜湊到1。。。k的自然數範圍。這樣查詢時連二分比較也不必做，直接用HASH值定位了。HASH方法只用來做鍵值的精確查詢，不能用來實現區間查詢，因為HASH函式並不單調，已經失去原來鍵值的大小資訊了，不過這在許多場景下也夠用（按身份證號找人）。HASH索引本質上也是排序，只是用了鍵值的HASH值來排序。我們下面的討論還是以普通鍵值排序為例，結論也適用於HASH索引。

從原理上看，顯然索引不會提高全量資料遍歷的運算效能。有些程式設計師不明就裡時為了提高分組彙總效能也建索引，就是濫用了。

單索引

理解了上述原理後，我們就能知道什麼時候索引會有效，以及書寫語法時的注意事項。

1。 只針對鍵值本身提條件的，很有效。

如：身份證號等於某值的、出生日期在某個區間內的，這些都很有效。

2。 針對鍵值的函式提條件的，大部分無效，小部分取決於資料庫最佳化

如：出生日期是星期幾的，索引鍵是出生日期。索引就沒法用，因為星期幾對索引無序，這時要把索引直接建在鍵值函式上，大部分資料庫都支援這種索引。

再如：年齡在某個區間的，索引鍵是出生日期。索引不能直接用，但年齡和出生日期之間是個單調函式，如果資料庫最佳化做得好是可能利用的。但大機率是不行的。

書寫查詢條件時要儘量寫成針對原始索引鍵值本身，不要使用函式或表示式。

3。 一般性條件中包含鍵值條件的，鍵值條件作為一個最外層的AND條件時有效

如：出生日期在某天且姓名中有某字的。資料庫會用索引找出出生日期在某天的、然後再在其中遍歷查找出姓名中有某字的。現代商用資料庫都能夠智慧地分析條件表示式而找到可以使用索引提速的部分。

再如：出生日期在某天或姓名中有某字的。這時候索引就沒法用了，後半部條件反正也只能遍歷，那就直接遍歷了，索引就忽略了。

書寫多個組合查詢條件時就要注意儘量把索引鍵有關的條件放在最外層和其它條件AND起來，索引鍵不能用於縮小查詢範圍時不會提高效能。

多索引

如果我們為資料集查詢條件中涉及的多個欄位都建立索引，是否會進一步提高效能？

從上面的原理分析後結論比較悲催，大部分場景是隻能用上一個。

比如在欄位A和B上都建有索引，查詢條件是 A=1 AND B=2。先用索引A過濾出來的A=1的記錄，對B並沒有序，這時B=2的條件一般就只能硬遍歷了；反過來也一樣，先用B=2過濾的結果集對A無序，也常常是遍歷了。商用資料庫一般會預估成本，選擇A和B中的過濾後結果集較小的那個索引來用。

還有個辦法是把滿足A=1和B=2的記錄分別檢索出來，再做交集運算，就可以同時利用兩個索引。但計算交集也需要比較記錄的鍵值（或至少是內部序號等），也是某種形式的遍歷計算，不一定比計算B=2更快，要根據實際情況來決定。

如果建立A，B雙欄位索引，那麼用A=1過濾後的結果集就對B有序，就可以繼續用該索引過濾B=2的條件。資料庫最佳化較好時會知道A=1 AND B=2和B=2 AND A=1是一回事，條件書寫次序可以不必刻意和索引次序一致，只要注意上一小節所說的情況3就行：儘量把索引涉及條件放在最外層。

但是，A，B雙欄位索引對單獨的B=2這個條件無效，因為對A，B有序未必對B有序。B=2這種條件又要遍歷了，這是許多程式設計師容易犯的錯誤。完整些說，A，B，C這樣的多欄位索引，對於A=？，A=？ AND B=？，A=？ AND B=？ AND C=？這類條件都有效，但對於B=？，C=？，B=？ AND C=？這種條件是無效的，還需要重新建立關於B或C的索引。

出於這個考慮，建立一次A，B，C多欄位索引會對A，A/B，A/B/C條件都有效，那我們是否應當儘量把索引欄位搞得儘量多？從索引原理上似乎是這樣，但這樣會導致索引表也大一圈，增加IO成本，所以也不一定，需要適當的權衡。

用於遍歷

如果我們按上述原則正確地建立和使用了索引，是否就一定能提高效能呢？

還是不一定！

索引的初衷是用鍵值取數， 大多數情況是從一個巨大的資料集中會取出很少的記錄出來。這類場景下，如果按上述原則建立和使用索引，確實是能顯著地提高效能。但有時候條件遍歷取出的記錄非常多，這就很難說是不是能提高效能了，甚至可能反而更差。

原因是這樣的：

我們前述說過，建索引時一般不會直接把原始資料集排序，而是另建一個索引表。按索引表的次序取出的資料，對於原始資料集而言並不是連續存放的，資料庫最佳化做得不好時甚至可能是亂序的。硬碟取出大量不連續存放的資料時會同時取出很多無關資料，其耗時不能簡單地按取出資料量來計算，這時候使用索引取數的效能提升就不會象希望的那樣明顯。如果亂序時還強行使用索引則還可能導致重複取，對於機械硬碟再有大量的磁頭跳動時間，結果集很大時就極有可能還不如硬遍歷的效能好。不過一般商用資料庫會預估成本後選擇合適的執行計劃，發現有可能是這些情況就不再使用索引了，所以看到的表現一般最差也就是和遍歷一樣了，但如果預估不準，執行計劃搞錯了就可能出現還不如遍歷效能好的現象。

資料庫中資料一般是按插入次序存放的，如果這個次序和索引鍵序基本一致，那麼會保證取出資料在物理上存放時是相對連續的，這時候再使用索引過濾，即使取出資料量較大也經常能觀察到比較明顯的效能提升。