簡介
為什么Mysql考慮使用B+樹贴浙，而不是B樹酵颁，其實我們可以先了解下B樹和B+樹的特點來看下米丘。
B樹特點
※ 樹的每個結(jié)點都會存儲數(shù)據(jù)
※ 單次查詢不一定要遍歷到樹的根部蚕甥，平均查詢時間會比較快
B+樹特點
※ 非葉子節(jié)點不存儲數(shù)據(jù)蝌以，只存儲（冗余）索引炕舵，索引包含主鍵和指針
※ 葉子節(jié)點才真正存儲數(shù)據(jù)
※ 每個葉子節(jié)點互相鏈表相連，保證了范圍查詢的時效性(頁之間用雙向鏈表連接跟畅，數(shù)據(jù)間用單項鏈表鏈接)
※ B+樹只有葉子節(jié)點才存儲數(shù)據(jù)咽筋，葉子節(jié)點包含雙向指針指向，所以對于范圍查詢B+樹明顯優(yōu)于B樹徊件。
※ IO對性能的影響晤硕，B樹的每個節(jié)點都存儲數(shù)據(jù)，而B+樹只有葉子節(jié)點才存儲數(shù)據(jù)庇忌，每個葉子所以查找相同數(shù)據(jù)量的情況下舞箍，B樹的高度更高，IO更頻繁皆疹，效率自然就降低了疏橄。
InnoDB存儲單位
InnoDB最小存儲單位是頁，葉子節(jié)點和非葉子節(jié)點最小單位都是頁略就，頁大小Mysql 默認設(shè)定16384字節(jié)捎迫，約為16KB。
// 可查看innodb_page_size 大小
show GLOBAL VARIABLES like "innodb_page_size";
InnoDB引擎-文件系統(tǒng)-磁盤扇區(qū)關(guān)系
1）磁盤扇區(qū)：磁盤的最小存儲單元表牢，默認512字節(jié)窄绒。
2）文件系統(tǒng)最小單位塊(機械硬盤一個扇區(qū)512字節(jié)，SSD固態(tài)硬盤使用4K對齊按照4K扇區(qū)規(guī)則寫入數(shù)據(jù))崔兴。4k = 8個扇區(qū)彰导。盡管一個文件只有1個字節(jié)，仍然占用4k空間
3）innodb的所有數(shù)據(jù)文件（后綴為ibd的文件）敲茄，他的大小始終都是16384（16k）的整數(shù)倍.
InnoDB高度計算
我們假設(shè)主鍵ID為bigint類型位谋，長度為8字節(jié)，而指針大小在InnoDB源碼中設(shè)置為6字節(jié)堰燎，這樣一共14字節(jié)
我們一個頁中能存放多少這樣的索引元素掏父，其實就代表有多少指針，即16384/14=1170;
假設(shè)一行記錄的數(shù)據(jù)大小為1k秆剪，實際上現(xiàn)在很多互聯(lián)網(wǎng)業(yè)務(wù)數(shù)據(jù)記錄大小通常就是1K左右
高度為2的B+樹能存放1170×16=18720
高度為3的B+樹能存放1170×1170×16 = 21902400
IB+樹高度一般為1-3層赊淑，它就能滿足千萬級的數(shù)據(jù)存儲爵政。
在查找數(shù)據(jù)時一次頁的查找代表一次IO，所以通過主鍵索引查詢通常只需要1-3次IO操作即可查找到數(shù)據(jù)陶缺。
一般根節(jié)點是常駐內(nèi)存的钾挟，所以一般我們查找千萬級別的數(shù)據(jù)，只需要 2 次磁盤 IO组哩。
