InnoDB一棵B+樹(shù)可以存放2千萬(wàn)數(shù)據(jù)？
InnoDB一棵B+樹(shù)可以存放多少行數(shù)據(jù)？
InnoDB一棵B+樹(shù)可以存放多少行數(shù)據(jù)？這個(gè)問(wèn)題的簡(jiǎn)單回答是：約2千萬(wàn)。為什么是這么多呢？因?yàn)檫@是可以算出來(lái)的，要搞清楚這個(gè)問(wèn)題，我們先從InnoDB索引數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)組織方式說(shuō)起。
我們都知道計(jì)算機(jī)在存儲(chǔ)數(shù)據(jù)的時(shí)候，有最小存儲(chǔ)單元，這就好比我們今天進(jìn)行現(xiàn)金的流通最小單位是一毛。在計(jì)算機(jī)中磁盤(pán)存儲(chǔ)數(shù)據(jù)最小單元是扇區(qū)，一個(gè)扇區(qū)的大小是512字節(jié)，而文件系統(tǒng)（例如XFS/EXT4）他的最小單元是塊，一個(gè)塊的大小是4k，而對(duì)于我們的InnoDB存儲(chǔ)引擎也有自己的最小儲(chǔ)存單元——頁(yè)（Page），一個(gè)頁(yè)的大小是16K。
下面幾張圖可以幫你理解最小存儲(chǔ)單元：
文件系統(tǒng)中一個(gè)文件大小只有1個(gè)字節(jié)，但不得不占磁盤(pán)上4KB的空間。
innodb的所有數(shù)據(jù)文件（后綴為ibd的文件），他的大小始終都是16384（16k）的整數(shù)倍。
磁盤(pán)扇區(qū)、文件系統(tǒng)、InnoDB存儲(chǔ)引擎都有各自的最小存儲(chǔ)單元。
在MySQL中我們的InnoDB頁(yè)的大小默認(rèn)是16k，當(dāng)然也可以通過(guò)參數(shù)設(shè)置：
mysql> show variables like 'innodb_page_size';
+------------------+-------+
| Variable_name ? ?| Value |
+------------------+-------+
| innodb_page_size | 16384 |
+------------------+-------+
1 row in set (0.00 sec)
數(shù)據(jù)表中的數(shù)據(jù)都是存儲(chǔ)在頁(yè)中的，所以一個(gè)頁(yè)中能存儲(chǔ)多少行數(shù)據(jù)呢？假設(shè)一行數(shù)據(jù)的大小是1k，那么一個(gè)頁(yè)可以存放16行這樣的數(shù)據(jù)。
如果數(shù)據(jù)庫(kù)只按這樣的方式存儲(chǔ)，那么如何查找數(shù)據(jù)就成為一個(gè)問(wèn)題，因?yàn)槲覀儾恢酪檎业臄?shù)據(jù)存在哪個(gè)頁(yè)中，也不可能把所有的頁(yè)遍歷一遍，那樣太慢了。所以人們想了一個(gè)辦法，用B+樹(shù)的方式組織這些數(shù)據(jù)。如圖所示：
我們先將數(shù)據(jù)記錄按主鍵進(jìn)行排序，分別存放在不同的頁(yè)中（為了便于理解我們這里一個(gè)頁(yè)中只存放3條記錄，實(shí)際情況可以存放很多），除了存放數(shù)據(jù)的頁(yè)以外，還有存放鍵值+指針的頁(yè)，如圖中page number=3的頁(yè)，該頁(yè)存放鍵值和指向數(shù)據(jù)頁(yè)的指針，這樣的頁(yè)由N個(gè)鍵值+指針組成。當(dāng)然它也是排好序的。這樣的數(shù)據(jù)組織形式，我們稱(chēng)為索引組織表。現(xiàn)在來(lái)看下，要查找一條數(shù)據(jù)，怎么查？
如 select * from user where id=5;
這里id是主鍵,我們通過(guò)這棵B+樹(shù)來(lái)查找，首先找到根頁(yè)，你怎么知道user表的根頁(yè)在哪呢？其實(shí)每張表的根頁(yè)位置在表空間文件中是固定的，即page number=3的頁(yè)（這點(diǎn)我們下文還會(huì)進(jìn)一步證明），找到根頁(yè)后通過(guò)二分查找法，定位到id=5的數(shù)據(jù)應(yīng)該在指針P5指向的頁(yè)中，那么進(jìn)一步去page number=5的頁(yè)中查找，同樣通過(guò)二分查詢法即可找到id=5的記錄：
| 5 | zhao2 | 27 |
現(xiàn)在我們清楚了InnoDB中主鍵索引B+樹(shù)是如何組織數(shù)據(jù)、查詢數(shù)據(jù)的，我們總結(jié)一下：
1、InnoDB存儲(chǔ)引擎的最小存儲(chǔ)單元是頁(yè)，頁(yè)可以用于存放數(shù)據(jù)也可以用于存放鍵值+指針，在B+樹(shù)中葉子節(jié)點(diǎn)存放數(shù)據(jù)，非葉子節(jié)點(diǎn)存放鍵值+指針。
2、索引組織表通過(guò)非葉子節(jié)點(diǎn)的二分查找法以及指針確定數(shù)據(jù)在哪個(gè)頁(yè)中，進(jìn)而在去數(shù)據(jù)頁(yè)中查找到需要的數(shù)據(jù)；
那么回到我們開(kāi)始的問(wèn)題，通常一棵B+樹(shù)可以存放多少行數(shù)據(jù)？
這里我們先假設(shè)B+樹(shù)高為2，即存在一個(gè)根節(jié)點(diǎn)和若干個(gè)葉子節(jié)點(diǎn)，那么這棵B+樹(shù)的存放總記錄數(shù)為：（根節(jié)點(diǎn)指針數(shù)*單個(gè)葉子節(jié)點(diǎn)記錄行數(shù)）。
上文我們已經(jīng)說(shuō)明單個(gè)葉子節(jié)點(diǎn)（頁(yè)）中的記錄數(shù)=16K/1K=16。（這里假設(shè)一行記錄的數(shù)據(jù)大小為1k，實(shí)際上現(xiàn)在很多互聯(lián)網(wǎng)業(yè)務(wù)數(shù)據(jù)記錄大小通常就是1K左右）。
那么現(xiàn)在我們需要計(jì)算出非葉子節(jié)點(diǎn)能存放多少指針？
其實(shí)這也很好算，我們假設(shè)主鍵ID為bigint類(lèi)型，長(zhǎng)度為8字節(jié)，而指針大小在InnoDB源碼中設(shè)置為6字節(jié)，這樣一共14字節(jié)，我們一個(gè)頁(yè)中能存放多少這樣的單元，其實(shí)就代表有多少指針，即16384/14=1170。那么可以算出一棵高度為2的B+樹(shù)，能存放 1170*16=18720條這樣的數(shù)據(jù)記錄。
根據(jù)同樣的原理我們可以算出一個(gè)高度為3的B+樹(shù)可以存放多少條這樣的記錄。
1170*16=18720, (18720*16384)/14=21907748.6條這樣的記錄。
其實(shí)也可以這樣算：1170*1170*16=21902400條這樣的記錄。所以在InnoDB中B+樹(shù)高度一般為1-3層，它就能滿足千萬(wàn)級(jí)的數(shù)據(jù)存儲(chǔ)。在查找數(shù)據(jù)時(shí)一次頁(yè)的查找代表一次IO，所以通過(guò)主鍵索引查詢通常只需要1-3次IO操作即可查找到數(shù)據(jù)。
怎么得到InnoDB主鍵索引B+樹(shù)的高度？
上面我們通過(guò)推斷得出B+樹(shù)的高度通常是1-3，下面我們從另外一個(gè)側(cè)面證明這個(gè)結(jié)論。在InnoDB的表空間文件中，約定page number為3的代表主鍵索引的根頁(yè)，而在根頁(yè)偏移量為64的地方存放了該B+樹(shù)的page level。如果page level為1，樹(shù)高為2，page level為2，則樹(shù)高為3。即B+樹(shù)的高度=page level+1；下面我們將從實(shí)際環(huán)境中嘗試找到這個(gè)page level。
在實(shí)際操作之前，你可以通過(guò)InnoDB元數(shù)據(jù)表確認(rèn)主鍵索引根頁(yè)的page number為3，你也可以從《InnoDB存儲(chǔ)引擎》這本書(shū)中得到確認(rèn)。
SELECT
b.name, a.name, index_id, type, a.space, a.PAGE_NO
FROM
information_schema.INNODB_SYS_INDEXES a,
information_schema.INNODB_SYS_TABLES b
WHERE
a.table_id = b.table_id AND a.space <> 0;
執(zhí)行結(jié)果：
可以看出數(shù)據(jù)庫(kù)dbt3下的customer表、lineitem表主鍵索引根頁(yè)的page number均為3，而其他的二級(jí)索引page number為4。關(guān)于二級(jí)索引與主鍵索引的區(qū)別請(qǐng)參考MySQL相關(guān)書(shū)籍，本文不在此介紹。
下面我們對(duì)數(shù)據(jù)庫(kù)表空間文件做想相關(guān)的解析：
因?yàn)橹麈I索引B+樹(shù)的根頁(yè)在整個(gè)表空間文件中的第3個(gè)頁(yè)開(kāi)始，所以可以算出它在文件中的偏移量：16384*3=49152（16384為頁(yè)大小）。
另外根據(jù)《InnoDB存儲(chǔ)引擎》中描述在根頁(yè)的64偏移量位置前2個(gè)字節(jié)，保存了page level的值，因此我們想要的page level的值在整個(gè)文件中的偏移量為：16384*3+64=49152+64=49216，前2個(gè)字節(jié)中。
接下來(lái)我們用hexdump工具，查看表空間文件指定偏移量上的數(shù)據(jù)：
linetem表的page level為2，B+樹(shù)高度為page level+1=3；region表的page level為0，B+樹(shù)高度為page level+1=1；customer表的page level為2，B+樹(shù)高度為page level+1=3；
這三張表的數(shù)據(jù)量如下：
小結(jié)
lineitem表的數(shù)據(jù)行數(shù)為600多萬(wàn)，B+樹(shù)高度為3，customer表數(shù)據(jù)行數(shù)只有15萬(wàn)，B+樹(shù)高度也為3。可以看出盡管數(shù)據(jù)量差異較大，這兩個(gè)表樹(shù)的高度都是3，換句話說(shuō)這兩個(gè)表通過(guò)索引查詢效率并沒(méi)有太大差異，因?yàn)槎贾恍枰?次IO。那么如果有一張表行數(shù)是一千萬(wàn)，那么他的B+樹(shù)高度依舊是3，查詢效率仍然不會(huì)相差太大。
region表只有5行數(shù)據(jù)，當(dāng)然他的B+樹(shù)高度為1。
最后回顧一道面試題
有一道MySQL的面試題，為什么MySQL的索引要使用B+樹(shù)而不是其它樹(shù)形結(jié)構(gòu)？比如B樹(shù)？
現(xiàn)在這個(gè)問(wèn)題的復(fù)雜版本可以參考本文；
他的簡(jiǎn)單版本回答是：
因?yàn)锽樹(shù)不管葉子節(jié)點(diǎn)還是非葉子節(jié)點(diǎn)，都會(huì)保存數(shù)據(jù)，這樣導(dǎo)致在非葉子節(jié)點(diǎn)中能保存的指針數(shù)量變少（有些資料也稱(chēng)為扇出），指針少的情況下要保存大量數(shù)據(jù)，只能增加樹(shù)的高度，導(dǎo)致IO操作變多，查詢性能變低；
總結(jié)
本文從一個(gè)問(wèn)題出發(fā)，逐步介紹了InnoDB索引組織表的原理、查詢方式，并結(jié)合已有知識(shí)，回答該問(wèn)題，結(jié)合實(shí)踐來(lái)證明。當(dāng)然為了表述簡(jiǎn)單易懂，文中忽略了一些細(xì)枝末節(jié)，比如一個(gè)頁(yè)中不可能所有空間都用于存放數(shù)據(jù)，它還會(huì)存放一些少量的其他字段比如page level，index number等等，另外還有頁(yè)的填充因子也導(dǎo)致一個(gè)頁(yè)不可能全部用于保存數(shù)據(jù)。關(guān)于二級(jí)索引數(shù)據(jù)存取方式可以參考MySQL相關(guān)書(shū)籍，他的要點(diǎn)是結(jié)合主鍵索引進(jìn)行回表查詢。
參考資料：
姜承堯 《MySQL技術(shù)內(nèi)幕:InnoDB存儲(chǔ)引擎》
姜承堯 http://www.innomysql.com/查看-innodb表中每個(gè)的索引高度/
版權(quán)申明：內(nèi)容來(lái)源網(wǎng)絡(luò)，版權(quán)歸原創(chuàng)者所有。除非無(wú)法確認(rèn)，我們都會(huì)標(biāo)明作者及出處，如有侵權(quán)煩請(qǐng)告知，我們會(huì)立即刪除并表示歉意。謝謝!
