[[191391]] 

索引是經(jīng)常用到的技術(shù)，但有些程序員對(duì)索引的原理了解不深，發(fā)現(xiàn)數(shù)據(jù)查詢(xún)性能有問(wèn)題立刻就想起建索引，但效果常常也不盡人意。那么到底什么時(shí)候該用索引以及該怎么用?我們來(lái)分析索引清理背后的技術(shù)原理就知道了。

基本原理

索引技術(shù)的初衷是為了快速?gòu)囊粋€(gè)大數(shù)據(jù)集中找出某個(gè)字段等于確定值(比如按身份證號(hào)找出某個(gè)人)的記錄。一個(gè)規(guī)模(行數(shù))為N的數(shù)據(jù)集，用遍歷查找則需要比較N次，而如果數(shù)據(jù)是按該字段值(在索引中稱(chēng)為鍵值)有序的，那么就可以建立二叉樹(shù)用二分法查找，只要比較logN(以2為底)次，比如10億行數(shù)據(jù)只要比較30次(10億約是2^30)，這顯然能大大提高性能。有時(shí)可能還會(huì)有鍵值有重復(fù)的情況(按出生日期找人)或按鍵值區(qū)間的查找需求(按出生日期區(qū)間找人)，比較次數(shù)就會(huì)比logN大一些，但基本仍是這個(gè)數(shù)量級(jí)的。

索引的本質(zhì)就是排序。

當(dāng)然，我們一般不會(huì)把原始數(shù)據(jù)集排序，而是把每條記錄的鍵值和這條記錄在數(shù)據(jù)集中的位置，按鍵值次序做成一個(gè)規(guī)模較小的數(shù)據(jù)集，這也就是索引表了。如果還有其它字段也要用于鍵值查找，則可以再建立別的索引。原始數(shù)據(jù)集只有一份，索引可以有多個(gè)，如果每個(gè)索引都把原始數(shù)據(jù)集排序，則會(huì)使數(shù)據(jù)集被復(fù)制很多遍，占用空間過(guò)大。

另外，數(shù)據(jù)庫(kù)在建立索引時(shí)還要考慮數(shù)據(jù)會(huì)插入刪除，簡(jiǎn)單排序的索引會(huì)導(dǎo)致插入刪除的成本非常高，這時(shí)一般會(huì)使用B樹(shù)以方便快速更新。B樹(shù)相當(dāng)于把二叉樹(shù)擴(kuò)展成n叉樹(shù)，本質(zhì)上仍然是鍵值有序。(索引如何建立的話(huà)題內(nèi)容不少，我們將另行撰文討論，這里只研討索引使用)

還有一種引申出來(lái)的方法是HASH索引，計(jì)算記錄鍵值的某種HASH值，散列到1…k的自然數(shù)范圍。這樣查找時(shí)連二分比較也不必做，直接用HASH值定位了。HASH方法只用來(lái)做鍵值的精確查找，不能用來(lái)實(shí)現(xiàn)區(qū)間查找，因?yàn)镠ASH函數(shù)并不單調(diào)，已經(jīng)失去原來(lái)鍵值的大小信息了，不過(guò)這在許多場(chǎng)景下也夠用(按身份證號(hào)找人)。HASH索引本質(zhì)上也是排序，只是用了鍵值的HASH值來(lái)排序。我們下面的討論還是以普通鍵值排序?yàn)槔Y(jié)論也適用于HASH索引。

從原理上看，顯然索引不會(huì)提高全量數(shù)據(jù)遍歷的運(yùn)算性能。有些程序員不明就里時(shí)為了提高分組匯總性能也建索引，就是濫用了。

單索引

理解了上述原理后，我們就能知道什么時(shí)候索引會(huì)有效，以及書(shū)寫(xiě)語(yǔ)法時(shí)的注意事項(xiàng)。

1. 只針對(duì)鍵值本身提條件的，很有效。

如：身份證號(hào)等于某值的、出生日期在某個(gè)區(qū)間內(nèi)的，這些都很有效。

2. 針對(duì)鍵值的函數(shù)提條件的，大部分無(wú)效，小部分取決于數(shù)據(jù)庫(kù)優(yōu)化

如：出生日期是星期幾的，索引鍵是出生日期。索引就沒(méi)法用，因?yàn)樾瞧趲讓?duì)索引無(wú)序，這時(shí)要把索引直接建在鍵值函數(shù)上，大部分?jǐn)?shù)據(jù)庫(kù)都支持這種索引。

再如：年齡在某個(gè)區(qū)間的，索引鍵是出生日期。索引不能直接用，但年齡和出生日期之間是個(gè)單調(diào)函數(shù)，如果數(shù)據(jù)庫(kù)優(yōu)化做得好是可能利用的。但大概率是不行的。

書(shū)寫(xiě)查詢(xún)條件時(shí)要盡量寫(xiě)成針對(duì)原始索引鍵值本身，不要使用函數(shù)或表達(dá)式。

3. 一般性條件中包含鍵值條件的，鍵值條件作為一個(gè)最外層的AND條件時(shí)有效

如：出生日期在某天且姓名中有某字的。數(shù)據(jù)庫(kù)會(huì)用索引找出出生日期在某天的、然后再在其中遍歷查找出姓名中有某字的。現(xiàn)代商用數(shù)據(jù)庫(kù)都能夠智能地分析條件表達(dá)式而找到可以使用索引提速的部分。

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

