B+-tree implementation：JDBM

在前篇文章當中，找了一些有關 B⁺-tree 的實作函式庫
其中有一些連結提到 JDBM 這個函式庫，因此就來嘗試看看了。

JDBM 本質上其實並不是實作資料結構的函式庫，而是要做一個 Java 版的資料庫系統
具有 B⁺-tree 只不過是因為他的資料庫系統會用到的關係。
JDBM 目前看起來有分 JDBM 到 JDBM4 總共四個版本，從原始碼的註記來看，JDBM2、JDBM3 似乎換作者了。
而 JDBM [1]、JDBM2 [2] 和 JDBM3 [3] 的差異在哪裡我也不是很確定～
光看專案的描述來說，JDBM2 有做一些效能調校，但調校的部份不知道在哪～
而 JDBM3 看起來好像多了不少 feature，像是它有特別提出它的 serialization 有客製化，可以提昇讀寫的效率

不過從 JDBM 到 JDBM3，整個函式庫的用法都不太一樣就是了。
舉例來說，JDBM 初始化時是用 RecordManager，可以單獨初始化 B⁺-tree
但到了 JDBM3 好像一定要用 DBMaker 去創建資料庫，而且看來沒辦法單獨抽 B⁺-tree 出來
因為 JDBM3 的 B⁺-tree 的 class 並沒有宣告 public...。

另外，JDBM 的 License 是 BSD Licence（參照 JDBM 的 SourceForge 頁面標示）
而 JDBM2 和 JDBM3 則是 Apache 2.0 Licence。

這裡先用 JDBM 來嘗試使用它的 B⁺-tree。
以下的範例程式碼是參考 JDBM 官方的 B⁺-tree 範例 FamousPeople

import java.io.IOException;

import jdbm.RecordManager;
import jdbm.RecordManagerFactory;
import jdbm.btree.BTree;
import jdbm.helper.StringComparator;
import jdbm.helper.Tuple;
import jdbm.helper.TupleBrowser;

public class FamousPeople {
   static String[] people =
        { "Greenspan, Alan",
          "Williams-Byrd, Julie",
          "Picasso, Pablo",
          "Stallman, Richard",
          "Fort, Paul",
          "Søndergaard, Ole",
          "Schwarzenegger, Arnold",
          "Dulkinys, Susanna" };

   static String[] occupations =
        { "Federal Reserve Board Chairman",
          "Engineer",
          "Painter",
          "Programmer",
          "Poet",
          "Typographer",
          "Actor",
          "Designer" };

   static String DATABASE = "people";
   static String BTREE_NAME = "FamousPeople";

　　public static void main(String[] args) {
　　　　RecordManager rm = null;
　　　　BTree tree = null;
　　　　try {
　　　　　　rm = RecordManagerFactory.createRecordManager(DATABASE);
　　　　　　long recordId = rm.getNamedObject(BTREE_NAME);
　　　　　　
　　　　　　if(recordId == 0) {
　　　　　　　　tree = BTree.createInstance( rm, new StringComparator() );
　　　　　　　　rm.setNamedObject( BTREE_NAME, tree.getRecid() );
　　　　　　　　
　　　　　　　　// insert people with their respective occupation
　　　　　　　　System.out.println();
　　　　　　　　for ( int i=0; i<people.length; i++ ) {
　　　　　　　　　　System.out.println( "Insert: " + people[i] );
　　　　　　　　　　tree.insert( people[ i ], occupations[ i ], false );
　　　　　　　　}
　　　　　　　　// make the data persistent in the database
　　　　　　　　rm.commit();
　　　　　　}
　　　　　　else {
　　　　　　　　tree = BTree.load(rm, recordId);
　　　　　　}

　　　　　　System.out.println("getNamedObject: " + recordId);
　　　　　　
　　　　　　// Find a record.
　　　　　　tree = BTree.load(rm, recordId);
　　　　　　Object result = tree.find("Greenspan, Alan");
　　　　　　if(result == null)
　　　　　　　　System.out.println("Not found.");
　　　　　　else {
　　　　　　　　System.out.println(result.toString());
　　　　　　}
　　　　　　
　　　　　　// Traverse all the records.
　　　　　　tree = BTree.load(rm, recordId);
　　　　　　TupleBrowser browser = tree.browse();
　　　　　　Tuple tuple = new Tuple();
　　　　　　System.out.println("Traverse:");
　　　　　　while(browser.getNext(tuple)) {
　　　　　　　　System.out.println(tuple.getKey().toString());
　　　　　　}
　　　　} catch (IOException e) {
　　　　　　e.printStackTrace();
　　　　}
　　}
}

簡要來說，在 38~39 行呼叫 RecordManager.getNamedObject() 函式，會嘗試去尋找指定名稱的 BTree 檔案
（實際上是資料庫檔案，不過因為我只在裡面存 B⁺-tree，所以就直接稱為 BTree 檔案吧）
如果檔案不存在會回傳 0，這時就要重新建立 Btree 檔案（42~43 行）。
而要讀取已經存在的 BTree 檔案時，就呼叫 BTree.load() 函式（55 行）。

取得 BTree 之後，自然就可以用 find()或 browse() 函式去搜尋 B⁺-tree 裡的資料
要插入資料到 B⁺-tree 裡面則是用 insert() 函式。

PS. find() 可參考 60~67 行、browse() 可參考 69~76 行、insert() 可參考 47~52 行

關於檔案儲存的問題，JDBM 函式庫預設是直接將檔案儲存在跟 Java 執行路徑相同的目錄下
如果要改變的話，可以直接在指定檔案名稱時給完整的路徑，或者去修改儲存檔案的原始碼～
修改的位置在 RecordFile.java 檔案中的 98 行：

file = new RandomAccessFile(fileName + extension, "rw");

有關 JDBM 的效率討論，可以看一下 SourceForge 上的討論
例如 [4] 是一個討論有關 JDBM 的 H⁺-tree 有沒有 memory leak 問題的討論。

PS. 使用 JDBM3 取出 B⁺-tree 的方法請參閱下一篇文章「B+-tree implementation：JDBM3」

參考資料：
1、JDBM
2、JDBM2
3、JDBM3
4、JDBM discussion：HTree memory not released