索引有什么用？

在生活中當(dāng)我們遇到不認(rèn)識(shí)的字的時(shí)候，可以通過(guò)漢語(yǔ)字典，先通過(guò)字的部首，根據(jù)部首的筆畫(huà)在《部首目錄》中找到這個(gè)部首及它在《檢字表》中的頁(yè)碼。再數(shù)清這個(gè)字余下部分的筆畫(huà)，就在部首下找到相應(yīng)的筆畫(huà)欄，找到要查的字及它的頁(yè)碼。或者通過(guò)漢語(yǔ)拼音音節(jié)查字法（這里就不多介紹了）也可以快速地在上萬(wàn)個(gè)字的詞典中找到對(duì)應(yīng)的字。
那么在mysql數(shù)據(jù)中，也存在跟字典一樣的索引，可以高效地在上萬(wàn)條的數(shù)據(jù)中，很快地找到你想要的數(shù)據(jù)。只不過(guò)他們的索引方式不同而已，查詢的效率也不一樣，那么我們就來(lái)看看mysql的一些索引，選擇合適的索引，讓你的查詢更快。

基礎(chǔ)·索引的常見(jiàn)模型

這里我先給你介紹三種常見(jiàn)、也比較簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，它們分別是哈希表、有序數(shù)組和搜索樹(shù)。

• 哈希表
  哈希表是以（key-value）的形式存儲(chǔ)的一種數(shù)據(jù)結(jié)構(gòu)，在key不沖突的情況下找value的時(shí)間復(fù)雜度為O(1)。但是實(shí)際中數(shù)據(jù)量越大，key重復(fù)的幾率就越高，這個(gè)時(shí)候重復(fù)的key，所對(duì)應(yīng)的value也會(huì)形成一個(gè)鏈表，鏈表的時(shí)間復(fù)雜度就是O(n)了。但這都不算是他最大缺點(diǎn)。最大的不足之處就是做區(qū)間查找的時(shí)候就很慢,因?yàn)樗皇怯行虻?。所以哈希表這種結(jié)構(gòu)適用于只有等值查詢的場(chǎng)景。
• 有序數(shù)組
  有序數(shù)組在等值查詢和范圍查詢場(chǎng)景中的性能就都非常優(yōu)秀。
  拿有序的訂單號(hào)舉個(gè)例子：
  想要找到某個(gè)xxx007的訂單號(hào)所對(duì)應(yīng)的信息，我們只要通過(guò)2分法（時(shí)間復(fù)雜度O(log(N))），就可以快速的找到你想要的數(shù)據(jù)。如果是[xxx007,xxx009]這個(gè)范圍的數(shù)據(jù)也一樣先通過(guò)2分法找到xxx007的訂單，如果訂單不存在那就往右遍歷一個(gè)，然后直到查到第一個(gè)比xxx009大的訂單號(hào)就可以退出查找，得到你想要的區(qū)間數(shù)據(jù)。
  但是有序數(shù)組也有缺點(diǎn)。比如在新增數(shù)據(jù)的時(shí)候，這個(gè)數(shù)據(jù)大小在中間，這個(gè)時(shí)候就必須要挪動(dòng)大量的記錄位置。所以，有序數(shù)組索引只適用于靜態(tài)存儲(chǔ)引擎。

