前幾天我寫了點 btree 的東西(/2891595/1261783)，今天繼續這個思路，繼續寫 b+tree。

而且 b+tree 才是我的目的，更加深入理解檔案和資料庫索引的基本原理。

在之前，我一直只把 b+tree 當成是 btree 的一種變形，或者說是在某種情況下的一種最佳化，另外一些情況可能還是 btree 好些。但是做完之後才發現，b+tree 在各種情況都可以完全取代 btree，並能夠讓索引效能得到比 btree 更好的最佳化。因為 b+tree 設計的核心要點，是為了彌補 btree 最大的缺陷。

btree 最大的缺陷是什麼?

首先,我們知道對於 btree 和 b+tree 這種多路搜尋樹來說，一個很重要的特點就是樹的度數非常大。因為只有這樣才能夠降低樹的深度，減少磁碟讀取的次數。而樹的度數越大，葉子節點在樹中的比例就越大。假設度數為 1000，那麼葉子節點比他上一層內部節點的數量至少要多 1000 倍，在上一層就更加可以忽略不計了。可以說樹種 99.9% 的節點都是葉子節點。 但是對於 btree 來說，所有節點都是一樣的結構，都含有一定數量的資料和指向節點的指標。這兩項資料佔據 btree 節點的幾乎全部的空間。一個節點內的資料的數量比硬碟指標的數量少一，可以說和指標的數量幾乎相等。對於 python 這種動態型別語言感覺不出來，但是對於 C 這種固定型別語言來說，即使這個 children list 陣列為空，這個陣列的空間也都是預留出去的。導致的結果就是佔絕大多數的葉子節點的 children list 指標陣列所佔的磁碟空間完全浪費。

Loading...

未載入完，嘗試【重新整理網頁】or【關閉小說模式】or【關閉廣告遮蔽】。

使用【Firefox瀏覽器】or【Chrome谷歌瀏覽器】開啟並收藏！

移動流量偶爾打不開，可以切換電信、聯通網路。

收藏網址：www.peakbooks.cc

(＞人＜；)