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)

由圖片可以看到，innodb中的B+樹，非葉子節(jié)點(diǎn)主要是存儲(chǔ)主鍵的記錄值，按照主鍵的大小順序排成一個(gè)單向鏈表。

葉子節(jié)點(diǎn)是存放用戶數(shù)據(jù)的，頁內(nèi)數(shù)據(jù)根據(jù)用戶記錄的主鍵大小排列成的單向鏈表。而頁和頁之間是根據(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)的頁記錄，也就是所謂的“下級(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范圍的頁數(shù)據(jù)，通過對(duì)比頁里面的最大最小主鍵來確定下層的查找范圍。

3、磁盤預(yù)讀以及如何保證每次都能拿到innodb的一頁也就是16kb的數(shù)據(jù)

（1）磁盤預(yù)讀

預(yù)讀其實(shí)就是利用了局部性原理，具體過程是：對(duì)于每個(gè)文件的第一個(gè)讀請(qǐng)求，系統(tǒng)讀入所請(qǐng)求的頁面并讀入緊隨其后的少數(shù)幾個(gè)頁面（通常是三個(gè)頁面），這時(shí)的預(yù)讀稱為同步預(yù)讀。

我們知道對(duì)大部分操作系統(tǒng)來說，磁盤的一頁數(shù)據(jù)是4kb,那么算上預(yù)讀的3頁：

4kb(磁盤一頁的大小)?+?12kb(預(yù)讀三個(gè)頁面)?=?16kb

（2）關(guān)于每次讀取16kb數(shù)據(jù)

這個(gè)16kb是innodb默認(rèn)的頁大小，為什么會(huì)有這個(gè)概念呢，因?yàn)楫?dāng)涉及到數(shù)據(jù)庫讀寫的時(shí)候，規(guī)定數(shù)據(jù)庫每次讀寫都是以16k為單位的，一次最少從磁盤中讀取16KB的內(nèi)容到內(nèi)存中，一次最少把內(nèi)存中的16KB內(nèi)容刷新到磁盤中。

（3）磁盤io固定是每次讀取4kb的嗎

答案明顯不是的，io讀取是可大可小的，具體看指令的內(nèi)容，并不是每次只能讀取固定的1頁。比如上面解釋一次io概念的時(shí)候，我們提到了指令，這個(gè)指令是類似于給出兩個(gè)參數(shù)，第一個(gè)參數(shù)是要開始讀取的扇區(qū)地址，第二個(gè)參數(shù)是要讀取多少扇區(qū)。

所以每次io的大小是根據(jù)指令來決定的，并不是每次只能讀取磁盤的一頁數(shù)據(jù)，也就是4kb。

（4）網(wǎng)友的問題

主要是明確磁盤中的一頁數(shù)據(jù)(4kb)和數(shù)據(jù)庫innodb規(guī)定的一頁數(shù)據(jù)(16kb),這兩個(gè)的概念是不一樣的。磁盤io的大小也是根據(jù)指令來規(guī)定的。對(duì)應(yīng)數(shù)據(jù)庫讀寫來說，會(huì)按照數(shù)據(jù)庫的配置，每次最少讀寫一頁數(shù)據(jù)，也就是16kb。

4、設(shè)置頁大小為64kb，是否一次io就拿不到對(duì)應(yīng)的數(shù)據(jù)了，需要多次io？

其實(shí)這個(gè)問題上面已經(jīng)給出了答案。設(shè)置innodb頁大小為64kb之后，我們每次數(shù)據(jù)庫的讀寫就必須操作64kb的數(shù)據(jù)了而已，和io次數(shù)沒什么關(guān)系的。

經(jīng)過看文檔，也沒看到有說到64kb頁大小有什么缺陷之類的，只知道會(huì)增大表空間上限：

InnoDB頁面大小 最大表空間大小：

關(guān)于磁盤部分和io部分，這里也就不多做解釋了。

往期精彩回顧

Mysql-B+TREE索引原理

Mysql為什么選擇B+樹存儲(chǔ)索引

深入了解 B-Tree 和 B+Tree 的區(qū)別

圖解 MySQL 索引 —— B-Tree、B+Tree

MySQL的查詢需要遍歷幾次B+樹，理論上需要幾次磁盤I/O？

MySQL

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。