我是小M，我在卡拉巴拉星球。

我喜歡數(shù)據(jù)，我立志成為一個數(shù)據(jù)管理者。

所以我來 Y 公司應(yīng)聘，聽說他們的數(shù)據(jù)量挺大的。

面試過程還是挺簡單的。

我用 007 這三個數(shù)字就輕易打敗了一堆吹噓 996 的應(yīng)聘者。

此刻，我獨(dú)領(lǐng)風(fēng)騷。

1

今天是我第一天上班，我筆直地坐在工位上，等著老板的寵幸。

下午兩點(diǎn)。

Y 老板推門而入，打著哈欠看著我：“007，你背有問題？坐得這么直？”

“老板你好，我叫小M，不是叫 007 ，007 是我對公司的熱愛，是我的畢生....”

“打住打住，看到你前面辦公桌上十幾條數(shù)據(jù)了么？”

“你的任務(wù)就是管理好它們，這些數(shù)據(jù)隨時會增加、查閱、刪除、更新的哦。”

我激動著、顫抖著回答：“Yes，Sir！”

2

花了10分鐘的時間，我把桌上的數(shù)據(jù)都掃視了一遍。

是的，沒錯，就十幾條數(shù)據(jù)我花了十分鐘。

因為這是我的第一份工作，我熱愛！

這些數(shù)據(jù)都來自一個叫 User 的部門，它們都有一樣的結(jié)構(gòu)：

這堆數(shù)據(jù)的 ID 都是有規(guī)律的，我想著就按順序把它排排坐，我用鏈表將它們相連。

每次查找數(shù)據(jù)，我從頭開始遍歷往后找就行了，有序，簡單。

我真是個小天才。

就這樣日復(fù)一日，年復(fù)一年，User 的數(shù)據(jù)在不斷的增加，現(xiàn)在已經(jīng)多達(dá)百條了。

這個鏈表也越來越長，每次老板來找我要數(shù)據(jù)，我查找的時間也越來越慢。

而且不僅是大老板，我發(fā)現(xiàn)好多小老板也來找我要數(shù)據(jù)。

我快要累死了，我的腰漸漸地也直不起來了。

3

5月1號深夜，今天是勞動節(jié)。

我依舊在公司加班。

我想不能再這樣下去了，是時候祭出我的秘密武器了！

只有在夜深人靜一個人的時候，我才能召喚它！

螺螄粉！

沒錯，就是它！

因為我發(fā)現(xiàn)，嗦了螺螄粉之后，我的腦子特別清晰，思維特別地發(fā)散。

為此，我還特意去醫(yī)院檢查了下腦子，醫(yī)生說從片子上看的話一切正常，不過從感覺上看我可能不太正常。

不管了，反正我知道，螺螄粉確實能賦予我通透的頭腦。

因為，此時我的腦子已經(jīng)開始動起來了！

有了！

我忽然回想起，在大學(xué)里面有一門叫《數(shù)據(jù)結(jié)構(gòu)》的課程里講了二分法。

現(xiàn)在有近一千條有序的數(shù)據(jù)，我把它按每十條數(shù)據(jù)分為一組，于是我吭哧吭哧的一頓操作。

(為了美觀，就畫10組)然后我再為每一組都配置一個槽，每個槽記錄了每組最大的那條記錄的地址。

這樣，我就可以通過二分法快速查找記錄啦！

假設(shè)現(xiàn)在就10組數(shù)據(jù)，然后我要找 ID 等于 12 這條數(shù)據(jù)，我就：

1. 先計算中間槽的位置(1+10)/2=5，通過地址找到第五組，此時第五組ID是50，12<50，所以繼續(xù)二分。
2. (1+5)/2=3，通過地址找到第三組，此時第三組ID是30，12<30，所以繼續(xù)二分。
3. (1+3)/2=2，通過地址找到第二組，此時第二組ID是20，12<20，所以繼續(xù)二分。
4. (1+2)/2=1，通過地址找到第一組，此時第一組ID是10，12>10，現(xiàn)在能斷定12在第二組。
5. 從圖中看起來第一組和第二組是分開的？實際上地址是相連的，所以通過第一組最后一條數(shù)據(jù)，可以往后隨著單向鏈表遍歷，找到ID為12的這條數(shù)據(jù)。

是不是很方便？

總結(jié)的來說：

1. 先通過二分法找到數(shù)據(jù)所在的槽。
2. 然后再通過單向鏈表遍歷得到數(shù)據(jù)。

在數(shù)據(jù)量很大的時候這種查找方式非?？焖?！

