大家好，我是君哥。

MySQL 默認存儲引擎是 InnoDB，跟 MyISAM 相比，InnoDB 支持事務、支持行級鎖、支持主鍵和外鍵、索引存儲上使用 B+ 樹。

那如果 MySQL 一張表存儲了 2 千萬條數據，B+ 樹層高是多少呢？今天來聊一聊這個面試題。

InnoDB 存儲

在 InnoDB 存儲引擎中，是以索引組織表的方式存放數據的，也就是表中數據是根據主鍵順序以索引的形式存放的。數據存儲在 B+ 樹中，每一個索引對應一棵 B+ 樹。

我們知道，計算機中，磁盤存儲數據的最小單位是扇區，一個扇區大小為 512B。而文件系統的最小單位是塊，一個塊大小是 4K。

那 InnoDB 具體是以什么單位來存放數據呢？InnoDB 是以頁為單位存放數據的，一個頁大小是 16K。如下圖：

圖片

B+ 樹索引

跟 MyISAM 不一樣的是，InnoDB 使用聚簇索引，葉子節點存儲數據，不用獨立的行存儲。下面是 MyISAM 的存儲結構：

圖片

InnoDB 主鍵索引每個葉節點包含了主鍵值和所有的剩余字段。二級索引的葉節點中存儲是索引鍵和主鍵值，以此作為指向行的“指針”。如下圖：

圖片

B+ 樹葉子節點存儲了數據，非葉子節點（索引節點）則存儲了 key 和指針。這樣存儲的優勢是可以在索引節點通過二分查找快速找到數據所在頁，時間復雜度為 O(log n)。找到數據頁后再去數據頁中找數據就很容易了。

圖片

前面講到，InnoDB 以頁為單位來存儲數據，每頁 16k，那如果一條數據占 1k 的空間，那每頁可以存儲 16 條數據。

而索引節點保存的是 key 和指針。假如 key 的數據類型是 bigint，占 8B，指針大小在 InnoDB 中固定占 6B，那索引節點占空間大小為 14B，那每頁存放的索引節點就是 1170。

16 * 1024B/14B = 1170。

因此假如 B+ 樹高度為 2 層，則存放的數據為 1170（頁）* 16（每頁 16 條數據）= 18720。 同理如果 B+ 樹高度為 3 層，則存放的數據為 1170（頁）* 1170（每頁 1170 索引節點）* 16（每頁 16 條數據）= 21902400。

回到問題，一張表中有 2 千萬條數據，B+ 樹有幾層？如果小于等于 21902400 條，則 B+ 樹是 3 層，如果大于 21902400，則 B+ 樹是 4 層。

注意前提條件，一條數據占用空間大小是 1k，索引節點（索引節點）中 key 占用空間為 8B。

總結

本節以一道經典的面試題，引出了 MySQL 中 InnoDB 的存儲結構。理解了這個存儲結構，就可以很好的理解索引和數據查找原理了。