MySQL的B+樹如何存儲(chǔ)主鍵和數(shù)據(jù)？
文章的起源是一位網(wǎng)友的評(píng)論，問的問題比較犀利且分散。借著這個(gè)機(jī)會(huì)研究下這些問題，分別作答一下。
這里是網(wǎng)友的提問：
二、正式作答部分
這里分析完這個(gè)網(wǎng)友的提問之后，可以大致分為4個(gè)問題來回答，下面分別嘗試作答一下，有不正確的地方歡迎大家留言討論~
1、關(guān)于B+樹的非葉子節(jié)點(diǎn)存儲(chǔ)問題
（1）B+樹的大致結(jié)構(gòu)
葉子節(jié)點(diǎn)是存放用戶數(shù)據(jù)的，頁(yè)內(nèi)數(shù)據(jù)根據(jù)用戶記錄的主鍵大小排列成的單向鏈表。而頁(yè)和頁(yè)之間是根據(jù)主鍵大小順序排成一個(gè)雙向鏈表。
（2）模擬計(jì)算下B+樹存儲(chǔ)的數(shù)據(jù)量
我們這里計(jì)算下，假設(shè)非葉節(jié)點(diǎn)不同元素占用情況為：下一條記錄指針占4Byte，id值8Byte，目標(biāo)記錄指針4Byte，那么一個(gè)4Kb的磁盤塊將大致可以容納250個(gè)下級(jí)指針。
我們假設(shè)，一個(gè)4kb的磁盤塊可以容納100條數(shù)據(jù)(用戶的實(shí)際數(shù)據(jù))：
如果B+樹只有1層，也就是只有1個(gè)用于存放用戶記錄的節(jié)點(diǎn)，最多能存放100條記錄。
如果B+樹有2層，最多能存放250×100=2.5W條記錄。
如果B+樹有3層，最多能存放250×250×100=625W條記錄。
（3）網(wǎng)友的問題答案
原來的計(jì)算方式確實(shí)是不嚴(yán)謹(jǐn)?shù)模挥蟹侨~子節(jié)點(diǎn)才會(huì)存有葉子節(jié)點(diǎn)的頁(yè)記錄，也就是所謂的“下級(jí)指針”。實(shí)際的存儲(chǔ)方式應(yīng)該是這篇重寫的部分。
2、磁盤IO次數(shù)計(jì)算問題
（1）什么是一次IO
每次IO其實(shí)是磁盤控制器向磁盤發(fā)出一次讀/寫指令，給出開始扇區(qū)的地址和向后連續(xù)讀/寫的扇區(qū)的個(gè)數(shù)。控制器發(fā)出的這種指令＋數(shù)據(jù)，就是一次IO，讀或者寫。
（2）IO次數(shù)的計(jì)算
首先要明確，我們每次IO都是讀取數(shù)據(jù)到內(nèi)存中進(jìn)行一些計(jì)算。當(dāng)我們遍歷主鍵索引的B+樹查找數(shù)據(jù)的時(shí)候，IO次數(shù)是近似于B+樹的層數(shù)-1，因?yàn)楦?jié)點(diǎn)是一直在內(nèi)存中的。
基本上可以理解為，每次io都是在樹的一層查找符合的id范圍的頁(yè)數(shù)據(jù)，通過對(duì)比頁(yè)里面的最大最小主鍵來確定下層的查找范圍。
3、磁盤預(yù)讀以及如何保證每次都能拿到innodb的一頁(yè)也就是16kb的數(shù)據(jù)
（1）磁盤預(yù)讀
預(yù)讀其實(shí)就是利用了局部性原理，具體過程是：對(duì)于每個(gè)文件的第一個(gè)讀請(qǐng)求，系統(tǒng)讀入所請(qǐng)求的頁(yè)面并讀入緊隨其后的少數(shù)幾個(gè)頁(yè)面（通常是三個(gè)頁(yè)面），這時(shí)的預(yù)讀稱為同步預(yù)讀。
我們知道對(duì)大部分操作系統(tǒng)來說，磁盤的一頁(yè)數(shù)據(jù)是4kb,那么算上預(yù)讀的3頁(yè)：
4kb(磁盤一頁(yè)的大小) + 12kb(預(yù)讀三個(gè)頁(yè)面) = 16kb（2）關(guān)于每次讀取16kb數(shù)據(jù)
這個(gè)16kb是innodb默認(rèn)的頁(yè)大小，為什么會(huì)有這個(gè)概念呢，因?yàn)楫?dāng)涉及到數(shù)據(jù)庫(kù)讀寫的時(shí)候，規(guī)定數(shù)據(jù)庫(kù)每次讀寫都是以16k為單位的，一次最少?gòu)拇疟P中讀取16KB的內(nèi)容到內(nèi)存中，一次最少把內(nèi)存中的16KB內(nèi)容刷新到磁盤中。
（3）磁盤io固定是每次讀取4kb的嗎
答案明顯不是的，io讀取是可大可小的，具體看指令的內(nèi)容，并不是每次只能讀取固定的1頁(yè)。比如上面解釋一次io概念的時(shí)候，我們提到了指令，這個(gè)指令是類似于給出兩個(gè)參數(shù)，第一個(gè)參數(shù)是要開始讀取的扇區(qū)地址，第二個(gè)參數(shù)是要讀取多少扇區(qū)。
所以每次io的大小是根據(jù)指令來決定的，并不是每次只能讀取磁盤的一頁(yè)數(shù)據(jù)，也就是4kb。
（4）網(wǎng)友的問題
主要是明確磁盤中的一頁(yè)數(shù)據(jù)(4kb)和數(shù)據(jù)庫(kù)innodb規(guī)定的一頁(yè)數(shù)據(jù)(16kb),這兩個(gè)的概念是不一樣的。磁盤io的大小也是根據(jù)指令來規(guī)定的。對(duì)應(yīng)數(shù)據(jù)庫(kù)讀寫來說，會(huì)按照數(shù)據(jù)庫(kù)的配置，每次最少讀寫一頁(yè)數(shù)據(jù)，也就是16kb。
4、設(shè)置頁(yè)大小為64kb，是否一次io就拿不到對(duì)應(yīng)的數(shù)據(jù)了，需要多次io？
其實(shí)這個(gè)問題上面已經(jīng)給出了答案。設(shè)置innodb頁(yè)大小為64kb之后，我們每次數(shù)據(jù)庫(kù)的讀寫就必須操作64kb的數(shù)據(jù)了而已，和io次數(shù)沒什么關(guān)系的。
經(jīng)過看文檔，也沒看到有說到64kb頁(yè)大小有什么缺陷之類的，只知道會(huì)增大表空間上限：
InnoDB頁(yè)面大小 最大表空間大小：
關(guān)于磁盤部分和io部分，這里也就不多做解釋了。
往期精彩回顧