因為查找數(shù)據(jù)的時間復(fù)雜度從O(n)幾乎簡化成了O(lgn）！

我稱之為頁目錄，我可真是個小天才呢！

4

就這樣，日復(fù)一日，年復(fù)一年。

User 的數(shù)據(jù)量還在逐日增加。

我發(fā)現(xiàn)每次查詢都需要掏出全部的名單來找。

我這小胳膊細(xì)腿的，都快抬不動了。

于是，在一個月黑風(fēng)高的夜晚，我又掏出了螺螄粉。

靈光乍現(xiàn)！

我以一千個數(shù)據(jù)為一個界限來分割數(shù)據(jù)，我將每一千個數(shù)據(jù)稱之為頁。

沒錯，我又想出了 idea，我將所有數(shù)據(jù)分為一頁一頁，每頁之間用雙向鏈表相連。

這樣每次查詢，我就不需要一次把有所數(shù)據(jù)都拉出來，我可以一頁一頁翻閱過去。

當(dāng)然，頁內(nèi)部還是按照剛才那樣分組訪問。

現(xiàn)在我是這樣查找數(shù)據(jù)的：

1. 每次查數(shù)據(jù)我從第一頁開始找。
2. 然后按照頁內(nèi)查找的方式二分去查數(shù)據(jù)，找不到就通過鏈表訪問下一頁。

因此，訪問速度并沒有變快，只是每次不需要把數(shù)據(jù)全部撈出來，只要一頁一頁的撈。

我的胳膊得到了解放。

5

公司越來越大，User 的數(shù)據(jù)爆炸性增長。

分的頁也越來越多，老板和小老板們開始抱怨了。

老板說，“我讓你找個人，你找了1小時？你今年年終獎還想不想要了！”

“唉，那個人在最后一頁，我翻的要死才翻到，我太難了！”

雖說在心里抱怨，但是我知道這樣下去不是辦法。

頭可斷血可流，年終獎不可少！

別問，問就是螺螄粉！

果不其然，螺螄粉是無敵的。

解決法子有了！

每個頁都標(biāo)上獨(dú)一無二的頁號。

參考書本目錄的設(shè)計，我還專門搞了一個頁，頁里面的存儲就是目錄！

我稱它為目錄頁。

你看，這樣我就能通過這個目錄頁找到對應(yīng)的數(shù)據(jù)頁。

比如：我現(xiàn)在要找 ID 為 500 的那條數(shù)據(jù)。

1. 我遍歷目錄頁數(shù)據(jù)就可以知道該條數(shù)據(jù)在頁1。
2. 然后就開始在頁內(nèi)通過老套路二分來查找數(shù)據(jù)！

可能有人覺得，目錄頁也是有大小的呀！裝不下怎么辦？

沒事，和數(shù)據(jù)頁一樣，新增頁唄！

可能有人會問，那目錄頁多了，查找目錄頁也會變慢的呀！

你說的沒錯，但這可難不倒我這個小聰明！

我們可以再搞一級目錄，我稱之為目中目(開個玩笑~)！

這樣，每次我從根目錄開始查詢，只要幾次查詢我就能找到想要的數(shù)據(jù)！

我稱這整一個為索引！

Y 老板看到了我的設(shè)計之后，拍了拍我的腦袋，“007，有一手啊，我看你這結(jié)構(gòu)看著像一棵樹，我這個人又喜歡吹牛 B，你看這玩意叫 B 樹怎么樣？”

“不行老板，我覺得這 B 格不夠高，要么叫B+樹吧？”

“行啊，007，年終獎我提前發(fā)給你！”

“叮鈴，支付寶到賬，0.1元?！?/p>

我：“...........”

“對了 007 ，這 User ID 太不好記了，下次我打算只告訴你名字，讓你找?！?/p>

我內(nèi)心：“@#%^&%........”

故事未完，敬請期待 ~

哈哈，第一次寫這類故事，有點(diǎn)意思。

這篇主要寫的是關(guān)于MySQL  InnoDB 聚簇索引的設(shè)計，闡述了 MySQL 的數(shù)據(jù)到底是如何查找的。

我記得之前阿里的面試官就問過我這個問題，讓我說說數(shù)據(jù)在索引上是如何找到的，越細(xì)越好。

嘿嘿，這下知道了吧。

不過，由于故事的原因，有些描述都是不準(zhǔn)確的，比如上面說的什么每一千條數(shù)據(jù)分為一頁。

我下面統(tǒng)一更正一下并補(bǔ)充一些點(diǎn)，看好了??！

• MySQL 一頁默認(rèn)16 KB，所以不是按數(shù)量的，是按總的記錄數(shù)所占的空間。
• 頁內(nèi)記錄是單向鏈表連接，頁之間是雙向鏈表連接。
• 當(dāng)一頁數(shù)據(jù)存滿了之后需要進(jìn)行頁分裂，也就是拆分下記錄變成兩個頁。
• 頁分裂操作也可能導(dǎo)致多個頁都滿了，比如你往一個頁中間插入數(shù)據(jù)，擠出一條數(shù)據(jù)到下一頁，然后下一頁也滿了，發(fā)生級聯(lián)，影響性能，所以建議主鍵有序，這樣不會往中間的頁插入數(shù)據(jù)。
• MySQL頁內(nèi)默認(rèn)會有一條最大記錄和一條最小記錄不存儲數(shù)據(jù)，就是這樣設(shè)計的，和鏈表dummy節(jié)點(diǎn)類似。
• 一頁除了存儲數(shù)據(jù)還有一些元數(shù)據(jù)，比如FileHeader、PageHeader等等，太細(xì)了講了你現(xiàn)在記得住，過兩星期也記不住，我也一樣。
• 一條記錄也有很多細(xì)節(jié)。

像大部分人可能知道 InnoDB B+樹索引的設(shè)計。

也能說出為什么要用 B+ 樹，但是很少會說到頁內(nèi)的二分查找。

其實這樣的設(shè)計很常見，像 Kafka 的索引也采用了二分，一般數(shù)據(jù)量大了，數(shù)據(jù)有序的情況都會上二分。

下次面試官問你，你就把這個跟他說說，面試官會覺得，嘖嘖真細(xì)啊。

對了，我上述講的只是索引結(jié)構(gòu)大致布局，想要看詳細(xì)的可以看《從根兒上理解 MySQL》，比如 FileHeader 有什么字段啊啥的。

不過，我個人覺得沒必要這么細(xì)，反正記不住，精髓掌握的即可。

如果你喜歡這樣故事類的文章，可以留言讓我知道，我之后多往這方面寫。