數(shù)據(jù)庫索引的作用和原理

數(shù)據(jù)庫索引是為了增加查詢速度而對(duì)表字段附加的一種標(biāo)識(shí)。很多人機(jī)械的理解索引的概念，認(rèn)為增加索引只有好處沒有壞處。其實(shí)遠(yuǎn)不是那樣的，這里將其介紹盡量詳細(xì)些。

首先明白為什么索引會(huì)增加速度，DB在執(zhí)行一條Sql語句的時(shí)候，默認(rèn)的方式是根據(jù)搜索條件進(jìn)行全表掃描，遇到匹配條件的就加入搜索結(jié)果集合。如果我們對(duì)某一字段增加索引，查詢時(shí)就會(huì)先去索引列表中一次定位到特定值的行數(shù)，大大減少遍歷匹配的行數(shù)，所以能明顯增加查詢的速度。那么在任何時(shí)候都應(yīng)該加索引么？這里有幾個(gè)反例：1、如果每次都需要取到所有表記錄，無論如何都必須進(jìn)行全表掃描了，那么是否加索引也沒有意義了。2、對(duì)非唯一的字段，例如“性別”這種大量重復(fù)值的字段，增加索引也沒有什么意義。3、對(duì)于記錄比較少的表，增加索引不會(huì)帶來速度的優(yōu)化反而浪費(fèi)了存儲(chǔ)空間，因?yàn)?a href='/map/suoyin/' style='color:#000;font-size:inherit;'>索引是需要存儲(chǔ)空間的，而且有個(gè)致命缺點(diǎn)是對(duì)于update/insert/delete的每次執(zhí)行，字段的索引都必須重新計(jì)算更新。

那么在什么時(shí)候適合加上索引呢？我們看一個(gè)Mysql手冊(cè)中舉的例子，這里有一條sql語句：

SELECT c.companyID, c.companyName FROM Companies c, User u WHERE c.companyID = u.fk_companyID AND c.numEmployees >= 0 AND c.companyName LIKE '%i%' AND u.groupID IN (SELECT g.groupID FROM Groups g WHERE g.groupLabel = 'Executive')

這條語句涉及3個(gè)表的聯(lián)接，并且包括了許多搜索條件比如大小比較，Like匹配等。在沒有索引的情況下Mysql需要執(zhí)行的掃描行數(shù)是77721876行。而我們通過在companyID和groupLabel兩個(gè)字段上加上索引之后，掃描的行數(shù)只需要134行。在Mysql中可以通過Explain Select來查看掃描次數(shù)。可以看出來在這種聯(lián)表和復(fù)雜搜索條件的情況下，索引帶來的性能提升遠(yuǎn)比它所占據(jù)的磁盤空間要重要得多。

那么索引是如何實(shí)現(xiàn)的呢？大多數(shù)DB廠商實(shí)現(xiàn)索引都是基于一種數(shù)據(jù)結(jié)構(gòu)——B樹。因?yàn)锽樹的特點(diǎn)就是適合在磁盤等直接存儲(chǔ)設(shè)備上組織動(dòng)態(tài)查找表。B樹的定義是這樣的：一棵m(m>=3)階的B樹是滿足下列條件的m叉樹：

1、每個(gè)結(jié)點(diǎn)包括如下作用域(j, p0, k1, p1, k2, p2, ... ki, pi) 其中j是關(guān)鍵字個(gè)數(shù)，p是孩子指針

2、所有葉子結(jié)點(diǎn)在同一層上，層數(shù)等于樹高h(yuǎn)

3、每個(gè)非根結(jié)點(diǎn)包含的關(guān)鍵字個(gè)數(shù)滿足[m/2-1]<=j<=m-1

4、若樹非空，則根至少有1個(gè)關(guān)鍵字，若根非葉子，則至少有2棵子樹，至多有m棵子樹

看一個(gè)B樹的例子，針對(duì)26個(gè)英文字母的B樹可以這樣構(gòu)造：

可以看到在這棵B樹搜索英文字母復(fù)雜度只為o(m)，在數(shù)據(jù)量比較大的情況下，這樣的結(jié)構(gòu)可以大大增加查詢速度。然而有另外一種數(shù)據(jù)結(jié)構(gòu)查詢的虛度比B樹更快——散列表。Hash表的定義是這樣的：設(shè)所有可能出現(xiàn)的關(guān)鍵字集合為u，實(shí)際發(fā)生存儲(chǔ)的關(guān)鍵字記為k，而|k|比|u|小很多。散列方法是通過散列函數(shù)h將u映射到表T[0,m-1]的下標(biāo)上，這樣u中的關(guān)鍵字為變量，以h為函數(shù)運(yùn)算結(jié)果即為相應(yīng)結(jié)點(diǎn)的存儲(chǔ)地址。從而達(dá)到可以在o(1)的時(shí)間內(nèi)完成查找。

然而散列表有一個(gè)缺陷，那就是散列沖突，即兩個(gè)關(guān)鍵字通過散列函數(shù)計(jì)算出了相同的結(jié)果。設(shè)m和n分別表示散列表的長(zhǎng)度和填滿的結(jié)點(diǎn)數(shù)，n/m為散列表的填裝因子，因子越大，表示散列沖突的機(jī)會(huì)越大。
因?yàn)橛羞@樣的缺陷，所以數(shù)據(jù)庫不會(huì)使用散列表來做為索引的默認(rèn)實(shí)現(xiàn)，Mysql宣稱會(huì)根據(jù)執(zhí)行查詢格式嘗試將基于磁盤的B樹索引轉(zhuǎn)變?yōu)楹秃线m的散列索引以追求進(jìn)一步提高搜索速度。