書(shū)寫(xiě)多個(gè)組合查詢(xún)條件時(shí)就要注意盡量把索引鍵有關(guān)的條件放在最外層和其它條件AND起來(lái)，索引鍵不能用于縮小查詢(xún)范圍時(shí)不會(huì)提高性能。

多索引

如果我們?yōu)閿?shù)據(jù)集查詢(xún)條件中涉及的多個(gè)字段都建立索引，是否會(huì)進(jìn)一步提高性能?

從上面的原理分析后結(jié)論比較悲催，大部分場(chǎng)景是只能用上一個(gè)。

比如在字段A和B上都建有索引，查詢(xún)條件是 A=1 AND B=2。先用索引A過(guò)濾出來(lái)的A=1的記錄，對(duì)B并沒(méi)有序，這時(shí)B=2的條件只能硬遍歷;反過(guò)來(lái)也一樣，先用B=2過(guò)濾的結(jié)果集對(duì)A無(wú)序，也只能遍歷了。商用數(shù)據(jù)庫(kù)一般會(huì)預(yù)估成本，選擇A和B中的過(guò)濾后結(jié)果集較小的那個(gè)索引來(lái)用。

不過(guò)，如果是A=1 OR B=2反而有可能用上，優(yōu)化能力較好的數(shù)據(jù)庫(kù)會(huì)分別用索引過(guò)濾出A=1和B=2的記錄，再做個(gè)并集。

還可以建立多字段索引，如果建立A,B雙字段索引，那么用A=1過(guò)濾后的結(jié)果集就對(duì)B有序，就可以繼續(xù)用該索引過(guò)濾B=2的條件。數(shù)據(jù)庫(kù)優(yōu)化較好時(shí)會(huì)知道A=1 AND B=2和B=2 AND A=1是一回事，條件書(shū)寫(xiě)次序可以不必刻意和索引次序一致，只要注意上一小節(jié)所說(shuō)的情況3就行：盡量把索引涉及條件放在最外層。

但是，A,B雙字段索引對(duì)單獨(dú)的B=2這個(gè)條件并無(wú)效，因?yàn)閷?duì)A,B有序未必對(duì)B有序。B=2這種條件普只能再遍歷了，這是許多程序員容易犯的錯(cuò)誤。完整些說(shuō)，A,B,C這樣的多字段索引，對(duì)于A=?，A=? AND B=?，A=? AND B=? AND C=?這類(lèi)條件都有效，但對(duì)于B=?，C=?，B=? AND C=?這種條件是無(wú)效的，還需要重新建立關(guān)于B或C的索引。

出于這個(gè)考慮，建立一次A,B,C多字段索引會(huì)對(duì)A,A/B,A/B/C條件都有效，那我們是否應(yīng)當(dāng)盡量把索引字段搞得盡量多?從索引原理上似乎是這樣，但這樣會(huì)導(dǎo)致索引表也大一圈，增加IO成本，所以也不一定，需要適當(dāng)?shù)臋?quán)衡。

用于遍歷

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

還是不一定!

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

原因是這樣的：

我們前述說(shuō)過(guò)，建索引時(shí)一般不會(huì)直接把原始數(shù)據(jù)集排序，而是另建一個(gè)索引表。按索引表的次序取出的數(shù)據(jù)，對(duì)于原始數(shù)據(jù)集而言并不是連續(xù)存放的，數(shù)據(jù)庫(kù)優(yōu)化做得不好時(shí)甚至可能是亂序的。硬盤(pán)取出大量不連續(xù)存放的數(shù)據(jù)時(shí)會(huì)同時(shí)取出很多無(wú)關(guān)數(shù)據(jù)，其耗時(shí)不能簡(jiǎn)單地按取出數(shù)據(jù)量來(lái)計(jì)算，這時(shí)候使用索引取數(shù)的性能提升就不會(huì)象希望的那樣明顯。如果亂序時(shí)還強(qiáng)行使用索引則還可能導(dǎo)致重復(fù)取，對(duì)于機(jī)械硬盤(pán)再有大量的磁頭跳動(dòng)時(shí)間，結(jié)果集很大時(shí)就極有可能還不如硬遍歷的性能好。不過(guò)一般商用數(shù)據(jù)庫(kù)會(huì)預(yù)估成本后選擇合適的執(zhí)行計(jì)劃，發(fā)現(xiàn)有可能是這些情況就不再使用索引了，所以看到的表現(xiàn)一般最差也就是和遍歷一樣了，但如果預(yù)估不準(zhǔn)，執(zhí)行計(jì)劃搞錯(cuò)了就可能出現(xiàn)還不如遍歷性能好的現(xiàn)象。

數(shù)據(jù)庫(kù)中數(shù)據(jù)一般是按插入次序存放的，如果這個(gè)次序和索引鍵序基本一致，那么會(huì)保證取出數(shù)據(jù)在物理上存放時(shí)是相對(duì)連續(xù)的，這時(shí)候再使用索引過(guò)濾，即使取出數(shù)據(jù)量較大也經(jīng)常能觀察到比較明顯的性能提升。