一個(gè)面試題：InnoDB 一棵 B+ 樹可以存放多少行數(shù)據(jù)?這個(gè)問題的簡(jiǎn)單回答是：約 2 千萬。

[[277685]]
圖片來自 Pexels 

為什么是這么多呢?因?yàn)檫@是可以算出來的，要搞清楚這個(gè)問題，我們先從 InnoDB 索引數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)組織方式說起。

我們都知道計(jì)算機(jī)在存儲(chǔ)數(shù)據(jù)的時(shí)候，有最小存儲(chǔ)單元，這就好比我們今天進(jìn)行現(xiàn)金的流通最小單位是一毛。

在計(jì)算機(jī)中磁盤存儲(chǔ)數(shù)據(jù)最小單元是扇區(qū)，一個(gè)扇區(qū)的大小是 512 字節(jié)，而文件系統(tǒng)(例如 XFS/EXT4)他的最小單元是塊，一個(gè)塊的大小是 4K。

而對(duì)于我們的 InnoDB 存儲(chǔ)引擎也有自己的最小儲(chǔ)存單元——頁(yè)(Page)，一個(gè)頁(yè)的大小是 16K。

下面幾張圖可以幫你理解最小存儲(chǔ)單元，文件系統(tǒng)中一個(gè)文件大小只有 1 個(gè)字節(jié)，但不得不占磁盤上 4KB 的空間。

InnoDB 的所有數(shù)據(jù)文件(后綴為 ibd 的文件)，他的大小始終都是 16384(16K)的整數(shù)倍。

磁盤扇區(qū)、文件系統(tǒng)、InnoDB 存儲(chǔ)引擎都有各自的最小存儲(chǔ)單元。

在 MySQL 中我們的 InnoDB 頁(yè)的大小默認(rèn)是 16K，當(dāng)然也可以通過參數(shù)設(shè)置：

mysql> show variables like 'innodb_page_size'; 
 
+------------------+-------+ 
 
| Variable_name    | Value | 
 
+------------------+-------+ 
 
| innodb_page_size | 16384 | 
 
+------------------+-------+ 
 
1 row in set (0.00 sec) 

數(shù)據(jù)表中的數(shù)據(jù)都是存儲(chǔ)在頁(yè)中的，所以一個(gè)頁(yè)中能存儲(chǔ)多少行數(shù)據(jù)呢?假設(shè)一行數(shù)據(jù)的大小是 1K，那么一個(gè)頁(yè)可以存放 16 行這樣的數(shù)據(jù)。

如果數(shù)據(jù)庫(kù)只按這樣的方式存儲(chǔ)，那么如何查找數(shù)據(jù)就成為一個(gè)問題。

因?yàn)槲覀儾恢酪檎业臄?shù)據(jù)存在哪個(gè)頁(yè)中，也不可能把所有的頁(yè)遍歷一遍，那樣太慢了。

所以人們想了一個(gè)辦法，用 B+ 樹的方式組織這些數(shù)據(jù)，如下圖所示：

我們先將數(shù)據(jù)記錄按主鍵進(jìn)行排序，分別存放在不同的頁(yè)中(為了便于理解我們這里一個(gè)頁(yè)中只存放 3 條記錄，實(shí)際情況可以存放很多)。

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

當(dāng)然它也是排好序的。這樣的數(shù)據(jù)組織形式，我們稱為索引組織表。

現(xiàn)在來看下，要查找一條數(shù)據(jù)，怎么查?如：

select * from user where id=5; 

這里 id 是主鍵，我們通過這棵 B+ 樹來查找，首先找到根頁(yè)，你怎么知道 user 表的根頁(yè)在哪呢?

其實(shí)每張表的根頁(yè)位置在表空間文件中是固定的，即 page number=3 的頁(yè)(這點(diǎn)我們下文還會(huì)進(jìn)一步證明)。

找到根頁(yè)后通過二分查找法，定位到 id=5 的數(shù)據(jù)應(yīng)該在指針 P5 指向的頁(yè)中，那么進(jìn)一步去 page number=5 的頁(yè)中查找，同樣通過二分查詢法即可找到 id=5 的記錄：

5    zhao2   27 

現(xiàn)在我們清楚了 InnoDB 中主鍵索引 B+ 樹是如何組織數(shù)據(jù)、查詢數(shù)據(jù)的，我們總結(jié)一下：

