[[419559]]

Q：在實(shí)際生產(chǎn)環(huán)境中，InnoDB 中一棵 B+ 樹(shù)索引一般有多少層?可以存放多少行數(shù)據(jù)?

關(guān)于這個(gè)問(wèn)題最近好像在牛客上經(jīng)常看到，感覺(jué)沒(méi)啥意義，可能主要考察的是對(duì) B+ 索引的理解吧。先上答案：

A：一般是 2 ~ 3 層，可以存放約 兩千萬(wàn)行 的數(shù)據(jù)。

前文說(shuō)過(guò)，頁(yè)是 InnoDB 磁盤(pán)管理的最小單位，在 InnoDB 存儲(chǔ)引擎中，默認(rèn)每個(gè)頁(yè)的大小為 16KB。而頁(yè)里面存放的東西就是一行一行的記錄。

假設(shè)一行數(shù)據(jù)的大小是 1k，那么一頁(yè)就可以存放 16 行這樣的數(shù)據(jù)。

眾所周知，B+ 樹(shù)的葉子節(jié)點(diǎn)存儲(chǔ)真正的記錄，而非葉子節(jié)點(diǎn)的存在是為了更快速的找到對(duì)應(yīng)記錄所在的葉子節(jié)點(diǎn)，所以可以簡(jiǎn)單理解為非葉子節(jié)點(diǎn)存放的是鍵值 + 指針。這里用指針來(lái)描其實(shí)述不是太準(zhǔn)確，準(zhǔn)確來(lái)說(shuō)是頁(yè)的偏移量，不過(guò)指針更好理解~

通過(guò)索引組織表的方式，數(shù)據(jù)行被存放在不同的頁(yè)中。如下圖所示：

假設(shè)我們要從上圖這棵 B+ 樹(shù)種找到主鍵是 20 這行數(shù)據(jù) select * from table where id = 20;

首先找到 B+ 樹(shù)的根節(jié)點(diǎn)，即存儲(chǔ)的非葉子節(jié)點(diǎn)的頁(yè) page_number = 10，在該頁(yè)上通過(guò)二分查找法以及指針定位到 id = 20 這行數(shù)據(jù)存在于 page_number = 12 這頁(yè)上，然后同樣的在這頁(yè)上用二分查找即可快速定位 id = 20 這行記錄。

說(shuō)這些和文題不是很相關(guān)的話題，其實(shí)就是想要大家知道：頁(yè)作為 InnoDB 磁盤(pán)管理的最小單位，不僅可以用來(lái)存放具體的行數(shù)據(jù)，還可以存放鍵值和指針。

回到文題，我們先從簡(jiǎn)單的入手，假設(shè) B+ 樹(shù)只有兩層，即一個(gè)根節(jié)點(diǎn)和若干個(gè)葉子節(jié)點(diǎn)，如下圖：

那么對(duì)于這棵 B+ 樹(shù)能夠存放多少行數(shù)據(jù)，其實(shí)問(wèn)的就是這棵 B+ 樹(shù)的非葉子節(jié)點(diǎn)中存放的數(shù)據(jù)量，可以通過(guò)下面這個(gè)簡(jiǎn)單的公式來(lái)計(jì)算：

• 根節(jié)點(diǎn)指針數(shù) * 每個(gè)葉子節(jié)點(diǎn)存放的行記錄數(shù)

每個(gè)葉子節(jié)點(diǎn)存放的行記錄數(shù)就是每頁(yè)存放的記錄數(shù)，由于各個(gè)數(shù)據(jù)表中的字段數(shù)量都不一樣，這里我們就不深究葉子節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)了，簡(jiǎn)單按照一行記錄的數(shù)據(jù)大小為 1k 來(lái)算的話(實(shí)際上現(xiàn)在很多互聯(lián)網(wǎng)業(yè)務(wù)數(shù)據(jù)記錄大小通常就是 1K 左右)，一頁(yè)或者說(shuō)一個(gè)葉子節(jié)點(diǎn)可以存放 16 行這樣的數(shù)據(jù)。

那么 B+ 數(shù)的根節(jié)點(diǎn)(非葉子節(jié)點(diǎn))能夠存儲(chǔ)多少數(shù)據(jù)呢?

非葉子節(jié)點(diǎn)里面存的是主鍵值 + 指針，我們假設(shè)主鍵的類(lèi)型是 BigInt，長(zhǎng)度為 8 字節(jié)，而指針大小在 InnoDB 中設(shè)置為 6 字節(jié)，這樣一共 14 字節(jié)。

為了方便行文，這里我們把一個(gè)主鍵值 + 一個(gè)指針?lè)Q為一個(gè)單元，這樣的話，一頁(yè)或者說(shuō)一個(gè)非葉子節(jié)點(diǎn)能夠存放 16384 / 14=1170 個(gè)這樣的單元。

也就是說(shuō)一個(gè)非葉子節(jié)點(diǎn)中能夠存放 1170 個(gè)指針，即對(duì)應(yīng) 1170 個(gè)葉子節(jié)點(diǎn)，所以對(duì)于這樣一棵高度為 2 的 B+ 樹(shù)，能存放 1170(一個(gè)非葉子節(jié)點(diǎn)中的指針數(shù)) * 16(一個(gè)葉子節(jié)點(diǎn)中的行數(shù))= 18720 行數(shù)據(jù)。

當(dāng)然，這樣分析其實(shí)不是很?chē)?yán)謹(jǐn)，按照 《MySQL 技術(shù)內(nèi)幕：InnoDB 存儲(chǔ)引擎》中的定義，InnoDB 數(shù)據(jù)頁(yè)結(jié)構(gòu)包含如下幾個(gè)部分：

想要深究的小伙伴可以去看書(shū)中的 4.4 章節(jié)，這里我就不再多分析了。

OK，分析完高度為 2 的 B+ 樹(shù)，同樣的道理，我們來(lái)看高度為 3 的：

根頁(yè)(page10)可以存放 1170 個(gè)指針，然后第二層的每個(gè)頁(yè)(page:11,12,13)也都分別可以存放1170個(gè)指針。這樣一共可以存放 1170 * 1170 個(gè)指針，即對(duì)應(yīng)的有 1170 * 1170 個(gè)非葉子節(jié)點(diǎn)，所以一共可以存放 1170 * 1170 * 16 = 21902400 行記錄。