[[419559]]

Q：在實際生產環境中，InnoDB 中一棵 B+ 樹索引一般有多少層?可以存放多少行數據?

關于這個問題最近好像在牛客上經常看到，感覺沒啥意義，可能主要考察的是對 B+ 索引的理解吧。先上答案：

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

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

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

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

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

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

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

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

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

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

• 根節點指針數 * 每個葉子節點存放的行記錄數

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

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

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

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

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

當然，這樣分析其實不是很嚴謹，按照 《MySQL 技術內幕：InnoDB 存儲引擎》中的定義，InnoDB 數據頁結構包含如下幾個部分：

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

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

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