• InnoDB 存儲(chǔ)引擎的最小存儲(chǔ)單元是頁(yè)，頁(yè)可以用于存放數(shù)據(jù)也可以用于存放鍵值+指針，在 B+ 樹中葉子節(jié)點(diǎn)存放數(shù)據(jù)，非葉子節(jié)點(diǎn)存放鍵值+指針。
• 索引組織表通過非葉子節(jié)點(diǎn)的二分查找法以及指針確定數(shù)據(jù)在哪個(gè)頁(yè)中，進(jìn)而在去數(shù)據(jù)頁(yè)中查找到需要的數(shù)據(jù)。

那么回到我們開始的問題，通常一棵B+樹可以存放多少行數(shù)據(jù)?

這里我們先假設(shè) B+ 樹高為 2，即存在一個(gè)根節(jié)點(diǎn)和若干個(gè)葉子節(jié)點(diǎn)，那么這棵 B+ 樹的存放總記錄數(shù)為：根節(jié)點(diǎn)指針數(shù)*單個(gè)葉子節(jié)點(diǎn)記錄行數(shù)。

上文我們已經(jīng)說明單個(gè)葉子節(jié)點(diǎn)(頁(yè))中的記錄數(shù)=16K/1K=16。(這里假設(shè)一行記錄的數(shù)據(jù)大小為 1K，實(shí)際上現(xiàn)在很多互聯(lián)網(wǎng)業(yè)務(wù)數(shù)據(jù)記錄大小通常就是 1K 左右)。

那么現(xiàn)在我們需要計(jì)算出非葉子節(jié)點(diǎn)能存放多少指針?其實(shí)這也很好算，我們假設(shè)主鍵 ID 為 bigint 類型，長(zhǎng)度為 8 字節(jié)，而指針大小在 InnoDB 源碼中設(shè)置為 6 字節(jié)，這樣一共 14 字節(jié)。

我們一個(gè)頁(yè)中能存放多少這樣的單元，其實(shí)就代表有多少指針，即 16384/14=1170。

那么可以算出一棵高度為 2 的 B+ 樹，能存放 1170*16=18720 條這樣的數(shù)據(jù)記錄。

根據(jù)同樣的原理我們可以算出一個(gè)高度為 3 的 B+ 樹可以存放：1170*1170*16=21902400 條這樣的記錄。

所以在 InnoDB 中 B+ 樹高度一般為 1-3 層，它就能滿足千萬級(jí)的數(shù)據(jù)存儲(chǔ)。

在查找數(shù)據(jù)時(shí)一次頁(yè)的查找代表一次 IO，所以通過主鍵索引查詢通常只需要 1-3 次 IO 操作即可查找到數(shù)據(jù)。

怎么得到 InnoDB 主鍵索引 B+ 樹的高度?

上面我們通過推斷得出 B+ 樹的高度通常是 1-3，下面我們從另外一個(gè)側(cè)面證明這個(gè)結(jié)論。

在 InnoDB 的表空間文件中，約定 page number 為 3 的代表主鍵索引的根頁(yè)，而在根頁(yè)偏移量為 64 的地方存放了該 B+ 樹的 page level。

如果 page level 為 1，樹高為 2，page level 為 2，則樹高為 3。即 B+ 樹的高度=page level+1;下面我們將從實(shí)際環(huán)境中嘗試找到這個(gè) page level。

在實(shí)際操作之前，你可以通過 InnoDB 元數(shù)據(jù)表確認(rèn)主鍵索引根頁(yè)的 page number 為 3，你也可以從《InnoDB 存儲(chǔ)引擎》這本書中得到確認(rèn)：

SELECT 
b.name, a.name, index_id, type, a.space, a.PAGE_NO 
FROM 
information_schema.INNODB_SYS_INDEXES a, 
information_schema.INNODB_SYS_TABLES b 
WHERE 
a.table_id = b.table_id AND a.space <> 0; 

執(zhí)行結(jié)果：

可以看出數(shù)據(jù)庫(kù) dbt3 下的 customer 表、lineitem 表主鍵索引根頁(yè)的 page number 均為 3，而其他的二級(jí)索引 page number 為 4。

