一個小故事，看懂MySQL索引原理！
我是小M，我在卡拉巴拉星球。
我喜歡數(shù)據(jù)，我立志成為一個數(shù)據(jù)管理者。
所以我來 Y 公司應聘，聽說他們的數(shù)據(jù)量挺大的。
面試過程還是挺簡單的。
我用 007 這三個數(shù)字就輕易打敗了一堆吹噓 996 的應聘者。
此刻，我獨領(lǐng)風騷。
1
今天是我第一天上班，我筆直地坐在工位上，等著老板的寵幸。
下午兩點。
Y 老板推門而入，打著哈欠看著我：“007，你背有問題？坐得這么直？”
“老板你好，我叫小M，不是叫 007 ，007 是我對公司的熱愛，是我的畢生....”
“打住打住，看到你前面辦公桌上十幾條數(shù)據(jù)了么？”
“你的任務就是管理好它們，這些數(shù)據(jù)隨時會增加、查閱、刪除、更新的哦。”
我激動著、顫抖著回答：“Yes，Sir！”
2
花了10分鐘的時間，我把桌上的數(shù)據(jù)都掃視了一遍。
是的，沒錯，就十幾條數(shù)據(jù)我花了十分鐘。
因為這是我的第一份工作，我熱愛！
這些數(shù)據(jù)都來自一個叫 User 的部門，它們都有一樣的結(jié)構(gòu)：
這堆數(shù)據(jù)的 ID 都是有規(guī)律的，我想著就按順序把它排排坐，我用鏈表將它們相連。
每次查找數(shù)據(jù)，我從頭開始遍歷往后找就行了，有序，簡單。
我真是個小天才。
就這樣日復一日，年復一年，User 的數(shù)據(jù)在不斷的增加，現(xiàn)在已經(jīng)多達百條了。
這個鏈表也越來越長，每次老板來找我要數(shù)據(jù)，我查找的時間也越來越慢。
而且不僅是大老板，我發(fā)現(xiàn)好多小老板也來找我要數(shù)據(jù)。
我快要累死了，我的腰漸漸地也直不起來了。
3
5月1號深夜，今天是勞動節(jié)。
我依舊在公司加班。
我想不能再這樣下去了，是時候祭出我的秘密武器了！
只有在夜深人靜一個人的時候，我才能召喚它！
螺螄粉！
沒錯，就是它！
因為我發(fā)現(xiàn)，嗦了螺螄粉之后，我的腦子特別清晰，思維特別地發(fā)散。
為此，我還特意去醫(yī)院檢查了下腦子，醫(yī)生說從片子上看的話一切正常，不過從感覺上看我可能不太正常。
不管了，反正我知道，螺螄粉確實能賦予我通透的頭腦。
因為，此時我的腦子已經(jīng)開始動起來了！
有了！
我忽然回想起，在大學里面有一門叫《數(shù)據(jù)結(jié)構(gòu)》的課程里講了二分法。
現(xiàn)在有近一千條有序的數(shù)據(jù)，我把它按每十條數(shù)據(jù)分為一組，于是我吭哧吭哧的一頓操作。
(為了美觀，就畫10組)然后我再為每一組都配置一個槽，每個槽記錄了每組最大的那條記錄的地址。
這樣，我就可以通過二分法快速查找記錄啦！
假設現(xiàn)在就10組數(shù)據(jù)，然后我要找 ID 等于 12 這條數(shù)據(jù)，我就：
先計算中間槽的位置 (1+10)/2=5，通過地址找到第五組，此時第五組ID是50，12<50，所以繼續(xù)二分。(1+5)/2=3，通過地址找到第三組，此時第三組ID是30，12<30，所以繼續(xù)二分。(1+3)/2=2，通過地址找到第二組，此時第二組ID是20，12<20，所以繼續(xù)二分。(1+2)/2=1，通過地址找到第一組，此時第一組ID是10，12>10，現(xiàn)在能斷定12在第二組。從圖中看起來第一組和第二組是分開的？實際上地址是相連的，所以通過第一組最后一條數(shù)據(jù)，可以往后隨著單向鏈表遍歷，找到ID為12的這條數(shù)據(jù)。
是不是很方便？
總結(jié)的來說：
先通過二分法找到數(shù)據(jù)所在的槽。 然后再通過單向鏈表遍歷得到數(shù)據(jù)。
在數(shù)據(jù)量很大的時候這種查找方式非?？焖?！
因為查找數(shù)據(jù)的時間復雜度從O(n)幾乎簡化成了O(lgn）！
我稱之為頁目錄，我可真是個小天才呢！
4
就這樣，日復一日，年復一年。
User 的數(shù)據(jù)量還在逐日增加。
我發(fā)現(xiàn)每次查詢都需要掏出全部的名單來找。
我這小胳膊細腿的，都快抬不動了。
于是，在一個月黑風高的夜晚，我又掏出了螺螄粉。
靈光乍現(xiàn)！
我以一千個數(shù)據(jù)為一個界限來分割數(shù)據(jù)，我將每一千個數(shù)據(jù)稱之為頁。
沒錯，我又想出了 idea，我將所有數(shù)據(jù)分為一頁一頁，每頁之間用雙向鏈表相連。
這樣每次查詢，我就不需要一次把有所數(shù)據(jù)都拉出來，我可以一頁一頁翻閱過去。
當然，頁內(nèi)部還是按照剛才那樣分組訪問。
現(xiàn)在我是這樣查找數(shù)據(jù)的：
每次查數(shù)據(jù)我從第一頁開始找。 然后按照頁內(nèi)查找的方式二分去查數(shù)據(jù)，找不到就通過鏈表訪問下一頁。
因此，訪問速度并沒有變快，只是每次不需要把數(shù)據(jù)全部撈出來，只要一頁一頁的撈。
我的胳膊得到了解放。
5
公司越來越大，User 的數(shù)據(jù)爆炸性增長。
分的頁也越來越多，老板和小老板們開始抱怨了。
老板說，“我讓你找個人，你找了1小時？你今年年終獎還想不想要了！”
“唉，那個人在最后一頁，我翻的要死才翻到，我太難了！”
雖說在心里抱怨，但是我知道這樣下去不是辦法。
頭可斷血可流，年終獎不可少！
別問，問就是螺螄粉！
果不其然，螺螄粉是無敵的。
解決法子有了！
每個頁都標上獨一無二的頁號。
參考書本目錄的設計，我還專門搞了一個頁，頁里面的存儲就是目錄！
我稱它為目錄頁。
你看，這樣我就能通過這個目錄頁找到對應的數(shù)據(jù)頁。
比如：我現(xiàn)在要找 ID 為 500 的那條數(shù)據(jù)。
我遍歷目錄頁數(shù)據(jù)就可以知道該條數(shù)據(jù)在頁1。 然后就開始在頁內(nèi)通過老套路二分來查找數(shù)據(jù)！
可能有人覺得，目錄頁也是有大小的呀！裝不下怎么辦？
沒事，和數(shù)據(jù)頁一樣，新增頁唄！
可能有人會問，那目錄頁多了，查找目錄頁也會變慢的呀！
你說的沒錯，但這可難不倒我這個小聰明！
我們可以再搞一級目錄，我稱之為目中目(開個玩笑~)！
這樣，每次我從根目錄開始查詢，只要幾次查詢我就能找到想要的數(shù)據(jù)！
我稱這整一個為索引！
Y 老板看到了我的設計之后，拍了拍我的腦袋，“007，有一手啊，我看你這結(jié)構(gòu)看著像一棵樹，我這個人又喜歡吹牛 B，你看這玩意叫 B 樹怎么樣？”
“不行老板，我覺得這 B 格不夠高，要么叫B+樹吧？”
“行啊，007，年終獎我提前發(fā)給你！”
“叮鈴，支付寶到賬，0.1元。”
我：“...........”
“對了 007 ，這 User ID 太不好記了，下次我打算只告訴你名字，讓你找?！?/p>
我內(nèi)心：“@#%^&%........”
故事未完，敬請期待 ~
哈哈，第一次寫這類故事，有點意思。
這篇主要寫的是關(guān)于MySQL InnoDB 聚簇索引的設計，闡述了 MySQL 的數(shù)據(jù)到底是如何查找的。
我記得之前阿里的面試官就問過我這個問題，讓我說說數(shù)據(jù)在索引上是如何找到的，越細越好。
嘿嘿，這下知道了吧。
不過，由于故事的原因，有些描述都是不準確的，比如上面說的什么每一千條數(shù)據(jù)分為一頁。
我下面統(tǒng)一更正一下并補充一些點，看好了??！
MySQL 一頁默認16 KB，所以不是按數(shù)量的，是按總的記錄數(shù)所占的空間。 頁內(nèi)記錄是單向鏈表連接，頁之間是雙向鏈表連接。 當一頁數(shù)據(jù)存滿了之后需要進行頁分裂，也就是拆分下記錄變成兩個頁。 頁分裂操作也可能導致多個頁都滿了，比如你往一個頁中間插入數(shù)據(jù)，擠出一條數(shù)據(jù)到下一頁，然后下一頁也滿了，發(fā)生級聯(lián)，影響性能，所以建議主鍵有序，這樣不會往中間的頁插入數(shù)據(jù)。 MySQL頁內(nèi)默認會有一條最大記錄和一條最小記錄不存儲數(shù)據(jù)，就是這樣設計的，和鏈表dummy節(jié)點類似。 一頁除了存儲數(shù)據(jù)還有一些元數(shù)據(jù)，比如FileHeader、PageHeader等等，太細了講了你現(xiàn)在記得住，過兩星期也記不住，我也一樣。 一條記錄也有很多細節(jié)。
像大部分人可能知道 InnoDB B+樹索引的設計。
也能說出為什么要用 B+ 樹，但是很少會說到頁內(nèi)的二分查找。
其實這樣的設計很常見，像 Kafka 的索引也采用了二分，一般數(shù)據(jù)量大了，數(shù)據(jù)有序的情況都會上二分。
下次面試官問你，你就把這個跟他說說，面試官會覺得，嘖嘖真細啊。
對了，我上述講的只是索引結(jié)構(gòu)大致布局，想要看詳細的可以看《從根兒上理解 MySQL》，比如 FileHeader 有什么字段啊啥的。
不過，我個人覺得沒必要這么細，反正記不住，精髓掌握的即可。
如果你喜歡這樣故事類的文章，可以留言讓我知道，我之后多往這方面寫。