前言
本文章主要說明，相比較B樹和平衡二叉樹，B+樹作為數(shù)據(jù)庫的索引的數(shù)據(jù)結(jié)構(gòu)優(yōu)勢在哪
平衡二叉樹的劣勢
數(shù)據(jù)庫作為存儲(chǔ)數(shù)據(jù)的工具，常常會(huì)存儲(chǔ)大量數(shù)據(jù)。而數(shù)據(jù)最終存儲(chǔ)的物理媒介便是磁盤。如果使用平衡二叉樹，那么當(dāng)數(shù)據(jù)量很大時(shí)，樹的深度也會(huì)很深。在磁盤存儲(chǔ)時(shí)，樹的每一個(gè)節(jié)點(diǎn)會(huì)存儲(chǔ)在一個(gè)數(shù)據(jù)塊中，約高的樹，在搜索一個(gè)數(shù)據(jù)時(shí)遍歷的節(jié)點(diǎn)越多，此時(shí)需要進(jìn)行磁盤IO的次數(shù)就越多，那么所耗費(fèi)的時(shí)間就越多。平衡二叉樹作為一種高瘦的數(shù)，在這點(diǎn)上就比不了矮胖的B樹和B+樹
B樹與B+樹的對比
B樹與B+樹最重要的兩點(diǎn)區(qū)別是：
- B+樹只在葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)，在非葉節(jié)點(diǎn)只有關(guān)鍵字
- B+樹所有葉子在同一層，包含了全部關(guān)鍵字信息，葉子節(jié)點(diǎn)按照關(guān)鍵字的大小自小而大順序鏈接
針對上面兩種不同，B+樹便顯示出比B樹更多的優(yōu)勢
因?yàn)闂l件1：
B+樹在搜索數(shù)據(jù)時(shí)，每次都需要搜索到葉子節(jié)點(diǎn)，這保證了B+樹查找時(shí)間的穩(wěn)定性
B+樹在一個(gè)數(shù)據(jù)塊中可以存儲(chǔ)更多的關(guān)鍵字信息
因?yàn)闂l件2：
B+樹更適合范圍查找，只要查找到最小值便可直接在葉子節(jié)點(diǎn)進(jìn)行遍歷獲取
參考文獻(xiàn)
B+樹在磁盤存儲(chǔ)中的應(yīng)用
漫畫算法：什么是 B 樹？
