一、InnoDB一棵B+樹可以存放多少行數(shù)據(jù)？

InnoDB一棵B+樹可以存放多少行數(shù)據(jù)？這個問題的簡單回答是：約2千萬。為什么是這么多呢？因為這是可以算出來的，要搞清楚這個問題，我們先從InnoDB索引數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)組織方式說起。

我們都知道計算機在存儲數(shù)據(jù)的時候，有最小存儲單元，這就好比我們今天進行現(xiàn)金的流通最小單位是一毛。在計算機中磁盤存儲數(shù)據(jù)最小單元是扇區(qū)，一個扇區(qū)的大小是512字節(jié)，而文件系統(tǒng)（例如XFS/EXT4）他的最小單元是塊，一個塊的大小是4k，而對于我們的InnoDB存儲引擎也有自己的最小儲存單元——頁（Page），一個頁的大小是16K。 

二、下面幾張圖可以幫你理解最小存儲單元：

文件系統(tǒng)中一個文件大小只有1個字節(jié)，但不得不占磁盤上4KB的空間。

innodb的所有數(shù)據(jù)文件（后綴為ibd的文件），他的大小始終都是16384（16k）的整數(shù)倍。

   

磁盤扇區(qū)、文件系統(tǒng)、InnoDB存儲引擎都有各自的最小存儲單元。

在MySQL中我們的InnoDB頁的大小默認是16k，當然也可以通過參數(shù)設(shè)置：

    

數(shù)據(jù)表中的數(shù)據(jù)都是存儲在頁中的，所以一個頁中能存儲多少行數(shù)據(jù)呢？假設(shè)一行數(shù)據(jù)的大小是1k，那么一個頁可以存放16行這樣的數(shù)據(jù)。

如果數(shù)據(jù)庫只按這樣的方式存儲，那么如何查找數(shù)據(jù)就成為一個問題，因為我們不知道要查找的數(shù)據(jù)存在哪個頁中，也不可能把所有的頁遍歷一遍，那樣太慢了。所以人們想了一個辦法，用B+樹的方式組織這些數(shù)據(jù)。如圖所示：

    

我們先將數(shù)據(jù)記錄按主鍵進行排序，分別存放在不同的頁中（為了便于理解我們這里一個頁中只存放3條記錄，實際情況可以存放很多），除了存放數(shù)據(jù)的頁以外，還有存放鍵值+指針的頁，如圖中page number=3的頁，該頁存放鍵值和指向數(shù)據(jù)頁的指針，這樣的頁由N個鍵值+指針組成。當然它也是排好序的。這樣的數(shù)據(jù)組織形式，我們稱為索引組織表。現(xiàn)在來看下，要查找一條數(shù)據(jù)，怎么查？

如select * from user where id=5 ;

這里id是主鍵,我們通過這棵B+樹來查找，首先找到根頁，你怎么知道user表的根頁在哪呢？其實每張表的根頁位置在表空間文件中是固定的，即page number=3的頁（這點我們下文還會進一步證明），找到根頁后通過二分查找法，定位到id=5的數(shù)據(jù)應該在指針P5指向的頁中，那么進一步去page number=5的頁中查找，同樣通過二分查詢法即可找到id=5的記錄：

| 5 | zhao2 | 27 |

現(xiàn)在我們清楚了InnoDB中主鍵索引B+樹是如何組織數(shù)據(jù)、查詢數(shù)據(jù)的，我們總結(jié)一下：

1、InnoDB存儲引擎的最小存儲單元是頁，頁可以用于存放數(shù)據(jù)也可以用于存放鍵值+指針，在B+樹中葉子節(jié)點存放數(shù)據(jù)，非葉子節(jié)點存放鍵值+指針。

2、索引組織表通過非葉子節(jié)點的二分查找法以及指針確定數(shù)據(jù)在哪個頁中，進而在去數(shù)據(jù)頁中查找到需要的數(shù)據(jù)； 

三、那么回到我們開始的問題，通常一棵B+樹可以存放多少行數(shù)據(jù)？

