什么是索引

數(shù)據(jù)庫索引是我們每個(gè)開發(fā)人員既熟悉又陌生的東西英岭，幾乎所有的業(yè)務(wù)系統(tǒng)都要與索引打交道飒炎，如果數(shù)據(jù)庫查詢慢了册赛，第一時(shí)間想到的也是添加一個(gè)索引試試谁不。但是大多數(shù)人并沒有去深究這個(gè)神奇的東西究竟是如何起作用的坐梯。

其實(shí)索引就像一本書的目錄，沒有目錄的書刹帕，我們只能一頁一頁的往下翻吵血，邊看邊找自己感興趣的內(nèi)容。而有了目錄偷溺，我們想看書的哪一部分只需要翻翻目錄的介紹蹋辅，找到對(duì)應(yīng)的頁碼，然后就可以快速的翻到感興趣的部分了挫掏。數(shù)據(jù)庫也是同樣的道理侦另，數(shù)據(jù)通常是保存到磁盤中的（ssd或者h(yuǎn)dd），而磁盤的讀取速度遠(yuǎn)遠(yuǎn)不如內(nèi)存那么快尉共。數(shù)據(jù)量較大的情況下褒傅，如果不能定位數(shù)據(jù)的大致位置，而采用順序掃描的方式去查找匹配的數(shù)據(jù)袄友，那用戶每次操作后等待結(jié)果的時(shí)間大概都能打一把王者了殿托，這個(gè)時(shí)候就需要索引出場(chǎng)了。

索引的原理其實(shí)很簡(jiǎn)單剧蚣，就是通過某種數(shù)據(jù)結(jié)構(gòu)把要查詢的關(guān)鍵字與實(shí)際的數(shù)據(jù)存儲(chǔ)位置進(jìn)行映射支竹。這樣我們?cè)谒阉鲾?shù)據(jù)的時(shí)候，就不是直接把數(shù)據(jù)逐條從磁盤上查出來和關(guān)鍵字進(jìn)行比較券敌，而是先從索引中查找到這個(gè)關(guān)鍵字唾戚，然后得到關(guān)鍵字所映射的數(shù)據(jù)記錄的實(shí)際位置，再根據(jù)存儲(chǔ)位置到磁盤上去讀取相應(yīng)的記錄待诅。索引都是排好序的叹坦，而且索引的部分結(jié)構(gòu)可以加載到內(nèi)存中，這些都能極大的提升檢索的速度卑雁。

基于BTree的索引實(shí)現(xiàn)

原理上很簡(jiǎn)單募书，但是要實(shí)現(xiàn)一個(gè)高效的數(shù)據(jù)索引并不容易。目前主流的關(guān)系型數(shù)據(jù)庫基本還是使用Btree(也叫B-Tree)的各種變形結(jié)構(gòu)來實(shí)現(xiàn)數(shù)據(jù)索引的测蹲。顧名思義莹捡，btree也是一種樹形結(jié)構(gòu)，中文名稱叫做平衡多路查找樹扣甲，結(jié)構(gòu)類似于下圖：

Btree數(shù)據(jù)庫結(jié)構(gòu)圖 (1).png

Btree的每個(gè)節(jié)點(diǎn)主要包含三類信息：數(shù)據(jù)的關(guān)鍵字（key）篮赢，數(shù)據(jù)本身齿椅，指向子節(jié)點(diǎn)的指針。key與指針交替間隔的启泣，而且從圖上可以很直觀的看出涣脚，所有的key都是從左到右升序排列的，每個(gè)key在整個(gè)Btree中只會(huì)出現(xiàn)一次寥茫。

在Mysql的索引實(shí)現(xiàn)中遣蚀，每個(gè)Btree的節(jié)點(diǎn)存儲(chǔ)到一個(gè)頁（Page）中,這是Mysql磁盤管理的最小單位，InnoDB 讀取數(shù)據(jù)時(shí)必須以Page為單位整體讀出來放到內(nèi)存中纱耻。我們以查詢關(guān)鍵字10為例芭梯，大致的過程如下：

1. 根據(jù)根節(jié)點(diǎn)找到Page1，讀入內(nèi)存弄喘【链【磁盤I/O操作第1次】
2. 比較關(guān)鍵字10在區(qū)間<17，找到Page2的指針P1限次。
3. 根據(jù)P1指針找到Page2芒涡，讀入內(nèi)存÷袈【磁盤I/O操作第2次】
4. 比較關(guān)鍵字29在區(qū)間（8,12）费尽，找到Page6的指針P2。
5. 根據(jù)P2指針找到Page6羊始，讀入內(nèi)存旱幼。【磁盤I/O操作第3次】
6. 在Page6中的關(guān)鍵字列表中找到關(guān)鍵字10以及對(duì)應(yīng)的數(shù)據(jù)突委。

整個(gè)過程只需要3次磁盤IO操作柏卤，3次內(nèi)存操作，效率比逐條讀取比對(duì)的方式提升了很多匀油。