關(guān)于二級(jí)索引與主鍵索引的區(qū)別請(qǐng)參考 MySQL 相關(guān)書籍，本文不在此介紹。

下面我們對(duì)數(shù)據(jù)庫(kù)表空間文件做想相關(guān)的解析：

因?yàn)橹麈I索引 B+ 樹的根頁(yè)在整個(gè)表空間文件中的第 3 個(gè)頁(yè)開始，所以可以算出它在文件中的偏移量：16384*3=49152(16384 為頁(yè)大小)。

另外根據(jù)《InnoDB 存儲(chǔ)引擎》中描述在根頁(yè)的 64 偏移量位置前 2 個(gè)字節(jié)，保存了 page level 的值。

因此我們想要的 page level 的值在整個(gè)文件中的偏移量為：16384*3+64=49152+64=49216，前 2 個(gè)字節(jié)中。

接下來我們用 hexdump 工具，查看表空間文件指定偏移量上的數(shù)據(jù)：

• linetem 表的 page level 為 2，B+ 樹高度為page level+1=3。
• region 表的 page level 為 0，B+ 樹高度為 page level+1=1。
• customer 表的 page level 為 2，B+ 樹高度為 page level+1=3。

這三張表的數(shù)據(jù)量如下：

總結(jié)

lineitem 表的數(shù)據(jù)行數(shù)為 600 多萬，B+ 樹高度為 3，customer 表數(shù)據(jù)行數(shù)只有 15 萬，B+ 樹高度也為 3。

可以看出盡管數(shù)據(jù)量差異較大，這兩個(gè)表樹的高度都是 3。換句話說這兩個(gè)表通過索引查詢效率并沒有太大差異，因?yàn)槎贾恍枰?3 次 IO。

那么如果有一張表行數(shù)是一千萬，那么他的 B+ 樹高度依舊是 3，查詢效率仍然不會(huì)相差太大。region 表只有 5 行數(shù)據(jù)，當(dāng)然他的 B+ 樹高度為 1。

最后回顧一道 MySQL 面試題：為什么 MySQL 的索引要使用 B+ 樹而不是其他樹形結(jié)構(gòu)?比如 B 樹?現(xiàn)在這個(gè)問題的復(fù)雜版本可以參考本文。

他的簡(jiǎn)單版本回答是：因?yàn)?B 樹不管葉子節(jié)點(diǎn)還是非葉子節(jié)點(diǎn)，都會(huì)保存數(shù)據(jù)，這樣導(dǎo)致在非葉子節(jié)點(diǎn)中能保存的指針數(shù)量變少(有些資料也稱為扇出)。

指針少的情況下要保存大量數(shù)據(jù)，只能增加樹的高度，導(dǎo)致 IO 操作變多，查詢性能變低。

本文從一個(gè)問題出發(fā)，逐步介紹了 InnoDB 索引組織表的原理、查詢方式，并結(jié)合已有知識(shí)，回答該問題，結(jié)合實(shí)踐來證明。

當(dāng)然為了表述簡(jiǎn)單易懂，文中忽略了一些細(xì)枝末節(jié)，比如一個(gè)頁(yè)中不可能所有空間都用于存放數(shù)據(jù)，它還會(huì)存放一些少量的其他字段比如 page level，index number 等等。

另外還有頁(yè)的填充因子也導(dǎo)致一個(gè)頁(yè)不可能全部用于保存數(shù)據(jù)。關(guān)于二級(jí)索引數(shù)據(jù)存取方式可以參考 MySQL 相關(guān)書籍，他的要點(diǎn)是結(jié)合主鍵索引進(jìn)行回表查詢。

作者：李平

簡(jiǎn)介：目前在一家 O2O 互聯(lián)網(wǎng)公司從事設(shè)計(jì)、開發(fā)工作。業(yè)余時(shí)間喜歡跑步、看書、游戲。喜歡簡(jiǎn)單而高效的工作環(huán)境，熟悉 JavaEE、SOA、數(shù)據(jù)庫(kù)架構(gòu)、優(yōu)化、系統(tǒng)運(yùn)維，有大型門戶網(wǎng)站，金融系統(tǒng)建設(shè)經(jīng)驗(yàn)。RHCE、MySQL OCP。MyCAT 開源項(xiàng)目成員。