這里我們先假設(shè)B+樹高為2，即存在一個根節(jié)點和若干個葉子節(jié)點，那么這棵B+樹的存放總記錄數(shù)為：根節(jié)點指針數(shù)*單個葉子節(jié)點記錄行數(shù)。

上文我們已經(jīng)說明單個葉子節(jié)點（頁）中的記錄數(shù)=16K/1K=16。（這里假設(shè)一行記錄的數(shù)據(jù)大小為1k，實際上現(xiàn)在很多互聯(lián)網(wǎng)業(yè)務數(shù)據(jù)記錄大小通常就是1K左右）。

那么現(xiàn)在我們需要計算出非葉子節(jié)點能存放多少指針？

其實這也很好算，我們假設(shè)主鍵ID為bigint類型，長度為8字節(jié)，而指針大小在InnoDB源碼中設(shè)置為6字節(jié)，這樣一共14字節(jié)，我們一個頁中能存放多少這樣的單元，其實就代表有多少指針，即16384/14=1170 。那么可以算出一棵高度為2的B+樹，能存放1170*16=18720 條這樣的數(shù)據(jù)記錄。

根據(jù)同樣的原理我們可以算出一個高度為3的B+樹可以存放 ：1170117016=21902400 條這樣的記錄。

所以在InnoDB中B+樹高度一般為1-3層，它就能滿足千萬級的數(shù)據(jù)存儲。在查找數(shù)據(jù)時一次頁的查找代表一次IO，所以通過主鍵索引查詢通常只需要1-3次IO操作即可查找到數(shù)據(jù)。 

四、怎么得到InnoDB主鍵索引B+樹的高度？

上面我們通過推斷得出B+樹的高度通常是1-3，下面我們從另外一個側(cè)面證明這個結(jié)論。在InnoDB的表空間文件中，約定page number為3 的代表主鍵索引的根頁，而在根頁偏移量為64 的地方存放了該B+樹的page level。如果page level為1，樹高為2，page level為2，則樹高為3。即B+樹的高度=page level+1；下面我們將從實際環(huán)境中嘗試找到這個page level。

在實際操作之前，你可以通過InnoDB元數(shù)據(jù)表確認主鍵索引根頁的page number為3，你也可以從《InnoDB存儲引擎》這本書中得到確認。

    

執(zhí)行結(jié)果：

    

可以看出數(shù)據(jù)庫dbt3下的customer表、lineitem表主鍵索引根頁的page number均為3，而其他的二級索引page number為4。關(guān)于二級索引與主鍵索引的區(qū)別請參考MySQL相關(guān)書籍，本文不在此介紹。

下面我們對數(shù)據(jù)庫表空間文件做想相關(guān)的解析：

因為主鍵索引B+樹的根頁在整個表空間文件中的第3個頁開始，所以可以算出它在文件中的偏移量：16384*3=49152（16384為頁大小） 。

另外根據(jù)《InnoDB存儲引擎》中描述在根頁的64偏移量位置前2個字節(jié)，保存了page level的值，因此我們想要的page level的值在整個文件中的偏移量為：16384*3+64=49152+64=49216 ，前2個字節(jié)中。

接下來我們用hexdump工具，查看表空間文件指定偏移量上的數(shù)據(jù)：

linetem表的page level為2，B+樹高度為page level+1=3；region表的page level為0，B+樹高度為page level+1=1；customer表的page level為2，B+樹高度為page level+1=3；

這三張表的數(shù)據(jù)量如下：

五、小結(jié)

lineitem表的數(shù)據(jù)行數(shù)為600多萬，B+樹高度為3，customer表數(shù)據(jù)行數(shù)只有15萬，B+樹高度也為3?？梢钥闯霰M管數(shù)據(jù)量差異較大，這兩個表樹的高度都是3，換句話說這兩個表通過索引查詢效率并沒有太大差異，因為都只需要做3次IO。那么如果有一張表行數(shù)是一千萬，那么他的B+樹高度依舊是3，查詢效率仍然不會相差太大。

region表只有5行數(shù)據(jù)，當然他的B+樹高度為1。