我是小M，我在卡拉巴拉星球扮饶。
我喜歡數(shù)據(jù)淮韭，我立志成為一個(gè)數(shù)據(jù)管理者。
所以我來 Y 公司應(yīng)聘贴届，聽說他們的數(shù)據(jù)量挺大的。
面試過程還是挺簡單的。
我用 007 這三個(gè)數(shù)字就輕易打敗了一堆吹噓 996 的應(yīng)聘者毫蚓。
此刻占键，我獨(dú)領(lǐng)風(fēng)騷。
1
今天是我第一天上班元潘，我筆直地坐在工位上畔乙，等著老板的寵幸。
下午兩點(diǎn)翩概。
Y 老板推門而入牲距，打著哈欠看著我：“007，你背有問題钥庇？坐得這么直牍鞠？”
“老板你好，我叫小M评姨，不是叫 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ù)都來自一個(gè)叫 User 的部門更舞，它們都有一樣的結(jié)構(gòu)：
這堆數(shù)據(jù)的 ID 都是有規(guī)律的畦幢，我想著就按順序把它排排坐，我用鏈表將它們相連缆蝉。
每次查找數(shù)據(jù)宇葱，我從頭開始遍歷往后找就行了瘦真，有序，簡單黍瞧。
我真是個(gè)小天才诸尽。
就這樣日復(fù)一日，年復(fù)一年印颤，User 的數(shù)據(jù)在不斷的增加您机，現(xiàn)在已經(jīng)多達(dá)百條了。
這個(gè)鏈表也越來越長年局，每次老板來找我要數(shù)據(jù)际看，我查找的時(shí)間也越來越慢。
而且不僅是大老板矢否，我發(fā)現(xiàn)好多小老板也來找我要數(shù)據(jù)仲闽。
我快要累死了，我的腰漸漸地也直不起來了兴喂。
3
5月1號(hào)深夜蔼囊，今天是勞動(dòng)節(jié)。
我依舊在公司加班衣迷。
我想不能再這樣下去了畏鼓，是時(shí)候祭出我的秘密武器了！
只有在夜深人靜一個(gè)人的時(shí)候壶谒，我才能召喚它云矫！
螺螄粉！
沒錯(cuò)汗菜，就是它让禀！
因?yàn)槲野l(fā)現(xiàn)，嗦了螺螄粉之后陨界，我的腦子特別清晰巡揍，思維特別地發(fā)散。
為此菌瘪，我還特意去醫(yī)院檢查了下腦子腮敌，醫(yī)生說從片子上看的話一切正常，不過從感覺上看我可能不太正常俏扩。
不管了糜工，反正我知道，螺螄粉確實(shí)能賦予我通透的頭腦录淡。
因?yàn)榘颇荆藭r(shí)我的腦子已經(jīng)開始動(dòng)起來了！
有了嫉戚！
我忽然回想起刨裆，在大學(xué)里面有一門叫《數(shù)據(jù)結(jié)構(gòu)》的課程里講了二分法澈圈。
現(xiàn)在有近一千條有序的數(shù)據(jù)，我把它按每十條數(shù)據(jù)分為一組崔拥，于是我吭哧吭哧的一頓操作极舔。
(為了美觀，就畫10組)然后我再為每一組都配置一個(gè)槽链瓦，每個(gè)槽記錄了每組最大的那條記錄的地址。
這樣盯桦，我就可以通過二分法快速查找記錄啦慈俯！
假設(shè)現(xiàn)在就10組數(shù)據(jù)，然后我要找 ID 等于 12 這條數(shù)據(jù)拥峦，我就：
- 先計(jì)算中間槽的位置
(1+10)/2=5贴膘，通過地址找到第五組，此時(shí)第五組ID是50略号，12<50刑峡，所以繼續(xù)二分。 -
(1+5)/2=3玄柠，通過地址找到第三組突梦，此時(shí)第三組ID是30，12<30羽利，所以繼續(xù)二分宫患。 -
(1+3)/2=2，通過地址找到第二組这弧，此時(shí)第二組ID是20娃闲，12<20，所以繼續(xù)二分匾浪。 -
(1+2)/2=1皇帮，通過地址找到第一組，此時(shí)第一組ID是10蛋辈，12>10属拾，現(xiàn)在能斷定12在第二組。 - 從圖中看起來第一組和第二組是分開的梯浪？實(shí)際上地址是相連的捌年，所以通過第一組最后一條數(shù)據(jù)，可以往后隨著單向鏈表遍歷挂洛，找到ID為12的這條數(shù)據(jù)礼预。
是不是很方便？
總結(jié)的來說：
- 先通過二分法找到數(shù)據(jù)所在的槽虏劲。
- 然后再通過單向鏈表遍歷得到數(shù)據(jù)托酸。
在數(shù)據(jù)量很大的時(shí)候這種查找方式非嘲保快速！
因?yàn)椴檎覕?shù)據(jù)的時(shí)間復(fù)雜度從O(n)幾乎簡化成了O(lgn）励堡！
我稱之為頁目錄谷丸，我可真是個(gè)小天才呢！
4
就這樣应结，日復(fù)一日刨疼，年復(fù)一年。
User 的數(shù)據(jù)量還在逐日增加鹅龄。
我發(fā)現(xiàn)每次查詢都需要掏出全部的名單來找揩慕。
我這小胳膊細(xì)腿的，都快抬不動(dòng)了扮休。
于是迎卤，在一個(gè)月黑風(fēng)高的夜晚，我又掏出了螺螄粉玷坠。
靈光乍現(xiàn)蜗搔！
我以一千個(gè)數(shù)據(jù)為一個(gè)界限來分割數(shù)據(jù)，我將每一千個(gè)數(shù)據(jù)稱之為頁八堡。
沒錯(cuò)樟凄，我又想出了 idea，我將所有數(shù)據(jù)分為一頁一頁秕重，每頁之間用雙向鏈表相連不同。
這樣每次查詢，我就不需要一次把有所數(shù)據(jù)都拉出來溶耘，我可以一頁一頁翻閱過去二拐。
當(dāng)然，頁內(nèi)部還是按照剛才那樣分組訪問凳兵。
現(xiàn)在我是這樣查找數(shù)據(jù)的：
- 每次查數(shù)據(jù)我從第一頁開始找百新。
- 然后按照頁內(nèi)查找的方式二分去查數(shù)據(jù)，找不到就通過鏈表訪問下一頁庐扫。
因此饭望，訪問速度并沒有變快，只是每次不需要把數(shù)據(jù)全部撈出來形庭，只要一頁一頁的撈铅辞。
我的胳膊得到了解放。
5
公司越來越大萨醒，User 的數(shù)據(jù)爆炸性增長斟珊。
分的頁也越來越多，老板和小老板們開始抱怨了富纸。
老板說囤踩，“我讓你找個(gè)人旨椒，你找了1小時(shí)？你今年年終獎(jiǎng)還想不想要了堵漱！”
“唉综慎，那個(gè)人在最后一頁，我翻的要死才翻到勤庐，我太難了示惊！”
雖說在心里抱怨，但是我知道這樣下去不是辦法埃元。
頭可斷血可流涝涤，年終獎(jiǎng)不可少！
別問岛杀，問就是螺螄粉！
果不其然崭孤，螺螄粉是無敵的类嗤。
解決法子有了！
每個(gè)頁都標(biāo)上獨(dú)一無二的頁號(hào)辨宠。
參考書本目錄的設(shè)計(jì)遗锣，我還專門搞了一個(gè)頁，頁里面的存儲(chǔ)就是目錄嗤形！
我稱它為目錄頁精偿。
你看，這樣我就能通過這個(gè)目錄頁找到對(duì)應(yīng)的數(shù)據(jù)頁赋兵。
比如：我現(xiàn)在要找 ID 為 500 的那條數(shù)據(jù)笔咽。
- 我遍歷目錄頁數(shù)據(jù)就可以知道該條數(shù)據(jù)在頁1。
- 然后就開始在頁內(nèi)通過老套路二分來查找數(shù)據(jù)霹期！
可能有人覺得叶组，目錄頁也是有大小的呀！裝不下怎么辦历造？
沒事甩十，和數(shù)據(jù)頁一樣，新增頁唄吭产！
可能有人會(huì)問侣监，那目錄頁多了，查找目錄頁也會(huì)變慢的呀臣淤！
你說的沒錯(cuò)橄霉，但這可難不倒我這個(gè)小聰明！
我們可以再搞一級(jí)目錄荒典，我稱之為目中目(開個(gè)玩笑~)酪劫！
這樣吞鸭，每次我從根目錄開始查詢，只要幾次查詢我就能找到想要的數(shù)據(jù)覆糟！
我稱這整一個(gè)為索引吸耿！
Y 老板看到了我的設(shè)計(jì)之后，拍了拍我的腦袋肆资，“007磅崭，有一手啊，我看你這結(jié)構(gòu)看著像一棵樹麦箍，我這個(gè)人又喜歡吹牛 B漓藕，你看這玩意叫 B 樹怎么樣？”
“不行老板挟裂，我覺得這 B 格不夠高享钞，要么叫B+樹吧？”
“行啊诀蓉，007栗竖，年終獎(jiǎng)我提前發(fā)給你！”
“叮鈴渠啤，支付寶到賬狐肢，0.1元×げ埽”
我：“...........”
“對(duì)了 007 份名，這 User ID 太不好記了，下次我打算只告訴你名字妓美，讓你找僵腺。”
我內(nèi)心：“@#%^&%........”
故事未完部脚，敬請(qǐng)期待 ~
哈哈想邦，第一次寫這類故事，有點(diǎn)意思委刘。
這篇主要寫的是關(guān)于MySQL InnoDB 聚簇索引的設(shè)計(jì)丧没，闡述了 MySQL 的數(shù)據(jù)到底是如何查找的。
我記得之前阿里的面試官就問過我這個(gè)問題锡移，讓我說說數(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)行頁分裂败明，也就是拆分下記錄變成兩個(gè)頁。
- 頁分裂操作也可能導(dǎo)致多個(gè)頁都滿了太防，比如你往一個(gè)頁中間插入數(shù)據(jù)妻顶，擠出一條數(shù)據(jù)到下一頁，然后下一頁也滿了蜒车，發(fā)生級(jí)聯(lián)盈包，影響性能，所以建議主鍵有序醇王，這樣不會(huì)往中間的頁插入數(shù)據(jù)。
- MySQL頁內(nèi)默認(rèn)會(huì)有一條最大記錄和一條最小記錄不存儲(chǔ)數(shù)據(jù)崭添，就是這樣設(shè)計(jì)的寓娩，和鏈表dummy節(jié)點(diǎn)類似。
- 一頁除了存儲(chǔ)數(shù)據(jù)還有一些元數(shù)據(jù)呼渣，比如FileHeader棘伴、PageHeader等等，太細(xì)了講了你現(xiàn)在記得住屁置，過兩星期也記不住焊夸，我也一樣。
- 一條記錄也有很多細(xì)節(jié)蓝角。
像大部分人可能知道 InnoDB B+樹索引的設(shè)計(jì)阱穗。
也能說出為什么要用 B+ 樹，但是很少會(huì)說到頁內(nèi)的二分查找使鹅。
其實(shí)這樣的設(shè)計(jì)很常見揪阶，像 Kafka 的索引也采用了二分，一般數(shù)據(jù)量大了患朱，數(shù)據(jù)有序的情況都會(huì)上二分鲁僚。
下次面試官問你，你就把這個(gè)跟他說說，面試官會(huì)覺得冰沙，嘖嘖真細(xì)啊侨艾。
對(duì)了，我上述講的只是索引結(jié)構(gòu)大致布局拓挥，想要看詳細(xì)的可以看《從根兒上理解 MySQL》唠梨，比如 FileHeader 有什么字段啊啥的。
不過撞叽，我個(gè)人覺得沒必要這么細(xì)姻成，反正記不住，精髓掌握的即可愿棋。
如果你喜歡這樣故事類的文章科展，可以留言讓我知道，我之后多往這方面寫糠雨。
我的個(gè)人github才睹，歡迎star！
我是yes甘邀，從一點(diǎn)點(diǎn)到億點(diǎn)點(diǎn)琅攘，我們下篇見。
