InnoDB的一棵B+樹可以存放多少行數(shù)據(jù)扒秸？
答案：約2千萬
為什么是這么多播演？
因為這是可以算出來的，要搞清楚這個問題伴奥，先從InnoDB索引數(shù)據(jù)結構写烤、數(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ù)據(jù)都是存儲在頁中的居暖，所以一個頁中能存儲多少行數(shù)據(jù)呢？
假設一行數(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ù)的。
總結一下：
InnoDB存儲引擎的最小存儲單元是頁坠非，頁可以用于存放數(shù)據(jù)也可以用于存放鍵值+指針敏沉，在B+樹中葉子節(jié)點存放數(shù)據(jù)，非葉子節(jié)點存放鍵值+指針炎码。
索引組織表通過非葉子節(jié)點的二分查找法以及指針確定數(shù)據(jù)在哪個頁中盟迟，進而在去數(shù)據(jù)頁中查找到需要的數(shù)據(jù)；
那么回到我們開始的問題潦闲，通常一棵B+樹可以存放多少行數(shù)據(jù)攒菠？
這里我們先假設B+樹高為2，即存在一個根節(jié)點和若干個葉子節(jié)點歉闰，那么這棵B+樹的存放總記錄數(shù)為：根節(jié)點指針數(shù)*單個葉子節(jié)點記錄行數(shù)辖众。
上文已經(jīng)說明單個葉子節(jié)點（頁）中的記錄數(shù)=16K/1K=16。（這里假設一行記錄的數(shù)據(jù)大小為1k和敬，實際上現(xiàn)在很多互聯(lián)網(wǎng)業(yè)務數(shù)據(jù)記錄大小通常就是1K左右）凹炸。
那么現(xiàn)在需要計算出非葉子節(jié)點能存放多少指針？
其實這也很好算昼弟，假設主鍵ID為bigint類型啤它，長度為8字節(jié)，而指針大小在InnoDB源碼中設置為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搂漠，下面從另外一個側面證明這個結論。
在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存儲引擎》這本書中得到確認筋帖。
可以看出數(shù)據(jù)庫dbt3下的customer表、lineitem表主鍵索引根頁的page number均為3冤馏，而其他的二級索引page number為4日麸。
關于二級索引與主鍵索引的區(qū)別請參考MySQL相關書籍，本文不在此介紹逮光。
下面對數(shù)據(jù)庫表空間文件做想相關的解析：
因為主鍵索引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ù)量如下：
總結：
lineitem表的數(shù)據(jù)行數(shù)為600多萬异吻，B+樹高度為3裹赴，customer表數(shù)據(jù)行數(shù)只有15萬，B+樹高度也為3诀浪∑宸担可以看出盡管數(shù)據(jù)量差異較大，這兩個表樹的高度都是3
換句話說這兩個表通過索引查詢效率并沒有太大差異雷猪，因為都只需要做3次IO睛竣。那么如果有一張表行數(shù)是一千萬，那么他的B+樹高度依舊是3求摇，查詢效率仍然不會相差太大射沟。
region表只有5行數(shù)據(jù)殊者，當然他的B+樹高度為1。
面試題
有一道MySQL的面試題验夯，為什么MySQL的索引要使用B+樹而不是其它樹形結構?比如B樹猖吴？
這個問題的復雜版本可以參考本文；
簡單回答是：
因為B樹不管葉子節(jié)點還是非葉子節(jié)點挥转，都會保存數(shù)據(jù)距误，這樣導致在非葉子節(jié)點中能保存的指針數(shù)量變少（有些資料也稱為扇出）
指針少的情況下要保存大量數(shù)據(jù)，只能增加樹的高度扁位，導致IO操作變多准潭，查詢性能變低；
小結
本文從一個問題出發(fā)域仇，逐步介紹了InnoDB索引組織表的原理刑然、查詢方式，并結合已有知識暇务，回答該問題泼掠，結合實踐來證明。
當然為了表述簡單易懂垦细，文中忽略了一些細枝末節(jié)择镇，比如一個頁中不可能所有空間都用于存放數(shù)據(jù)，它還會存放一些少量的其他字段比如page level括改，index number等等腻豌，另外還有頁的填充因子也導致一個頁不可能全部用于保存數(shù)據(jù)。
寫在最后
歡迎大家關注我的公眾號【風平浪靜如碼】嘱能，海量Java相關文章吝梅，學習資料都會在里面更新，整理的資料也會放在里面惹骂。
覺得寫的還不錯的就點個贊苏携，加個關注唄！點關注对粪，不迷路右冻，持續(xù)更新！Ｖ谩纱扭！
