[[419559]]

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

關(guān)于這個問題最近好像在?？蜕辖?jīng)?？吹剑杏X沒啥意義，可能主要考察的是對 B+ 索引的理解吧。先上答案：

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

前文說過，頁是 InnoDB 磁盤管理的最小單位，在 InnoDB 存儲引擎中，默認每個頁的大小為 16KB。而頁里面存放的東西就是一行一行的記錄。

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

眾所周知，B+ 樹的葉子節(jié)點存儲真正的記錄，而非葉子節(jié)點的存在是為了更快速的找到對應(yīng)記錄所在的葉子節(jié)點，所以可以簡單理解為非葉子節(jié)點存放的是鍵值 + 指針。這里用指針來描其實述不是太準確，準確來說是頁的偏移量，不過指針更好理解~

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

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

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

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

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

那么對于這棵 B+ 樹能夠存放多少行數(shù)據(jù)，其實問的就是這棵 B+ 樹的非葉子節(jié)點中存放的數(shù)據(jù)量，可以通過下面這個簡單的公式來計算：

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

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

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

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

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

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

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

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

OK，分析完高度為 2 的 B+ 樹，同樣的道理，我們來看高度為 3 的：

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