大家好，我是君哥。

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

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

InnoDB 存儲

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

我們知道，計算機中，磁盤存儲數(shù)據(jù)的最小單位是扇區(qū)，一個扇區(qū)大小為 512B。而文件系統(tǒng)的最小單位是塊，一個塊大小是 4K。

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

圖片

B+ 樹索引

跟 MyISAM 不一樣的是，InnoDB 使用聚簇索引，葉子節(jié)點存儲數(shù)據(jù)，不用獨立的行存儲。下面是 MyISAM 的存儲結(jié)構(gòu)：

圖片

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

圖片

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

圖片

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

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

16 * 1024B/14B = 1170。

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

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

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

總結(jié)

本節(jié)以一道經(jīng)典的面試題，引出了 MySQL 中 InnoDB 的存儲結(jié)構(gòu)。理解了這個存儲結(jié)構(gòu)，就可以很好的理解索引和數(shù)據(jù)查找原理了。