關鍵字與數據的存儲方式
B 樹:非葉子結點和葉子結點都會存儲關鍵字及對應的數據。
B + 樹:非葉子結點僅存儲關鍵字(作為索引),實際數據只保存在葉子結點中。
順序查找的支持情況
B 樹:不支持順序查找,因為結點之間沒有順序鏈接的結構。
B + 樹:支持順序查找,所有葉子結點按關鍵字順序鏈接成一個鏈表。
查詢效率的穩定性
B 樹:查詢效率不穩定,可能在非葉子結點就找到目標數據(查詢深度不確定)。
B + 樹:查詢效率穩定,無論查找哪個數據,都必須遍歷到葉子結點(查詢深度固定)。
空間利用率
B 樹:空間利用率較低,因為非葉子結點同時存儲關鍵字和數據,單結點能容納的關鍵字數量較少。
B + 樹:空間利用率較高,非葉子結點僅存關鍵字,單結點可存儲更多關鍵字,樹的高度更低。
範圍查詢的效率
B 樹:範圍查詢效率低,需要多次回溯父結點來遍歷符合條件的結點。
B + 樹:範圍查詢效率高,只需找到範圍的起始葉子結點,再沿葉子結點的鏈表依次遍歷即可