MYSQL的B+Tree索引樹高度如何計算

前一段被問到一個平時沒有關注到有關于MYSQL索引相關的問題點，被問到一個表有3000萬記錄，假如有一列占8位位元組的字段，根據這一列建索引的話索引樹的高度是多少？

這一問當時就被問蒙了，平時這也隻關注MySQL索引一般都是都是用B+Tree來存儲維護索引的，還有一些複合索引的最左比對原則等等，還真沒有實際關注過始即然用到索引能提升

查詢的效率，那麼這個索引樹高是多少，給定表和索引字段後怎麼計算出索引樹的高度？下面将用舉例的形式來說明如何計算索引樹的高度。

在舉例之前，先給出一個千萬級記錄表的索引的高度大概在3-5的樣，當時我看到這個數字時也是很驚訝的！

舉例前先做一下舉例時用到的公式的一些次元的說明

假設：

 表的記錄數是N

 每一個BTREE節點平均有B個索引KEY

那麼B+TREE索引樹的高度就是logNB(等價于logN/logB)

由于索引樹每個節點的大小固定，是以索引KEY越小，B值就越大，那麼每個BTREE節點上可以儲存更多的索引KEY，也就是B值越大，索引樹的高度就越小，那麼基于索引的查詢的性能就越高。是以相同表記錄數的情況下，索引KEY越小，索引樹的高度就越小。

現在我們假設表3000W條記錄（因為2^25=33554432），如果每個節點儲存64個索引KEY,那麼索引的高度就是（log2^25)/log64≈ 25/6 ≈ 4.17

通過上面的計算可知，要計一張表索引樹的高度，隻需要知道一個節點有多，進而就能知道每個節點能存儲多少個索引KEY。現代資料庫經過不斷的探索和優化，并結合磁盤的預讀特點，每個索引節點一般都是作業系統頁的整數倍，作業系統頁可通過指令得到該值得大小，且一般是4094，即4k。而InnoDB的pageSize可以通過指令得到，預設值是16k。

以BIGINT為例，存儲大小為8個位元組。INT存儲大小為4個位元組（32位）。索引樹上每個節點除了存儲KEY，還需要存儲指針。是以每個節點儲存的KEY的數量為pagesize/(keysize+pointsize)（如果是B-TREE索引結構，則是pagesize/(keysize+datasize+pointsize)）。

假設平均指針大小是4個位元組，那麼索引樹的每個節點可以存儲16k/((8+4)*8)≈171。那麼：一個擁有3000w資料，且主鍵是BIGINT類型的表的主鍵索引樹的高度就是(log2^25)/log171 ≈ 25/7.4 ≈ 3.38。

假設平均指針大小是8個位元組，那麼索引樹的每個節點可以存儲16k/((8+8)*8)≈128。那麼：一個擁有3000w資料，且主鍵是BIGINT類型的表的主鍵索引樹的高度就是(log2^25)/log128 ≈ 25/7 ≈ 3.57

由上面的計算可知：一個千萬量級，且存儲引擎是MyISAM或者InnoDB的表，其索引樹的高度在3~5之間。

參專文章