心態崩了，我怎麼知道實際生產環境的 B+ 樹索引有多少層？
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 行記錄。
關注公眾號 | 飛天小牛肉，即時獲取更新
-
博主東南大學碩士在讀，攜程 Java 後台開發暑期實習生，利用課餘時間運營一個公眾號『 飛天小牛肉 』，2020/12/29 日開通，專註分享計算機基礎（數據結構 + 算法 + 計算機網絡 + 數據庫 + 操作系統 + Linux）、Java 技術棧等相關原創技術好文。本公眾號的目的就是讓大家可以快速掌握重點知識，有的放矢。關注公眾號第一時間獲取文章更新，成長的路上我們一起進步
-
並推薦個人維護的開源教程類項目： CS-Wiki（Gitee 推薦項目，現已累計 1.8k+ star）, 致力打造完善的後端知識體系，在技術的路上少走彎路，歡迎各位小夥伴前來交流學習 ~
-
如果各位小夥伴春招秋招沒有拿得出手的項目的話，可以參考我寫的一個項目「開源社區系統 Echo」Gitee 官方推薦項目，目前已累計 1.1k+ star，基於 SpringBoot + MyBatis + MySQL + Redis + Kafka + Elasticsearch + Spring Security + … 並提供詳細的開發文檔和配套教程。公眾號後台回復 Echo 可以獲取配套教程，目前尚在更新中。
