B+樹在B樹的基礎上的一中優(yōu)化,InnoDB和MylSAM存儲引擎都是用B+樹實現索引結構
B樹的索引和關鍵字key-data存儲在磁盤里面,然后被磁盤IO操作讀入內存,如果這個data很大的話,每次加到內存中的key就會減少, 這會使得B數的高度增加,這樣還是會增加磁盤IO查詢
為了解決這個問題, B+樹將所有數據記錄節(jié)點按照鍵值的大小順序存放在同一層葉子節(jié)點上, 而非葉子節(jié)點只存儲key值信息,這樣可以大大增加每個節(jié)點存儲的key值的數量,降低B+樹的高度
非葉子節(jié)點只存鍵值信息,所有葉子節(jié)點之間都有一個鏈指針,數據記錄都存在葉子節(jié)點上如圖:
image
InnoDB存儲引擎最小的存儲單元是(頁), 每一頁的大小是16k(即16384個字節(jié)),每一行數據大概就是1k左右,那么一頁就可以存16條數據
那么在InnoDb中2層的高度的B+樹能存多少條數據,我們來分析一下:
在InnoDB中每個指針為6個字節(jié),一個鍵值4-8個字節(jié)(如:Id為主鍵 -> bigInt類型是8字節(jié))那么加起來就是14個字節(jié), 那么一頁就能存16384 / 14 =1170個指針, 所以2層的B+樹能存1170*16=18720條數據
在InnoDB在B+樹高度一般為3層所以1170 * 1170 * 16= 21902400 條數據,能存千萬級別的數據
