前言
開門見山诫肠，面對(duì)這樣一個(gè)問題矾克，你將如何作答症概？
1千萬油航，2千萬糊闽，或者上億條數(shù)據(jù)啥箭？具體的答案不重要欢顷，當(dāng)然肯定也不會(huì)是一個(gè)固定的數(shù)目，今天我們就一起來探討探討這個(gè)問題捉蚤。
InnoDB是一種兼顧了高可靠性和高性能的通用存儲(chǔ)引擎抬驴，它擁有諸多功能和特性，體系結(jié)構(gòu)和工作原理也比較復(fù)雜缆巧。真要講明白說透徹布持，不是一兩篇博文能夠?qū)崿F(xiàn)的，也不是今天的重點(diǎn)陕悬。
所以题暖，本文不涉及太多的原理性知識(shí)，咱們就針對(duì)開頭提出的問題捉超，通過熟悉一些基本的概念和利用工具來驗(yàn)證胧卤，對(duì)這個(gè)問題做到心中有數(shù)。
文件結(jié)構(gòu)
我們知道拼岳，InnoDB引擎是支持事務(wù)的枝誊，所以表里的數(shù)據(jù)肯定都是存儲(chǔ)在磁盤上的。如果在test數(shù)據(jù)庫下創(chuàng)建兩個(gè)表：t1和t2惜纸，那么在相應(yīng)的數(shù)據(jù)目錄下就會(huì)發(fā)現(xiàn)兩個(gè)文件叶撒。
[root@localhost test]# ls
db.opt t1.frm t1.ibd t2.frm t2.ibd
[root@localhost test]# pwd
/var/lib/mysql/test
其中，frm文件是表結(jié)構(gòu)信息耐版，ibd文件是表中的數(shù)據(jù)祠够。
表結(jié)構(gòu)信息包含MySQL表的元數(shù)據(jù)（例如表定義）的文件，比如表名粪牲、表有多少列古瓤、列的數(shù)據(jù)類型啥的，不重要，我們先不管落君；
ibd文件存儲(chǔ)的是表中的數(shù)據(jù)穿香，比如數(shù)據(jù)行和索引。這個(gè)文件比較重要叽奥，它是今天我們的重點(diǎn)研究對(duì)象扔水。
我們說，MySQL表里的數(shù)據(jù)都是存放在磁盤上的朝氓。那么在磁盤上魔市，最小單元是扇區(qū)，每個(gè)扇區(qū)可以存放512個(gè)字節(jié)的數(shù)據(jù)赵哲；操作系統(tǒng)中最小單元是塊（block）待德，最小單位是4kb。
在Windows系統(tǒng)中枫夺，我們可以通過fsutil fsinfo ntfsinfo c:來查看将宪。
C:\Windows\system32>fsutil fsinfo ntfsinfo c:
NTFS 卷序列號(hào): 0x78f40b2cf40aec66
NTFS 版本: 3.1
LFS 版本: 2.0
扇區(qū)數(shù)量: 0x000000001bcb6fff
簇總數(shù): 0x0000000003796dff
可用簇: 0x0000000000a63a03
保留總數(shù): 0x00000000000017c3
每個(gè)扇區(qū)字節(jié)數(shù): 512
每個(gè)物理扇區(qū)字節(jié)數(shù): 4096
每個(gè)簇字節(jié)數(shù): 4096
每個(gè) FileRecord 段字節(jié)數(shù): 1024
每個(gè) FileRecord 段簇?cái)?shù): 0
在Linux系統(tǒng)上，可以通過以下兩個(gè)命令查看橡庞，這取決于文件系統(tǒng)的格式较坛。
xfs_growfs /dev/mapper/centos-root | grep bsize
tune2fs -l /dev/mapper/centos-root | grep Block
我們拉回來接著說MySQL，InnoDB存儲(chǔ)引擎它也是有最小存儲(chǔ)單位的扒最，叫做頁（Page）丑勤，默認(rèn)大小是16kb。
我們新創(chuàng)建一個(gè)表 t3吧趣，里面任何數(shù)據(jù)都沒有法竞，我們來看它的ibd文件。
[root@localhost test]# ll
總用量 18579600
-rw-r-----. 1 mysql mysql 67 11月 30 20:59 db.opt
-rw-r-----. 1 mysql mysql 12756 12月 7 21:10 t1.frm
-rw-r-----. 1 mysql mysql 13077839872 12月 7 21:37 t1.ibd
-rw-r-----. 1 mysql mysql 8608 12月 7 21:43 t2.frm
-rw-r-----. 1 mysql mysql 5947523072 12月 7 21:52 t2.ibd
-rw-r-----. 1 mysql mysql 12756 12月 8 21:02 t3.frm
-rw-r-----. 1 mysql mysql 98304 12月 8 21:02 t3.ibd
不僅是t3强挫，我們看到岔霸，任何表的ibd文件大小，它永遠(yuǎn)是16k的整數(shù)倍俯渤。理解這個(gè)事非常重要呆细，MySQL從磁盤加載數(shù)據(jù)是按照頁來讀取的，即便你查詢一條數(shù)據(jù)稠诲，它也會(huì)讀取一頁16k的數(shù)據(jù)出來侦鹏。
聚簇索引
數(shù)據(jù)庫表中的數(shù)據(jù)都是存儲(chǔ)在頁里的，那么這一個(gè)頁可以存放多少條記錄呢臀叙？
這取決于一行記錄的大小是多少，假如一行數(shù)據(jù)大小是1k价卤，那么理論上一頁就可以放16條數(shù)據(jù)劝萤。
當(dāng)然，查詢數(shù)據(jù)的時(shí)候慎璧，MySQL也不能把所有的頁都遍歷一遍床嫌，所以就有了索引跨释，InnoDB存儲(chǔ)引擎用B+樹的方式來構(gòu)建索引。
聚簇索引就是按照每張表的主鍵構(gòu)造一顆B+樹厌处，葉子節(jié)點(diǎn)存放的是整行記錄數(shù)據(jù)鳖谈，在非葉子節(jié)點(diǎn)上存放的是鍵值以及指向數(shù)據(jù)頁的指針，同時(shí)每個(gè)數(shù)據(jù)頁之間都通過一個(gè)雙向鏈表來進(jìn)行鏈接阔涉。
如上圖所示缆娃，就是一顆聚簇索引樹的大致結(jié)構(gòu)。它先將數(shù)據(jù)記錄按照主鍵排序瑰排，放在不同的頁中贯要，下面一行是數(shù)據(jù)頁。上面的非葉子節(jié)點(diǎn)椭住，存放主鍵值和一個(gè)指向頁的指針崇渗。
當(dāng)我們通過主鍵來查詢的時(shí)候，比如id=6的條件京郑，就是通過這顆B+樹來查找數(shù)據(jù)的過程宅广。它先找到根頁面（page offset=3），然后通過二分查找些举，定位到id=6的數(shù)據(jù)在指針為5的頁上跟狱。然后進(jìn)一步的去page offset=5的頁面上加載數(shù)據(jù)。
在這里金拒，我們需要理解兩件事：
上圖中B+樹的根節(jié)點(diǎn)（page offset=3）兽肤，是固定不會(huì)變化的。只要表創(chuàng)建了聚簇索引绪抛，它的根節(jié)點(diǎn)頁號(hào)就被記錄到某個(gè)地方了资铡。還有一點(diǎn)，B+樹索引本身并不能直接找到具體的一條記錄幢码，只能知道該記錄在哪個(gè)頁上笤休，數(shù)據(jù)庫會(huì)把頁載入到內(nèi)存，再通過二分查找定位到具體的記錄症副。
現(xiàn)在我們知道了InnoDB存儲(chǔ)引擎最小存儲(chǔ)單元是頁店雅，在B+樹索引結(jié)構(gòu)里，頁可以放一行一行的數(shù)據(jù)（葉子節(jié)點(diǎn)）贞铣，也可以放主鍵+指針（非葉子節(jié)點(diǎn)）闹啦。
上面已經(jīng)說過，假如一行數(shù)據(jù)大小是1k辕坝，那么理論上一頁就可以放16條數(shù)據(jù)窍奋。那一頁可以放多少主鍵+指針呢？
假如我們的主鍵id為bigint類型，長度為8字節(jié)琳袄，而指針大小在InnoDB源碼中設(shè)置為6字節(jié)江场。這樣算下來就是 16384 / 14 = 1170，就是說一個(gè)頁上可以存放1170個(gè)指針窖逗。
一個(gè)指針指向一個(gè)存放記錄的頁址否，一個(gè)頁里可以放16條數(shù)據(jù)，那么一顆高度為2的B+樹就可以存放 1170 * 16=18720 條數(shù)據(jù)碎紊。同理佑附，高度為3的B+樹，就可以存放 1170 * 1170 * 16 = 21902400 條記錄矮慕。
理論上就是這樣帮匾，在InnoDB存儲(chǔ)引擎中，B+樹的高度一般為2-4層痴鳄，就可以滿足千萬級(jí)數(shù)據(jù)的存儲(chǔ)瘟斜。查找數(shù)據(jù)的時(shí)候，一次頁的查找代表一次IO痪寻，那我們通過主鍵索引查詢的時(shí)候螺句，其實(shí)最多只需要2-4次IO就可以了。
那么橡类，實(shí)際上到底是不是這樣呢蛇尚？我們接著往下看。
頁的類型
在開始驗(yàn)證之前顾画，我們不僅需要了解頁取劫，還需要知道，在InnoDB引擎中研侣，頁并不是只有一種谱邪。常見的頁類型有：
- 數(shù)據(jù)頁，B-tree Node庶诡；
- undo頁惦银，undo Log Page；
- 系統(tǒng)頁末誓，System Page扯俱；
- 事務(wù)數(shù)據(jù)頁，Transaction system Page喇澡；
- 插入緩沖位圖頁迅栅，Insert Buffer Bitmap；
- 插入緩沖空閑列表頁晴玖，Insert Buffer Free List库继；
- 未壓縮的二進(jìn)制大對(duì)象頁箩艺，Uncompressed BLOB Page窜醉；
在這里我們重點(diǎn)來看 B-tree Node宪萄，我們的索引和數(shù)據(jù)就放在這種頁上。既然有不同的頁類型榨惰，我們怎么知道當(dāng)前的頁屬于什么頁呢拜英？
那么我們就需要大概了解下數(shù)據(jù)頁的結(jié)構(gòu)，數(shù)據(jù)頁由七個(gè)部分組成琅催，每個(gè)部分都有不同的含義居凶。
- File Header，文件頭藤抡，固定38字節(jié)侠碧；
- Page Header，頁頭缠黍，固定56字節(jié)弄兜；
- Infimum + supremum，固定26字節(jié)瓷式；
- User Records替饿，用戶記錄，即行記錄贸典，大小不固定视卢；
- Free Space，空閑空間廊驼，大小不固定据过；
- Page Directort，頁目錄妒挎，大小不固定绳锅；
- File Trailer，文件結(jié)尾信息饥漫，固定8字節(jié)榨呆。
其中，F(xiàn)ile Header用來記錄頁的一些頭信息庸队，共占用38個(gè)字節(jié)积蜻。在這個(gè)頭信息里，我們可以獲取到該頁在表空間里的偏移值和這個(gè)數(shù)據(jù)頁的類型彻消。
接下來是Page Header竿拆，它記錄的是數(shù)據(jù)頁的狀態(tài)信息，共占用56個(gè)字節(jié)宾尚。在這一部分丙笋，我們可以獲取到兩個(gè)重要的信息：該頁中記錄的數(shù)量和當(dāng)前頁在索引樹的層級(jí)谢澈，其中0x00代表葉子節(jié)點(diǎn)，比如聚簇索引中的葉子節(jié)點(diǎn)放的就是整行數(shù)據(jù)御板，它總是在第0層锥忿。
驗(yàn)證
前面我們已經(jīng)說過，ibd文件就是表數(shù)據(jù)文件怠肋。這個(gè)文件會(huì)隨著數(shù)據(jù)庫表里數(shù)據(jù)的增長而增長敬鬓，不過它始終會(huì)是16k的整數(shù)倍。里面就是一個(gè)個(gè)的頁笙各，那我們就可以一個(gè)一個(gè)頁的來解析钉答，通過文件頭可以判斷它是什么頁，找到 B-tree Node杈抢，就可以看到里面的 Page Level数尿，它的值+1，就代表了當(dāng)前B+樹的高度惶楼。
我們現(xiàn)在就來重新創(chuàng)建一個(gè)表右蹦，為了使這個(gè)表中的數(shù)據(jù)一行大小為1k，我們設(shè)置幾個(gè)char(255)的字段即可鲫懒。
CREATE TABLE `t5` (
`id` bigint(8) NOT NULL,
`c1` char(245) NOT NULL DEFAULT '1',
`c2` char(255) NOT NULL DEFAULT '1',
`c3` char(255) NOT NULL DEFAULT '1',
`c4` char(255) NOT NULL DEFAULT '1',
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
然后筆者寫了一個(gè)存儲(chǔ)過程嫩实，用來批量插入數(shù)據(jù)用的，為了加快批量插入的速度窥岩，筆者還修改了innodb_flush_log_at_trx_commit=0甲献，切記生產(chǎn)環(huán)境可不要這樣玩。
BEGIN
DECLARE i int DEFAULT 0;
select ifnull(max(id),0) into i from t5;
set i = i+1;
WHILE i <= 100000 DO
insert into t5(id)value(i);
set i = i+1;
END WHILE;
END
innodbPageInfo.jar是筆者用Java代碼寫的一個(gè)工具類颂翼，用來輸出ibd文件中晃洒，頁的信息。
-path 后面是文件的路徑朦乏，-v 是否顯示頁的詳情信息球及，0是 1否。
上面我們創(chuàng)建了t5這張表呻疹，一條數(shù)據(jù)還沒有的情況下吃引，我們看一下這個(gè)ibd文件的信息。
[root@localhost innodbInfo]# java -jar innodbPageInfo.jar -path /var/lib/mysql/test/t5.ibd -v 0
page offset 00000000,page type <File Space Header>
page offset 00000001,page type <Insert Buffer Bitmap>
page offset 00000002,page type <File Segment inode>
page offset 00000003,page type <B-tree Node>,page level <0000>
page offset 00000000,page type <Freshly Allocated Page>
page offset 00000000,page type <Freshly Allocated Page>
數(shù)據(jù)頁總記錄數(shù):0
Total number of page: 6
Insert Buffer Bitmap: 1
File Segment inode: 1
B-tree Node: 1
File Space Header: 1
Freshly Allocated Page: 2
[root@localhost innodbInfo]#
t5表現(xiàn)在沒有任何數(shù)據(jù)刽锤，它的ibd文件大小是98304镊尺，也就是說一共有6個(gè)頁。其中第四個(gè)頁（page offset 3）是數(shù)據(jù)頁并思，page level等于0庐氮，代表該頁為葉子節(jié)點(diǎn)。因?yàn)槟壳斑€沒有數(shù)據(jù)宋彼，可以認(rèn)為B+樹的索引只有1層弄砍。
我們接著插入10條數(shù)據(jù)仙畦，這個(gè)page level還是為0，B+樹的高度還是1音婶，這是因?yàn)橐粋€(gè)頁大約能存放16條大小為1k的數(shù)據(jù)慨畸。
page offset 00000003,page type <B-tree Node>,page level <0000>
數(shù)據(jù)頁總記錄數(shù):10
Total number of page: 6
當(dāng)我們插入15條數(shù)據(jù)的時(shí)候，一個(gè)頁就放不下了桃熄，原本為新分配的頁（Freshly Allocated Page）就會(huì)變成數(shù)據(jù)頁先口，原來的根頁面（page offset=3）就會(huì)升級(jí)成存儲(chǔ)目錄項(xiàng)的頁。offset 04 和 05就變成了葉子節(jié)點(diǎn)的數(shù)據(jù)頁瞳收，所以現(xiàn)在整個(gè)B+樹的高度為2。
page offset 00000003,page type <B-tree Node>,page level <0001>
page offset 00000004,page type <B-tree Node>,page level <0000>
page offset 00000005,page type <B-tree Node>,page level <0000>
數(shù)據(jù)頁總記錄數(shù):15
Total number of page: 6
繼續(xù)插入10000條數(shù)據(jù)厢汹，我們再來看一下B+樹高的情況螟深。當(dāng)然現(xiàn)在信息比較多了，我們把輸出結(jié)果寫到文件里烫葬。
java -jar innodbPageInfo.jar -path /var/lib/mysql/test/t5.ibd -v 0 > t5.txt
截取部分結(jié)果如下：
[root@localhost innodbInfo]# vim t5.txt
page offset 00000003,page type <B-tree Node>,page level <0001>
page offset 00000004,page type <B-tree Node>,page level <0000>
page offset 00000005,page type <B-tree Node>,page level <0000>
page offset 00000000,page type <Freshly Allocated Page>
數(shù)據(jù)頁總記錄數(shù):10000
Total number of page: 1216
B-tree Node: 716
可以看到界弧，1萬條1k大小的記錄，一共用了716個(gè)數(shù)據(jù)頁搭综，根頁面顯示的樹高還是2層垢箕。
前面我們計(jì)算過，2層的B+樹理論上可以存放18000條左右兑巾，筆者測試大約13000條數(shù)據(jù)左右条获，B+樹就會(huì)成為3層了。
page offset 00000003,page type <B-tree Node>,page level <0002>
數(shù)據(jù)頁總記錄數(shù):13000
Total number of page: 1472
B-tree Node: 933
原因也不難理解蒋歌，因?yàn)槊總€(gè)頁不可能只放數(shù)據(jù)本身帅掘。
首先每個(gè)頁都有一些固定的格式，比如文件頭部堂油、頁面頭部修档、文件尾部這些，我們的數(shù)據(jù)放在用戶記錄這部分里的府框；
其次吱窝，用戶記錄也不只放數(shù)據(jù)行，每個(gè)數(shù)據(jù)行還有一些其他標(biāo)記迫靖，比如是否刪除院峡、最小記錄、記錄數(shù)袜香、在堆中的位置信息撕予、記錄的類型、下一條記錄的相對(duì)位置等等蜈首；
另外实抡，MySQL參考手冊中也有說到欠母，InnoDB會(huì)保留頁的1/16空閑，以便將來插入或者更新索引使用吆寨，如果主鍵id不是順序插入的赏淌，那可能還不是1/16，會(huì)占用更多的空閑空間啄清。
總之六水，我們理解一個(gè)頁不會(huì)全放數(shù)據(jù)就行了。所以辣卒，實(shí)測跟理論上不一致也是完全正常的掷贾，因?yàn)樯厦娴睦碚摏]有排除這些項(xiàng)。
接著來荣茫，我們再插入1000萬條數(shù)據(jù)想帅，現(xiàn)在ibd文件已經(jīng)達(dá)到11GB。
page offset 00000003,page type <B-tree Node>,page level <0002>
數(shù)據(jù)頁總記錄數(shù):10000000
Total number of page: 725760
B-tree Node: 715059
我們看到啡莉，1千萬條數(shù)據(jù)港准，數(shù)據(jù)頁已經(jīng)有71萬個(gè)，B+樹的高度還是3層咧欣，這也就是說幾萬條數(shù)據(jù)和一千萬條數(shù)據(jù)的查詢效率基本上是一樣的浅缸。
比如我們現(xiàn)在根據(jù)主鍵ID查詢一條數(shù)據(jù)，select * from t5 where id = 6548215; 魄咕，查詢時(shí)間顯示用了0.010秒衩椒。
什么時(shí)候會(huì)到4層呢？大概在1300萬左右蚕礼，B+樹就會(huì)增加樹高到4層烟具。
什么時(shí)候會(huì)到5層呢？筆者沒測試出來奠蹬，因?yàn)椴迦氲?000萬條數(shù)據(jù)的時(shí)候朝聋，ibd數(shù)據(jù)文件大小已經(jīng)55G了，虛擬機(jī)已經(jīng)空間不足了囤躁。冀痕。
page offset 00000003,page type <B-tree Node>,page level <0003>
數(shù)據(jù)頁總記錄數(shù):50000000
B-tree Node: 3575286
即便是5000萬條數(shù)據(jù)，我們通過主鍵ID查詢狸演，查詢時(shí)間也是毫秒級(jí)的言蛇。
理論上要達(dá)到十億 - 百億行數(shù)據(jù)，樹高才能到5層宵距。如果有小伙伴用這種方法腊尚，測試出來5層高的數(shù)據(jù)，歡迎在評(píng)論區(qū)留言满哪，讓我看看婿斥。
另外劝篷，朋友們有沒有意識(shí)到一個(gè)問題？其實(shí)影響B(tài)+樹樹高的因素民宿，不僅是數(shù)據(jù)行娇妓，還有主鍵ID的長度。我們上面的測試中活鹰，ID的類型是bigint(8)哈恰，在其他字段長度均不變的情況下，我們把ID的類型改為int(4)志群，相同的樹高就會(huì)容納更多的數(shù)據(jù)着绷，因?yàn)樗鼏蝹€(gè)頁能承載的指針數(shù)變多了。
CREATE TABLE `t6` (
`id` int(4) NOT NULL,
`c1` char(245) NOT NULL DEFAULT '1',
`c2` char(255) NOT NULL DEFAULT '1',
`c3` char(255) NOT NULL DEFAULT '1',
`c4` char(255) NOT NULL DEFAULT '1',
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
針對(duì)t6這張表赖舟，我們插入16000條數(shù)據(jù)蓬戚，然后輸出一下頁面信息。
page offset 00000003,page type <B-tree Node>,page level <0001>
數(shù)據(jù)頁總記錄數(shù):16000
B-tree Node: 1145
我們來看宾抓，如果按照主鍵ID類型bigint(8)來測試，13000條數(shù)據(jù)的時(shí)候豫喧，樹高就已經(jīng)是3了石洗，現(xiàn)在改為int(4)，16000條數(shù)據(jù)紧显，樹高依然還是2層讲衫。盡管數(shù)據(jù)頁（B-tree Node）數(shù)量還是那么多，變化并不大孵班，但是它不影響樹高涉兽。
ok，看到這里篙程，相信朋友們對(duì)開頭提出的問題已經(jīng)有自己的答案了枷畏，如果你也跟著試一遍，理解可能會(huì)更加深入虱饿。
看到這拥诡，還有道經(jīng)典的面試題：為什么MySQL的索引要使用B+樹而不是其它樹形結(jié)構(gòu)?比如B樹？
簡單來說氮发，其中有一個(gè)原因就是B+樹的高度比較穩(wěn)定渴肉，因?yàn)樗姆侨~子節(jié)點(diǎn)不會(huì)保存數(shù)據(jù)，只保存鍵值和指針的情況下爽冕，一個(gè)頁能承載大量的數(shù)據(jù)仇祭。你想啊，B樹它的非葉子節(jié)點(diǎn)也會(huì)保存數(shù)據(jù)的颈畸，同樣的一行數(shù)據(jù)大小是1kb乌奇，那么它一頁最多也只能保存16個(gè)指針没讲，在大量數(shù)據(jù)的情況下，樹高就會(huì)速度膨脹华弓，導(dǎo)致IO次數(shù)就會(huì)很多食零，查詢就會(huì)變得很慢。
源碼地址
本文的innodbPageInfo.jar代碼是筆者參考 MySQL技術(shù)內(nèi)幕（InnoDB存儲(chǔ)引擎）一書中的工具包寂屏，書里作者是用Python寫的贰谣，所以筆者在這里用Java重新實(shí)現(xiàn)了一遍。
Java版本的源碼我放在GitHub上了：https://github.com/taoxun/innodbPageInfo
已經(jīng)打完包的Jar版本迁霎，也可以下載：https://pan.baidu.com/s/1IZVJRNUk_bPESp5zoQwOvA 提取碼:5rnz吱抚。
朋友們可以拿這個(gè)工具看一看，自己認(rèn)為較大的表考廉，它的B+樹索引到底有幾層秘豹？
參考資料：
姜承堯：《MySQL技術(shù)內(nèi)幕:InnoDB存儲(chǔ)引擎》
天涯淚小武：https://tianyalei.blog.csdn.net/article/details/100015840
飄揚(yáng)的紅領(lǐng)巾：https://www.cnblogs.com/leefreeman/p/8315844.html
MySQL官方參考手冊：https://dev.mysql.com/doc/refman/5.7/en/