• 搜索樹(shù)
  二叉樹(shù)是一個(gè)經(jīng)典的數(shù)據(jù)結(jié)構(gòu)。我們知道它的時(shí)間復(fù)雜度是O(log(N))。為了維持這個(gè)時(shí)間復(fù)雜度，我們需要將它整成一顆平衡二叉樹(shù)，因此更新的時(shí)間復(fù)雜度也是O(log(N))。
  但是如果樹(shù)高為10，一次查詢可能需要訪問(wèn)20個(gè)數(shù)據(jù)塊。在機(jī)械硬盤(pán)時(shí)代，從磁盤(pán)隨機(jī)讀一個(gè)數(shù)據(jù)塊需要10 ms左右的尋址時(shí)間，這就很慢了。為了增加它的效率，我們可以就得讓查詢?cè)L問(wèn)盡量少的數(shù)據(jù)塊，于是可以把這個(gè)二叉樹(shù)改為n叉樹(shù)，n取決于數(shù)據(jù)塊大小。以InnoDB的一個(gè)整數(shù)字段索引為例，這個(gè)N差不多是1200。這棵樹(shù)高是4的時(shí)候，就可以存1200的3次方個(gè)值，這已經(jīng)17億了。由于根節(jié)點(diǎn)常駐內(nèi)存所以在這么大量的數(shù)據(jù)下只需要訪問(wèn)3次磁盤(pán)。

  
  
  這是一顆3叉樹(shù)

B-Tree和B+Tree

目前大部分?jǐn)?shù)據(jù)庫(kù)系統(tǒng)及文件系統(tǒng)都采用B-Tree或其變種B+Tree作為索引結(jié)構(gòu)

B-Tree

B+Tree

先上圖可以看到這2種樹(shù)都是上面所說(shuō)的n叉樹(shù)，但是它們也有區(qū)別的。

• B+樹(shù)的數(shù)據(jù)只存在葉子節(jié)點(diǎn)，而B(niǎo)-樹(shù)的數(shù)據(jù)存在于每個(gè)節(jié)點(diǎn)。
• B+樹(shù)給所有葉子節(jié)點(diǎn)增加了一個(gè)指針讓他們首尾相連（沒(méi)錯(cuò)，是不是想到了上面的有序數(shù)組，就是為了區(qū)間查詢）

所以B-樹(shù)找到索引key就能立馬找到數(shù)據(jù)了，但是B+樹(shù)是需要到跟節(jié)點(diǎn)下才能拿到數(shù)據(jù)，所以說(shuō)同樣的內(nèi)存大小，或者說(shuō)同樣的頁(yè)大小，B+樹(shù)比B-樹(shù)能放更多的數(shù)據(jù)。將data放到外部存儲(chǔ)即可比如磁盤(pán)。
看到這里，我想大家就能知道了，是的，Mysql的索引采用的就是B+樹(shù)的方式。

MyISAM和InnoDB

id | age | name

假如有一張User表，有上面3個(gè)字段。id為主鍵索引，age為輔助索引,name也為輔助索引。那么來(lái)看2種索引的實(shí)現(xiàn)圖

MyISAM根據(jù)id找

MyISAM根據(jù)age找

InnoDB根據(jù)id找

InnoDB根據(jù)name找

可以看到MyISAM無(wú)論是根據(jù)主索引找還是輔助索引找，都能在葉子節(jié)點(diǎn)找到地址，然后根據(jù)地址直接找到對(duì)應(yīng)磁盤(pán)的完整數(shù)據(jù)。
而InnoDB通過(guò)id找也可以。但是當(dāng)InnoDB通過(guò)name這個(gè)輔助索引去找，只能找到對(duì)應(yīng)的id，然后再通過(guò)id再去找到對(duì)應(yīng)的記錄數(shù)據(jù)。

聚集索引和非聚集索引

可以看到葉節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄。這種索引叫做聚集索引。因?yàn)镮nnoDB的數(shù)據(jù)文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵（MyISAM可以沒(méi)有），如果沒(méi)有顯式指定，則MySQL系統(tǒng)會(huì)自動(dòng)選擇一個(gè)可以唯一標(biāo)識(shí)數(shù)據(jù)記錄的列作為主鍵，如果不存在這種列，則MySQL自動(dòng)為InnoDB表生成一個(gè)隱含字段作為主鍵，這個(gè)字段長(zhǎng)度為6個(gè)字節(jié)，類(lèi)型為長(zhǎng)整形，相應(yīng)地我們稱(chēng)MyISAM為“非聚集”索引。所以我們要盡量地縮短主鍵id，防止輔助索引過(guò)大。還有就是最好采用有規(guī)律的自增id，防止id插入的時(shí)候調(diào)整B+樹(shù)的節(jié)點(diǎn)位置。

