提到MySQL巧还，不得不提索引鞭莽，為什么要有索引呢？簡單說是為了提高查詢效率狞悲，那么索引是如何做到的呢撮抓？
我們先來回憶一下二分查找，一個排好序的數(shù)組摇锋，時間復(fù)雜度LogN丹拯。如果數(shù)據(jù)量很少，還是很快的荸恕。比如1000乖酬，logN = 10, 如果是1百萬呢，logN = 100,平均需要100次查詢融求，是不是很可怕咬像。我們知道每次查詢都是從磁盤IO操作，而磁盤IO操作是很慢的生宛，查詢一個數(shù)據(jù)需要100次IO县昂，也是醉了。那該怎么辦陷舅？
是不是可以向上提煉一層倒彰，比如你要在一本書翻到第8章的內(nèi)容，如果你從書本中間找一頁開始莱睁，用二分法遞歸不斷查找到第八章開頭在200頁待讳。換個方法呢芒澜，你先去看看目錄，目錄雖然只有短短幾頁创淡，但是詳細(xì)記錄的每章的位置痴晦，這樣你翻一下目錄，就知道第八章在200頁琳彩，然后直接翻到200也就可以誊酌，是不是加快了查詢速度。
還有一個問題就是范圍查找露乏，要在所有數(shù)據(jù)找到（a,b）區(qū)間的開頭和結(jié)尾术辐，效率也是低效的。
So how to do施无？先來了解一種數(shù)據(jù)結(jié)構(gòu)辉词，跳躍表。
跳躍表
1.1 什么是跳躍表
????對于一個單鏈表來講猾骡，即便鏈表中存儲的數(shù)據(jù)是有序的瑞躺，如果我們要想在其中查找某個數(shù)據(jù)，也只能從頭到尾遍歷鏈表兴想。這樣查找效率就會很低幢哨，時間復(fù)雜度會很高，是 O(n)嫂便。
如果我們想要提高其查找效率捞镰，可以考慮在鏈表上建索引的方式。每兩個結(jié)點提取一個結(jié)點到上一級毙替，我們把抽出來的那一級叫作索引岸售。
????這個時候，我們假設(shè)要查找節(jié)點8厂画，我們可以先在索引層遍歷凸丸，當(dāng)遍歷到索引層中值為 7 的結(jié)點時，發(fā)現(xiàn)下一個節(jié)點是9袱院，那么要查找的節(jié)點8肯定就在這兩個節(jié)點之間屎慢。我們下降到鏈表層繼續(xù)遍歷就找到了8這個節(jié)點。原先我們在單鏈表中找到8這個節(jié)點要遍歷8個節(jié)點忽洛，而現(xiàn)在有了一級索引后只需要遍歷五個節(jié)點腻惠。
????從這個例子里，我們看出欲虚，加來一層索引之后集灌，查找一個結(jié)點需要遍的結(jié)點個數(shù)減少了，也就是說查找效率提高了苍在，同理再加一級索引绝页。
????從圖中我們可以看出，查找效率又有提升寂恬。在例子中我們的數(shù)據(jù)很少续誉，當(dāng)有大量的數(shù)據(jù)時，我們可以增加多級索引初肉，其查找效率可以得到明顯提升酷鸦。
像這種鏈表加多級索引的結(jié)構(gòu)，就是跳躍表牙咏！
以上內(nèi)容來自：https://www.cnblogs.com/hunternet/p/11248192.html
跳躍表是Redis使用的數(shù)據(jù)結(jié)構(gòu)臼隔，因為數(shù)據(jù)都在內(nèi)存中，但是這個模式不適合文件存儲妄壶，不過MySQL的實現(xiàn)也是類似的結(jié)構(gòu)摔握，我們稱之為B+樹。
非葉子節(jié)點存放的是目錄丁寄，葉子節(jié)點存儲具體數(shù)據(jù)氨淌。
在MySQL中，數(shù)據(jù)是以頁為單位進(jìn)行管理的伊磺，就像一本書盛正，一章一章地排版。默認(rèn)一頁大小16KB屑埋，16KB是可以存儲很多數(shù)據(jù)的豪筝，不過我們還是簡單起見，假設(shè)一頁只有3條數(shù)據(jù)摘能，簡單看一下MySQL頁的結(jié)構(gòu)续崖。
建表語句如下：
CREATE TABLE index_demo(
? ? ? ? c1 INT,
? ? ? ? ?c2 INT,
? ? ? ? ?c3 CHAR(1),
? ? ? ? ?PRIMARY KEY(c1)
? ? ?) ;
INSERT INTO index_demo VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');
插入幾條數(shù)據(jù)后，一頁如果只有3個數(shù)據(jù)团搞，如下：
頁中的記錄是用鏈表前后相連的袜刷，每個記錄都有一個記錄類型。
record_type分類
0：普通的用戶記錄
1：目錄項記錄
2：最小記錄
3：最大記錄
當(dāng)數(shù)據(jù)量增加后莺丑，索引是這樣的：
不論是存放用戶記錄的數(shù)據(jù)頁著蟹，還是存放目錄項記錄的數(shù)據(jù)頁，我們都把它們存放到B+樹這個數(shù)據(jù)結(jié)構(gòu)中了梢莽，所以我們也稱這些數(shù)據(jù)頁為節(jié)點萧豆。從圖中可以看出來，我們的實際用戶記錄其實都存放在B+樹的最底層的節(jié)點上昏名，這些節(jié)點也被稱為葉子節(jié)點或葉節(jié)點涮雷，其余用來存放目錄項的節(jié)點稱為非葉子節(jié)點或者內(nèi)節(jié)點，其中B+樹最上邊的那個節(jié)點也稱為根節(jié)點轻局。
從圖中可以看出來洪鸭，一個B+樹的節(jié)點其實可以分成好多層样刷，假設(shè)所有存放用戶記錄的葉子節(jié)點代表的數(shù)據(jù)頁可以存放100條用戶記錄，所有存放目錄項記錄的內(nèi)節(jié)點代表的數(shù)據(jù)頁可以存放1000條目錄項記錄览爵，那么：
如果B+樹只有1層置鼻，也就是只有1個用于存放用戶記錄的節(jié)點，最多能存放100條記錄蜓竹。
如果B+樹有2層箕母，最多能存放1000×100=100000條記錄。
如果B+樹有3層俱济，最多能存放1000×1000×100=100000000條記錄嘶是。
如果B+樹有4層，最多能存放1000×1000×1000×100=100000000000條記錄蛛碌。哇咔咔～這么多的記錄Ｄ衾！蔚携！
你的表里能存放100000000000條記錄么授帕？所以一般情況下，我們用到的B+樹都不會超過4層浮梢，那我們通過主鍵值去查找某條記錄最多只需要做4個頁面內(nèi)的查找（查找3個目錄項頁和一個用戶記錄頁）跛十，又因為在每個頁面內(nèi)有所謂的Page Directory（頁目錄），所以在頁面內(nèi)也可以通過二分法實現(xiàn)快速定位記錄
索引分類
索引分為聚簇索引和二級索引（官方鏈接：https://dev.mysql.com/doc/refman/5.7/en/innodb-index-types.html）秕硝，強烈建議大家讀讀芥映，不多，就幾段远豺，官方資料是我們學(xué)習(xí)最好的參考奈偏。簡單說，聚簇索引包含主鍵和所有列數(shù)據(jù)躯护，二級索引只包含索引列的內(nèi)容和主鍵的id惊来。
上面示例的索引就是聚簇索引。我們在看一下建表語句：
CREATE TABLE index_demo(
? ? ? ? c1 INT,
? ? ? ? ?c2 INT,
? ? ? ? ?c3 CHAR(1),
? ? ? ? ?PRIMARY KEY(c1)
? ? ?) ;
為c2列建立索引棺滞，二級索引的效果如下：
聯(lián)合索引
為c2裁蚁、c3建立聯(lián)合索引，索引
下面我們執(zhí)行查詢：
select * from index_demo where id = 1
這時候继准，id是主鍵索引枉证，直接掃描主鍵索引得到數(shù)據(jù)
select * from index_demo where c2 = 2
c2列有二級索引，使用該索引搜索到c2 = 2 的列移必，但是索引只有主鍵值室谚，無法獲得其他列的值，怎么辦呢？這個時候就要使用主鍵id去主鍵索引查詢自己需要的數(shù)據(jù)秒赤，這個過程叫作回表猪瞬。
如果c2=2的數(shù)據(jù)非常多，需要回表多次入篮，mysql做了優(yōu)化陈瘦，MRR.如果沒有MRR，查詢回表是隨機的崎弃，但是有的話就是放在緩存，然后順序讀含潘。
https://dev.mysql.com/doc/refman/5.7/en/mrr-optimization.html
如果不是select *饲做，而是select c2 from? index_demo where c2 = 2,這個時候查詢的列c2，索引就有這個列遏弱，這個時候是不是不用回表了盆均，索引就能得到值，這種情況叫索引覆蓋漱逸。
主鍵索引泪姨、二級索引、回表饰抒、MRR優(yōu)化肮砾、索引覆蓋。相信大家已經(jīng)掌握了
