B+樹在B樹的基礎(chǔ)上的一中優(yōu)化,InnoDB和MylSAM存儲(chǔ)引擎都是用B+樹實(shí)現(xiàn)索引結(jié)構(gòu)

B樹的索引和關(guān)鍵字key-data存儲(chǔ)在磁盤里面,然后被磁盤IO操作讀入內(nèi)存,如果這個(gè)data很大的話,每次加到內(nèi)存中的key就會(huì)減少, 這會(huì)使得B數(shù)的高度增加,這樣還是會(huì)增加磁盤IO查詢

為了解決這個(gè)問題, B+樹將所有數(shù)據(jù)記錄節(jié)點(diǎn)按照鍵值的大小順序存放在同一層葉子節(jié)點(diǎn)上, 而非葉子節(jié)點(diǎn)只存儲(chǔ)key值信息,這樣可以大大增加每個(gè)節(jié)點(diǎn)存儲(chǔ)的key值的數(shù)量,降低B+樹的高度

非葉子節(jié)點(diǎn)只存鍵值信息,所有葉子節(jié)點(diǎn)之間都有一個(gè)鏈指針,數(shù)據(jù)記錄都存在葉子節(jié)點(diǎn)上如圖:

image

InnoDB存儲(chǔ)引擎最小的存儲(chǔ)單元是(頁(yè)), 每一頁(yè)的大小是16k(即16384個(gè)字節(jié)),每一行數(shù)據(jù)大概就是1k左右,那么一頁(yè)就可以存16條數(shù)據(jù)

那么在InnoDb中2層的高度的B+樹能存多少條數(shù)據(jù),我們來(lái)分析一下:

在InnoDB中每個(gè)指針為6個(gè)字節(jié),一個(gè)鍵值4-8個(gè)字節(jié)(如:Id為主鍵 -> bigInt類型是8字節(jié))那么加起來(lái)就是14個(gè)字節(jié), 那么一頁(yè)就能存16384 / 14 =1170個(gè)指針, 所以2層的B+樹能存1170*16=18720條數(shù)據(jù)

在InnoDB在B+樹高度一般為3層所以1170 * 1170 * 16= 21902400 條數(shù)據(jù),能存千萬(wàn)級(jí)別的數(shù)據(jù)