B+Tree的優(yōu)化

Btree能夠極大的提升數(shù)據(jù)查詢的效率缘缚，但仍然存在一些缺點(diǎn)，比如：數(shù)據(jù)和關(guān)鍵字都存儲(chǔ)到節(jié)點(diǎn)中敌蚜，占用的空間較大桥滨，導(dǎo)致單個(gè)節(jié)點(diǎn)能容納的Key的數(shù)量較少，每次能讀入內(nèi)存的key也就越少弛车，這樣可能會(huì)影響搜索效率齐媒；另外Btree的查詢效率頁不穩(wěn)定，如果關(guān)鍵字位于上層節(jié)點(diǎn)纷跛，則可以很快的返回結(jié)果喻括，但關(guān)鍵字如果在更深的節(jié)點(diǎn)上，則查詢的效率會(huì)大大降低贫奠。針對(duì)這些問題唬血，人們又對(duì)Btree進(jìn)行一些細(xì)節(jié)上的優(yōu)化望蜡，使其能夠更加滿足數(shù)據(jù)庫索引的需求，這就是B+Tree刁品。Mysql InnoDB的索引就是采用B+Tree實(shí)現(xiàn)的：

B+tree數(shù)據(jù)庫結(jié)構(gòu)圖.png

B+Tree的改進(jìn)主要有3點(diǎn)：

1. B+Tree的非葉子節(jié)點(diǎn)并不存儲(chǔ)數(shù)據(jù)本身泣特，只存儲(chǔ)Key和子節(jié)點(diǎn)指針浩姥。因此單個(gè)節(jié)點(diǎn)可以存儲(chǔ)更多的Key挑随，一次性讀入內(nèi)存的關(guān)鍵字也就越多，相對(duì)IO讀寫次數(shù)就降低了勒叠。

2. B+Tree的葉子節(jié)點(diǎn)包含了所有的Key和數(shù)據(jù)兜挨，而且每個(gè)葉子節(jié)點(diǎn)都存儲(chǔ)了前后兩個(gè)葉子節(jié)點(diǎn)的位置指針，這樣在區(qū)間查詢時(shí)可以直接從葉子節(jié)點(diǎn)進(jìn)行遍歷眯分，跳過上層的根節(jié)點(diǎn)拌汇，可以提高區(qū)間查詢的效率。

3. B+Tree的Key可能出現(xiàn)在多個(gè)節(jié)點(diǎn)中弊决，而Btree的Key只會(huì)出現(xiàn)在唯一的一個(gè)節(jié)點(diǎn)噪舀，由于B+Tree的數(shù)據(jù)都只存儲(chǔ)在葉子結(jié)點(diǎn)中，所以不管查詢什么Key飘诗，最終都需要沿著根節(jié)點(diǎn)逐次搜索到葉子節(jié)點(diǎn)才能找到數(shù)據(jù)与倡，這樣可以避免不同的Key查詢效率差異過大的問題。

聚簇索引(Clustered Index)和非聚簇索引 (Non- Clustered Index)

聚簇索引就是數(shù)據(jù)和索引本身是存儲(chǔ)在一起（物理上的）里烦，比如上面B+Tree的示意圖咏窿，黃色小格里面的Data就是數(shù)據(jù)本身抹估；聚簇索引的查詢效率肯定是最高的，只要找到了數(shù)據(jù)就可以直接讀取了净响，不需要再進(jìn)行任何跳轉(zhuǎn)。但是因?yàn)閿?shù)據(jù)只能存儲(chǔ)在一個(gè)位置喳瓣，所以每張表的聚簇索引肯定也就只有一個(gè)馋贤。在Mysql InnoDB中，主鍵索引就是聚簇索引畏陕，不能修改（沒有主鍵的表就看第一個(gè)唯一索引配乓，都沒有Mysql就自己生成一個(gè)），所以主鍵查詢的效率是最高的蹭秋。和數(shù)據(jù)的存儲(chǔ)位置無關(guān)的索引都是非聚簇索引（也叫二級(jí)索引）扰付，這個(gè)時(shí)候葉子節(jié)點(diǎn)里面存儲(chǔ)的Data實(shí)際上是數(shù)據(jù)的主鍵（而不是數(shù)據(jù)本身），所以非聚簇索引的查詢會(huì)多一個(gè)步驟仁讨，找到數(shù)據(jù)主鍵之后還要到聚簇索引中去查找實(shí)際的數(shù)據(jù)羽莺。

主鍵的選擇

根據(jù)以上對(duì)索引結(jié)構(gòu)的分析，我們就能了解一些Mysql InnoDB數(shù)據(jù)表主鍵的一些限制：

