[[191391]] 

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

基本原理

索引技術的初衷是為了快速從一個大數據集中找出某個字段等于確定值(比如按身份證號找出某個人)的記錄。一個規模(行數)為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 OR B=2反而有可能用上，優化能力較好的數據庫會分別用索引過濾出A=1和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成本，所以也不一定，需要適當的權衡。

用于遍歷

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

還是不一定!

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

原因是這樣的：

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

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