MyISAM和InnoDB一些其他區(qū)別：

1. 是否支持行級(jí)鎖 : MyISAM 只有表級(jí)鎖(table-level locking)，而InnoDB 支持行級(jí)鎖(row-level locking)和表級(jí)鎖,默認(rèn)為行級(jí)鎖。
2. 是否支持事務(wù)和崩潰后的安全恢復(fù)：MyISAM不提供事務(wù)，所以強(qiáng)調(diào)的是性能，每次查詢具有原子性,其執(zhí)行比InnoDB類(lèi)型更快。InnoDB 提供事務(wù)支持事務(wù)，外部鍵等高級(jí)數(shù)據(jù)庫(kù)功能。具有事務(wù)(commit)、回滾(rollback)和崩潰修復(fù)能力(crash recovery capabilities)的事務(wù)安全(transaction-safe (ACID compliant))型表。
3. 是否支持外鍵： MyISAM不支持，而InnoDB支持
4. 是否支持MVCC ：僅 InnoDB 支持。應(yīng)對(duì)高并發(fā)事務(wù), MVCC比單純的加鎖更高效;MVCC只在 READ COMMITTED 和 REPEATABLE READ 兩個(gè)隔離級(jí)別下工作;MVCC可以使用 樂(lè)觀(optimistic)鎖 和 悲觀(pessimistic)鎖來(lái)實(shí)現(xiàn);各數(shù)據(jù)庫(kù)中MVCC實(shí)現(xiàn)并不統(tǒng)一

覆蓋索引

針對(duì)InnoDB的name這種2次查詢才能找到完整數(shù)據(jù)的方式，我們叫做回表查詢。如果是個(gè)通過(guò)輔助索引的范圍查找，那么回表查的次數(shù)是不是會(huì)有點(diǎn)過(guò)分了呢？我們是否有解決方法呢？

select id from User where age = 18;

哈哈，因?yàn)镮nnoDB輔助上是能拿到主鍵索引的，所以這么查，我們就不需要回表了。因?yàn)橛械臉I(yè)務(wù)場(chǎng)景我們可能只需要找到一個(gè)id就行了“覆蓋”了我們的需求，我們稱(chēng)為覆蓋索引。

最左前綴原則

1）select id from User where name like 'A%';這條SQL是走索引的
2）select id from User where name like '%A';這條SQL不走索引的

這個(gè)在我們建立聯(lián)合索引的時(shí)候很有用：

• 當(dāng)你想建（age,name）的聯(lián)合索引時(shí)，還想建一個(gè)（name）索引。這時(shí)我們只要調(diào)整聯(lián)合索引的順序?yàn)椋╪ame,age）,就可以省一個(gè)（name）的索引空間下來(lái)。
• 但是當(dāng)你的查詢基于（name）、（age）各自查詢又有（age,name）聯(lián)合查詢的時(shí)候怎么建索引呢?；谏厦婺且粭l規(guī)則，然后age一般比name短，所以我們可以（name,age）,(age) 這么建，是不是又能省空間了。

索引下推

id | name（有索引） | sex（無(wú)索引）

當(dāng)查詢一個(gè)名字為”阿“開(kāi)頭的，性別為男時(shí)

select * from User where name like '阿%' and sex = 1;

這樣子我們可以先通過(guò)索引快速找到’阿‘開(kāi)頭的所有同學(xué)。在通過(guò)sex條件判斷即可

在MySQL 5.6之前，只能從ID3開(kāi)始一個(gè)個(gè)回表。到主鍵索引上找出數(shù)據(jù)行，再對(duì)比字段值。
而MySQL 5.6 引入的索引下推優(yōu)化（index condition pushdown)， 可以在索引遍歷過(guò)程中，對(duì)索引中包含的字段先做判斷，直接過(guò)濾掉不滿足條件的記錄，減少回表次數(shù)。