什么是索引
對于索引的定義你可能并不知道，但是我們?nèi)粘Ｉ钪袩o時不刻都有用到赞咙。當(dāng)你打電話給某人時，手機(jī)通訊錄會按照名字的首字母分組排序，然后你就能根據(jù)用戶名很快的找到對應(yīng)的手機(jī)號柴梆。在看書時我們想找到相關(guān)章節(jié)我們會通過書中的目錄來找到對應(yīng)的頁碼，然后直接翻到我們想看的內(nèi)容终惑。像通訊錄绍在、目錄等等這些都是索引，而索引的作用也很明顯雹有，它就是為了提高查詢的效率偿渡。你試想一下，如果讓你找到字典中的一個字件舵，你只能從第一頁開始找一只到找到這個字卸察，這個效率是有多低。
在關(guān)系型數(shù)據(jù)庫中铅祸，索引指的就是對數(shù)據(jù)庫中一列或者多列值就行排序的存儲結(jié)構(gòu)坑质。而索引的加入，能讓數(shù)據(jù)庫查詢速度得到質(zhì)的改變临梗，特別是對于數(shù)據(jù)量大的表涡扼。提高查詢效率這個是索引的作用也是我們大多數(shù)程序追求的目標(biāo)，但是索引也會帶來一些負(fù)面影響盟庞。例如索引需要占用磁盤空間吃沪，簡單的說索引也是一種數(shù)據(jù)，它也是需要存儲在服務(wù)器上什猖。同時當(dāng)原始數(shù)據(jù)進(jìn)行插入和修改時票彪，需要更新索引數(shù)據(jù)，這會導(dǎo)致程序的寫效率的下降不狮。所以如果正確的使用索引就顯得更加重要了降铸，正確合理的使用索引能大大提高我們程序的運(yùn)行效率，反之即不能提升程序的效率摇零，反而降低了系統(tǒng)寫的效率推掸。
索引類型
上面了解了什么是索引以及索引的作用，接下來我們來聊聊索引的類型。實現(xiàn)索引的方式不同從而導(dǎo)致索引的類型不同谅畅，不同的索引類型所適應(yīng)的場景也不同登渣。例如我們可以使用二叉樹來實現(xiàn)索引，使用hash來實現(xiàn)索引毡泻，還可以使用B+Tree樹來實現(xiàn)索引等等胜茧。
為什么有這么多種方式來實現(xiàn)索引呢？難道就沒有一種最好的嗎牙捉？答案是沒有絕對最好的實現(xiàn)方式竹揍，只有在某些場景中最合適的。下面我們列舉幾種在Mysql中比較常用的索引類型邪铲，需要注意的是芬位，Mysql的索引是在存儲引擎層面實現(xiàn)的，所以不同的存儲引擎在實現(xiàn)細(xì)節(jié)上會有差別带到，而且并不是所有引擎都支持所有的索引昧碉。
B+Tree
數(shù)據(jù)頁
為了讓你更好的了解B+Tree索引，我們這里先了解一下數(shù)據(jù)頁揽惹。InnoDB中管理存儲空間的最小單位就是數(shù)據(jù)頁被饿，這個大小默認(rèn)是16K。數(shù)據(jù)頁的類型有很多種搪搏，但是我們這里只關(guān)注表中數(shù)據(jù)存儲的頁類型狭握，官方把這種頁叫做索引頁。這個數(shù)據(jù)頁的結(jié)構(gòu)長啥樣呢疯溺？
上面就是一個數(shù)據(jù)頁的大致結(jié)構(gòu)论颅，實際上會比這個復(fù)雜一點，不過這里我們關(guān)注三塊囱嫩，表中的數(shù)據(jù)恃疯，空閑空間，Page Directory墨闲。表中的數(shù)據(jù)就是我們數(shù)據(jù)庫中表里面的數(shù)據(jù)今妄，表中的記錄數(shù)據(jù)按照順序被存放在這個里面≡П蹋空閑空間就是這個頁中還沒有用完的空間盾鳞，每次當(dāng)我們向表中插入一條數(shù)據(jù)，空間空間的大小就變小一點瞻离。
Page Directory是用來加快頁中數(shù)據(jù)查詢的雁仲，請注意是頁中的數(shù)據(jù)，因為頁的大小有16K琐脏，其他結(jié)構(gòu)并占不了多大的空間，大部分空間是用來存儲用戶的數(shù)據(jù)的，所以為了加快在一個頁內(nèi)搜索速度才有了Page Directory日裙，你可以簡單的認(rèn)為在一個頁內(nèi)搜索速度就是用的二分法吹艇，想想是不是查詢很快呢。
那如果我的頁里面的數(shù)據(jù)存滿了呢昂拂？不用說那就再創(chuàng)建一個新的頁唄受神。整個過程如下圖所示：
注意這里面只是一個簡圖，為了便于理解我這里省去數(shù)據(jù)頁的其他結(jié)構(gòu)格侯，只保留了用戶數(shù)據(jù)鼻听。而實際上這些頁的頭部會保存上一頁的頁號和下一頁的頁號。正是通過這些信息联四，所有的頁被一個個的串起來了撑碴，就是像雙向鏈表一樣。
下面我們用以下的表結(jié)構(gòu)來作為示例演示：
CREATE TABLE `t_student` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(255) COLLATE utf8mb4_bin NOT NULL COMMENT '名字',
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_bin;
而對應(yīng)的數(shù)據(jù)頁如下：
從上面的數(shù)據(jù)頁編號可以看出朝墩，為什么不是遞增的呢醉拓？因為在物理上這些數(shù)據(jù)頁并不是連續(xù)的，它只能保證頁內(nèi)的數(shù)據(jù)是物理上連續(xù)的收苏。再說如果表中存儲了很多數(shù)據(jù)亿卤，要保證這些頁全部是物理上連續(xù)的也不太現(xiàn)實。這里說的的連續(xù)是指在硬盤上物理連續(xù)鹿霸，因為順序I/O和隨機(jī)I/O它們的效率是不一樣的排吴，特別是針對于機(jī)械硬盤。
索引
如果現(xiàn)在我們要通過ID查詢一條數(shù)據(jù)該怎么辦呢懦鼠？如果不做任何優(yōu)化的情況下你只能從第一個數(shù)據(jù)頁開始遍歷钻哩，然后在頁內(nèi)你可以通過Page Directory快速查找你要找的數(shù)據(jù)是不是在其中。如果找到了就返回葛闷，如果沒找到繼續(xù)讀取下一個數(shù)據(jù)頁憋槐，然后查找，如此反復(fù)下去淑趾。
我們前面說過阳仔，數(shù)據(jù)頁之間在物理上不是連續(xù)的，這就會導(dǎo)致一個問題扣泊，如果數(shù)據(jù)位置靠后近范，那么會有大量的隨機(jī)I/O。
總結(jié)上面兩點我們現(xiàn)在的問題主要有兩點延蟹，第一我們無法快速的知道我們的數(shù)據(jù)存在那個數(shù)據(jù)頁中评矩，只能通過從第一個數(shù)據(jù)頁節(jié)點往后依次遍歷（注意：頁內(nèi)是能通過二分法快速定位的）。這樣也就導(dǎo)致了第二個問題阱飘，遍歷頁時大量隨機(jī)I/O斥杜。如果現(xiàn)在我們能快速找到我們的數(shù)據(jù)存在哪個頁虱颗，那是不是就能解決上面兩個問題呢？
二叉樹
如果我們將每個頁中最小值和頁號作為用戶數(shù)據(jù)蔗喂，然后把這些數(shù)據(jù)放入到頁中形成一個二叉樹忘渔，二叉樹的查詢就跟二分法一樣，那是不是我們就能提高搜索速度呢缰儿？
按照我們上面說的畦粮，我們使用二叉樹做索引將數(shù)據(jù)存好了。現(xiàn)在如果我要搜索ID為12的同學(xué)乖阵，我該怎么搜呢宣赔？首先我不需要遍歷每個頁，我從第一層節(jié)點開始搜索瞪浸，因為12最靠近7儒将，所以選右節(jié)點頁21號；然后判斷12靠近10默终，所以選頁9號椅棺，然后再頁9號里面通過二分法找找到數(shù)據(jù)12號同學(xué)小藍(lán)（頁內(nèi)查找）。
通過上面這種方法齐蔽，我們原先需要經(jīng)過讀取4次隨機(jī)I/O两疚，然后進(jìn)行4次頁內(nèi)查找才能找到，現(xiàn)在變成3次隨機(jī)I/O含滴，1次頁內(nèi)查找诱渤。從上面我們可以知道，我們查詢的消耗為樹高度+1加上頁內(nèi)查找谈况，而每次讀取頁為隨機(jī)I/O勺美。假設(shè)我們有100萬條數(shù)據(jù)，每頁能容納100條數(shù)據(jù)碑韵，對應(yīng)的二叉樹葉子節(jié)點就為1萬個赡茸，那么樹的層高至少為14層（2^14），那么每次查詢需要15次隨機(jī)I/O和一次頁內(nèi)查找祝闻。假設(shè)每次隨機(jī)I/O需要10ms占卧，那么算下來15次隨機(jī)I/O需要耗時150毫秒，想象這該得有多慢联喘，所以我們必須要降低樹的高度华蜒，這樣才能減少隨機(jī)I/O的次數(shù)。
B+Tree
上面我們知道如果想加快查詢速度還需要降低樹的高度豁遭，那么如何降低樹的高度呢叭喜？如果我們不是使用二叉樹，簡單的說就是節(jié)點不再是存儲兩個節(jié)點蓖谢，而是存儲多個節(jié)點呢捂蕴？這樣是不是就能降低樹的高度呢譬涡？
首先我們需要明白一點，我們對頁內(nèi)數(shù)據(jù)的查找肯定是比多次讀去隨機(jī)I/O要快的启绰，我們降低了樹的高度昂儒，減少了隨機(jī)I/O次數(shù)，增加了頁內(nèi)搜索的次數(shù)委可。一次頁內(nèi)搜索先比與多次隨機(jī)I/O讀取的消耗我們幾乎可以忽略不計。
按照我們之前的說法腊嗡，我們將數(shù)據(jù)如上圖存放（PS:請饒恕我沒有耐心畫全着倾，因為真的很麻煩，而且沒有合適的畫圖軟件燕少，求推薦）卡者。經(jīng)過修改之后，我們還是假設(shè)存100萬條數(shù)據(jù)客们，每頁能存放100條數(shù)據(jù)崇决。如果樹高為1，則我們能存100個頁底挫，如果樹高為2恒傻，那我們能存1萬個頁（100100）。如果樹高為3建邓，那能存100萬個頁（100100*100）盈厘。
現(xiàn)在再來分析我們的查詢消耗，我們需要3次隨機(jī)I/O加上一次頁內(nèi)查找官边。之前忘記說了沸手，我們的數(shù)據(jù)存在葉子節(jié)點，查找數(shù)據(jù)位于哪個頁需要搜索的次數(shù)為樹的高度次注簿，最后還要讀取數(shù)據(jù)所在的頁契吉，所以這又是一次隨機(jī)I/O，所以是樹的高度+1次诡渴。我們還是假設(shè)每次隨機(jī)I/O需要10ms捐晶，那么這次搜索大概需要30ms左右，相比于之前的150ms時間大大的減少了玩徊。
聚族索引
經(jīng)過上面的分析租悄，我想你對B+Tree索引有了了解。在Innodb中恩袱，我們常說到一句話即索引即數(shù)據(jù)泣棋，數(shù)據(jù)即索引，這里面講的就是聚族索引畔塔。我們將數(shù)據(jù)存放在數(shù)據(jù)頁中潭辈，這里的數(shù)據(jù)指的是表中的整行記錄鸯屿，包括了所有字段，而數(shù)據(jù)本身就是索引把敢。
聚族索引有兩個特點：使用主鍵的大小進(jìn)行記錄和頁的排序寄摆。頁內(nèi)的記錄是按照順序存放形成一個單鏈表。而各個存放用戶數(shù)據(jù)的頁也是根據(jù)頁內(nèi)主鍵大小按順序存放形成一個雙向鏈表修赞。存放頁信息的節(jié)點和存放用戶數(shù)據(jù)的節(jié)點不在同一個層級婶恼，在同一層的的頁也是根據(jù)主鍵大小形成按順序組成一個雙向鏈表。第二點就是整顆B+Tree樹存放了完整的用戶記錄柏副。
二級索引
而作為二級索引就沒有這個待遇了勾邦，它只保存了索引列和主鍵的信息。例如下面的表：
CREATE TABLE `t_member` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(64) COLLATE utf8mb4_bin DEFAULT NULL,
`age` int(11) NOT NULL,
`phone` varchar(32) COLLATE utf8mb4_bin DEFAULT NULL,
`sex` varchar(32) COLLATE utf8mb4_bin DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `name_index` (`name`) USING BTREE,
KEY `age_sex_index` (`age`,`sex`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=10001 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_bin;
在這個表結(jié)構(gòu)中存在一個主鍵索引ID割择，也就是我們前面說的聚族索引眷篇。而剩下的name_index和age_sex_index則是二級索引，所以在這個表中會有三顆B+Tree樹索引荔泳。其中name_index這顆樹頁中只存放了name和id字段信息蕉饼，而age_sex_index這棵樹中只存放了age，sex和id字段信息玛歌。
回表
例如現(xiàn)在我按名字查找用戶SQL如下:
SELECT * FROM t_member WHERE `name` = '小明';
這個查詢會使用name_index索引昧港，在該索引中查詢到數(shù)據(jù)之后就能獲取到這條數(shù)據(jù)的id，然后我們通過id再回到聚族索引中獲取到這條數(shù)據(jù)的全部信息沾鳄，這個過程我們就叫回表慨飘。
索引覆蓋
通過上面我們知道通過二級索引查詢數(shù)據(jù)是需要回表的，毫無疑問回表是有消耗的译荞，有沒有什么辦法可以優(yōu)化一下瓤的？答案是索引覆蓋。例如我通過姓名查找用戶這個需求吞歼，我只是想查找這個用戶的手機(jī)號圈膏，那么我們可以優(yōu)化一下索引，我們創(chuàng)建一個由name和phone組成的索引篙骡，然后只返回name和phone這兩個字段稽坤。
ALTER TABLE `t_member`
DROP INDEX `name_index` ,
ADD INDEX `name_phone_index` (`name`, `phone`) USING BTREE ;
我們將查詢語句修改為如下：
SELECT `name`,phone FROM t_member WHERE `name` = '小明';
在上面的查詢中，我們可以通過name_phone_index這個二級索引直接獲取到name和phone信息糯俗，所以省去了去聚族索引中再次查找的必要尿褪，從而省去了回表的消耗，這種方式我們就叫做索引覆蓋得湘。
最左匹配
現(xiàn)在我們有個查詢?nèi)缦拢?/p>
SELECT * FROM t_member WHERE phone = '15202405150';
現(xiàn)在我想問的是這個查詢能用到索引嗎杖玲？如果看懂了B+Tree索引那么你的心里一定有了答案，這個是無法用到索引的淘正。我們直接使用EXPLAIN分析結(jié)果看看：
從上面的結(jié)果可以看出確實用不到索引摆马。對于索引name_phone_index而言臼闻，它在頁中的數(shù)據(jù)長這樣：
這時候的數(shù)據(jù)的排序規(guī)則是name+phone，在索引內(nèi)能保證的是name+phone是有序的囤采，而對于phone來說并不是有序的述呐，同時對于name是有序的。如果我們通過name來查詢蕉毯，這個時候是能用到該索引的乓搬，而這個原則我們就叫做最左匹配原則。所以在創(chuàng)建索引時恕刘，索引的順序是很重要的缤谎。
根據(jù)這個原則，我們可以省去一些不必要的索引褐着。例如我們根據(jù)name創(chuàng)建了一個name_index索引，然后又根據(jù)name和phone創(chuàng)建了一個name_phone_index索引托呕，這個時候我們?nèi)サ鬾ame_index索引含蓉。因為根據(jù)最左匹配原則，通過name查詢時可以利用到索引的项郊，而name_index就沒有存在的必要了馅扣。
索引下推
例如現(xiàn)在我們有如下的查詢：
SELECT * FROM t_member WHERE `name` LIKE '陳%' AND phone = '111111'
這個查詢我們會利用到name_phone_index索引，但是這個索引使用會有一些限制着降，因為我們的查詢中存在name like '陳%'差油，這樣會導(dǎo)致我們無法使用的phone來進(jìn)行匹配了。那是不是在這個查詢中任洞，phone這個字段的索引是不是就毫無作用了呢蓄喇？答案是否定的。
這個查詢會先通過name篩選到id為1和2的記錄滿足條件交掏，然后接著根據(jù)id通過回表的方式到聚族索引中找到對應(yīng)的記錄妆偏，然后判斷phone的條件。那能不能優(yōu)化一下呢盅弛？
在Mysql5.6之前是沒有優(yōu)化的钱骂，但是在5.6及以后的版本中，Mysql會通過索引下推的****方式來****減少回表的次數(shù)挪鹏。在name_phone_index中篩選name符合要求的數(shù)據(jù)后见秽，然后會接著在該索引中判斷phone是不是滿足條件，從而減少了回表的次數(shù)讨盒。在本示例中解取，它會取消藍(lán)色線這次回表，因為在name_phone_index中就能判斷出該記錄不服和條件了催植。
哈希
哈希索引是基于哈希表實現(xiàn)的肮蛹，只有精確匹配了所有索引列的查詢才有效勺择。簡單的說，對于索引列的每行數(shù)據(jù)都會計算出一個哈希碼（hashcode）伦忠。對于相同的數(shù)據(jù)其計算出的hash碼是唯一的省核，但是需要注意的是不同的哈希碼計算出來的數(shù)據(jù)也有可能相同，這個取決于哈希算法昆码。算出哈希碼之后气忠，會在哈希表中保存一個指向原始數(shù)據(jù)的指針，然后通過該指針獲取到原始數(shù)據(jù)赋咽。而hash索引適合的是精確值的搜索旧噪，這個是它的優(yōu)勢。但是它無法使用像like查詢脓匿，范圍查詢等淘钟。
其實哈希索引跟Java中的HashMap很像，不過需要注意的是Innodb引擎是不支持hash索引的陪毡，在Mysql中Memory的默認(rèn)索引類型就是Hash米母。鑒于我們使用的最多的是Innodb引擎，這部分只是就不具體提了毡琉。
全文索引
全文索引是一種特殊的索引類型铁瞒，它查找的是文本中的關(guān)鍵字，而不是直接比較索引中的值桅滋。需要注意的是慧耍，全文檢索它并不是像like一樣的查詢，在like查詢中像'%world%'這種它是無法使用的索引的丐谋，即使像'world%'這種它能使用到索引也存在很大的限制芍碧。
考慮到該索引平常使用的較少這里面就不詳細(xì)的介紹了。因為在很多情況下有其他很好的代替產(chǎn)品笋鄙，像ElasticSearch师枣，Solr等這些能提供更好的全文檢索功能。如果項目只是需要簡單的使用全文檢索又不想引入其他組件萧落，可以考慮使用Mysql中提供的全文索引践美。
總結(jié)
總的來說，Mysql中的索引有很多種類型找岖，而且索引的實現(xiàn)是靠存儲引擎來實現(xiàn)的陨倡。即使索引都叫B+Tree它也會因為引擎的不同而有所不同，同時不同的引擎支持的索引類型也不相同许布。但實際上我們現(xiàn)在使用較多的引擎就是Innodb兴革，而Innodb中使用最多的就是B+Tree索引。所以我們在學(xué)習(xí)過程中推薦先了解Innodb相關(guān)的索引知識，然后再去學(xué)習(xí)其他引擎的索引相關(guān)知識杂曲。
