引言

事萬(wàn)物都有自己的單元體系，若干個(gè)小單體組成一個(gè)個(gè)大的個(gè)體。就像拼樂(lè)高一樣，可以自由組合。所以說(shuō)，如果能熟悉最小單元，就意味著我們抓住了事物的本事，再?gòu)?fù)雜的問(wèn)題也會(huì)迎刃而解。

存儲(chǔ)單元

存儲(chǔ)器范圍比較大，但是數(shù)據(jù)具體怎么存儲(chǔ)，有自己的最小存儲(chǔ)單元。

1、數(shù)據(jù)持久化存儲(chǔ)磁盤里，磁盤的最小單元是扇區(qū)，一個(gè)扇區(qū)的大小是 512個(gè)字節(jié)

2、文件系統(tǒng)的最小單元是塊，一個(gè)塊的大小是 4K

3、InnoDB存儲(chǔ)引擎，有自己的最小單元，稱之為頁(yè)，一個(gè)頁(yè)的大小是16K

扇區(qū)、塊、頁(yè)這三者的存儲(chǔ)關(guān)系？

mysql數(shù)據(jù)庫(kù)中，table表中的記錄都是存儲(chǔ)在頁(yè)中，那么一頁(yè)可以存多少行數(shù)據(jù)？假如一行數(shù)據(jù)的大小約為1K字節(jié)，那么按 16K / 1K = 16，可以計(jì)算出一頁(yè)大約能存放16條數(shù)據(jù)。

mysql 的最小存儲(chǔ)單元叫做“頁(yè)”，這么多的頁(yè)是如何構(gòu)建一個(gè)龐大的數(shù)據(jù)組織，我們又如何知道數(shù)據(jù)存儲(chǔ)在哪一個(gè)頁(yè)中？

如果逐條遍歷，性能肯定很差。為了提升查找速度，我們引入了B+樹，先來(lái)看下B+樹的存儲(chǔ)結(jié)構(gòu)

頁(yè)除了可以存放數(shù)據(jù)（葉子節(jié)點(diǎn)），還可以存放健值和指針（非葉子節(jié)點(diǎn)），當(dāng)然他們是有序的。這樣的數(shù)據(jù)組織形式，我們稱為索引組織表。

如：上圖中 page number=3的頁(yè)，該頁(yè)存放鍵值和指向數(shù)據(jù)頁(yè)的指針，這樣的頁(yè)由N個(gè)鍵值+指針組成

B+ 樹是如何檢索記錄？

首先找到根頁(yè)，你怎么知道一張表的根頁(yè)在哪呢？
其實(shí)每張表的根頁(yè)位置在表空間文件中是固定的，即page number=3的頁(yè)
找到根頁(yè)后通過(guò)二分查找法，定位到id=5的數(shù)據(jù)應(yīng)該在指針P5指向的頁(yè)中
然后再去page number=5的頁(yè)中查找，同樣通過(guò)二分查詢法即可找到id=5的記錄

查詢數(shù)據(jù)庫(kù)時(shí)，不論讀一行，還是讀多行，都是將這些行所在的整頁(yè)數(shù)據(jù)加載，然后在內(nèi)存中匹配過(guò)濾出最終結(jié)果。

表的檢索速度跟樹的深度有直接關(guān)系，畢竟一次頁(yè)加載就是一次IO，而磁盤IO又是比較費(fèi)時(shí)間。對(duì)于一張千萬(wàn)級(jí)條數(shù)B+樹高度為3的表與幾十萬(wàn)級(jí)B+樹高度也為3的表，其實(shí)查詢效率相差不大。

一棵樹可以存放多少行數(shù)據(jù)？

假設(shè)B+樹的深度為2

這棵B+樹的存儲(chǔ)總記錄數(shù) = 根節(jié)點(diǎn)指針數(shù) * 單個(gè)葉子節(jié)點(diǎn)記錄條數(shù)

那么指針數(shù)如何計(jì)算？

假設(shè)主鍵ID為bigint類型，長(zhǎng)度為8字節(jié)，而指針大小在InnoDB源碼中設(shè)置為6字節(jié)，這樣一共14字節(jié)。

那么一個(gè)頁(yè)中能存放多少這樣的組合，就代表有多少指針，即 16384 / 14 = 1170。那么可以算出一棵高度為2 的B+樹，能存放 1170 * 16 = 18720 條這樣的數(shù)據(jù)記錄。

同理：高度為3的B+樹可以存放的行數(shù) = 1170 * 1170 * 16 = 21902400

千萬(wàn)級(jí)的數(shù)據(jù)存儲(chǔ)只需要約3層B+樹，查詢數(shù)據(jù)時(shí)，每加載一頁(yè)（page）代表一次IO。所以說(shuō)，根據(jù)主鍵id索引查詢約3次IO便可以找到目標(biāo)結(jié)果。