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