1. 寫在前面
說起B(yǎng)+樹，大家應(yīng)該都很熟悉。B+樹是一種平衡的多路搜索樹，廣泛在操作系統(tǒng)和數(shù)據(jù)庫系統(tǒng)用作索引。相比于內(nèi)存的存取速度，磁盤I/O存取的開銷要高上幾個數(shù)量級。而將B+樹用作索引時，它可以在查找過程有效地減少磁盤I/O操作次數(shù)。
一般涉及B+Tree的書籍和文章都會提到它廣泛用作外存的索引中，但是并沒有詳細(xì)講解怎么實現(xiàn)。本文打算獨辟蹊徑，基于以前實現(xiàn)過的一個程序，介紹怎么實現(xiàn)一個簡單可用的磁盤B+樹。
本文對B+樹的基礎(chǔ)知識就不再贅言。磁盤中的B+樹以文件的形式將整體都存放磁盤當(dāng)中，使用時只在內(nèi)存中緩存部份結(jié)構(gòu)。在本文中，數(shù)據(jù)塊和結(jié)點這兩個詞語都代表了B+樹的一個結(jié)點。
當(dāng)然本文作者水平有限，如有錯誤，還請大家給予指出。
2. 簡單實現(xiàn)
將B+樹存放于磁盤之中，第一步先定自義文件的格式，以便于讀回的時候可以正確解析文件的數(shù)據(jù)。
2.1 B+樹文件的格式
B+樹的結(jié)點在內(nèi)存中使用指針進(jìn)行結(jié)點之間的串聯(lián)，指針值是結(jié)點的第一個字節(jié)的虛擬內(nèi)存地址。而對應(yīng)的在磁盤中可以用所在的數(shù)據(jù)塊的第一個字節(jié)相對文件頭部的偏移量來標(biāo)識。
