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

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

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

面試過程還是挺簡(jiǎn)單的。

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

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

1

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

下午兩點(diǎn)。

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

“老板你好，我叫小S，不是叫 007 ，007 是我對(duì)公司的熱愛，是我的畢生....”

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

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

我激動(dòng)著、顫抖著回答：“Yes，Sir！”

2

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

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

因?yàn)檫@是我的第一份工作，我熱愛！

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

image

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

image

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

我真是個(gè)小天才。

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

image

這個(gè)鏈表也越來(lái)越長(zhǎng)，每次老板來(lái)找我要數(shù)據(jù)，我查找的時(shí)間也越來(lái)越慢。

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

我快要累死了，我的腰漸漸地也直不起來(lái)了。

3

5月1號(hào)深夜，今天是勞動(dòng)節(jié)。

我依舊在公司加班。

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

只有在夜深人靜一個(gè)人的時(shí)候，我才能召喚它！

螺螄粉！

image

沒錯(cuò)，就是它！

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

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

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

因?yàn)?，此時(shí)我的腦子已經(jīng)開始動(dòng)起來(lái)了！

有了！

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

image

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

image

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

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

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

是不是很方便？

總結(jié)的來(lái)說(shuō)：

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

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

因?yàn)椴檎覕?shù)據(jù)的時(shí)間復(fù)雜度從O(n)幾乎簡(jiǎn)化成了O(lgn）！

我稱之為頁(yè)目錄，我可真是個(gè)小天才呢！

4

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

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

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

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

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

image

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

圖圖圖圖圖圖

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

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

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

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

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

我的胳膊得到了解放。

5

公司越來(lái)越大，User 的數(shù)據(jù)爆炸性增長(zhǎng)。

分的頁(yè)也越來(lái)越多，老板和小老板們開始抱怨了。

老板說(shuō)，“我讓你找個(gè)人，你找了1小時(shí)？你今年年終獎(jiǎng)還想不想要了！”

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

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

頭可斷血可流，年終獎(jiǎng)不可少！

別問，問就是螺螄粉！

果不其然，螺螄粉是無(wú)敵的。

解決法子有了！

每個(gè)頁(yè)都標(biāo)上獨(dú)一無(wú)二的頁(yè)號(hào)。

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

我稱它為目錄頁(yè)。

image

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

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

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

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

image

可能有人會(huì)問，那目錄頁(yè)多了，查找目錄頁(yè)也會(huì)變慢的呀！

你說(shuō)的沒錯(cuò)，但這可難不倒我這個(gè)小聰明！

image

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

我稱這整一個(gè)為索引！

image

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

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

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

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

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

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

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

故事未完，敬請(qǐng)期待 ~

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

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

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

嘿嘿，這下知道了吧。

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

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