大家好，我是君哥。

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

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

InnoDB 存儲(chǔ)

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

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

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

B+ 樹(shù)索引

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

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

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

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

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

16 * 1024B/14B = 1170。

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

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

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

總結(jié)

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