1. 不要用過長(zhǎng)的字段作為主鍵：因?yàn)樗械亩?jí)索引的data區(qū)域都是存放到數(shù)據(jù)記錄的主鍵洞豁，如果主鍵過長(zhǎng)會(huì)導(dǎo)致二級(jí)索引的空間占用變大盐固，影響查詢效率荒给；
2. 盡量使用單調(diào)自增的字段作為主鍵：主鍵索引本質(zhì)上是一棵B+Tree，key是有序排列的刁卜；如果主鍵是單調(diào)自增的志电，那么產(chǎn)生新數(shù)據(jù)的時(shí)候，記錄就會(huì)順序添加到當(dāng)前索引節(jié)點(diǎn)的后續(xù)位置蛔趴，當(dāng)一頁寫滿挑辆，就會(huì)自動(dòng)開辟一個(gè)新的頁，如圖：
   
   新增數(shù)據(jù)時(shí)B+Tree分裂示意圖.png
   
   這樣可以形成一個(gè)緊湊的存儲(chǔ)結(jié)構(gòu)（沒有磁盤碎片）孝情，也無需移到其它已有的節(jié)點(diǎn)鱼蝉，索引的插入效率較高；反之箫荡，如果主鍵是類似于身份證號(hào)碼那樣的非自增結(jié)構(gòu)魁亦，索引在插入時(shí)會(huì)產(chǎn)生大量額外的節(jié)點(diǎn)移動(dòng)開銷，導(dǎo)致大量的磁盤碎片羔挡，而且已被緩存的索引頁可能會(huì)被強(qiáng)制刷新洁奈，影響插入效率。

使用索引的一些注意事項(xiàng)：

1. 索引不能解決一切問題绞灼，好的索引會(huì)提高查詢效率利术，但同時(shí)也會(huì)增加插入數(shù)據(jù)的開銷，需要綜合考慮系統(tǒng)的性能瓶頸來進(jìn)行設(shè)置镀赌；

2. 如果需要索引的列是一個(gè)很長(zhǎng)的字符列時(shí)氯哮，可以考慮使用前綴索引，前綴的長(zhǎng)度計(jì)算需要綜合實(shí)際的數(shù)據(jù)來考慮商佛。例如：

ALTER TABLE `city_demo` ADD KEY `idx_city` (`city`(7))

3. SQL查詢時(shí)喉钢，如果索引列必須要是獨(dú)立的，否則無法使用索引良姆，索引肠虽。“ 獨(dú)立的列” 是指索引列不能是表達(dá)式的一部分玛追， 也不能是函數(shù)的參數(shù)税课。例如下面的情況都無法使用索引：

SELECT actor_id FROM sakila.actor WHERE actor_id + 1 = 5;

SELECT ... WHERE TO_DAYS( CURRENT_DATE) - TO_DAYS( date_col) <= 10;

4. 復(fù)合索引的索引列序非常重要：建立復(fù)合索引時(shí)，多個(gè)字段的排列順序是能夠影響索引是否生效的重要問題痊剖。簡(jiǎn)單的說韩玩，復(fù)合索引是按照從左到右的順序生效的，如果查詢條件中缺少中間的部分字段陆馁，則僅左邊能夠匹配的索引部分可以生效找颓。假設(shè)有一個(gè)復(fù)合索引（a,b,c），則有以下的規(guī)則：

select * from exp_tbl  where a=3  and b=45 and c=5 --這種三個(gè)索引順序使用中間沒有中斷叮贩，全部發(fā)揮作用佛析；
select * from exp_tbl  where a=3  and c=5 -- 這種情況下b就是斷點(diǎn)，a發(fā)揮了效果彪蓬，c沒有效果
select * from exp_tbl  where b=3  and c=4 -- 這種情況下a就是斷點(diǎn)寸莫，在a后面的索引都沒有發(fā)揮作用，這種寫法聯(lián)合索引沒有發(fā)揮任何效果档冬；
select * from exp_tbl  where b=45 and a=3 and c=5 -- 和第一種情況是一樣的膘茎，條件書寫的順序無關(guān)

5. 如果一個(gè)查詢中條件經(jīng)常都是不固定的（比如用戶輸入條件進(jìn)行查詢，這種情況很常見）捣郊，就不太好設(shè)置復(fù)合索引了辽狈，還有一種方式就是把潛在的可能成為條件的數(shù)據(jù)列都設(shè)置成單列索引。Mysql從5.1開始支持index merge技術(shù)（索引合并）呛牲，簡(jiǎn)單的說就是如果一個(gè)查詢有個(gè)多個(gè)條件，在沒有合適的復(fù)合索引可以使用的情況下驮配，Mysql會(huì)同時(shí)使用多個(gè)單列索引進(jìn)行掃描娘扩，再把掃描的結(jié)果進(jìn)行合并（并集，交集）壮锻。但索引合并在性能是可能是不可控的（并集琐旁，交集操作可能消耗大量的資源），所以使用時(shí)需要慎重猜绣，如果可能的話使用復(fù)合索引仍然是最佳的選擇灰殴。