爪哇教室＞ BTree_qing (王建興)    BTree一直是我心中的惡夢，依稀還記得我大二上的時候，修了一門叫「 檔案結構」的課，依稀有教到這個東西。這門課最後以9分收場，不僅造 成了終生的遺憾，也讓我自此對資料庫相關的課程，望之卻步，差點成為 我軟體技術上的罩門，一直等到在獨孤木先生英明偉大的領導下，才漸漸 明白和關聯式資料庫有關的一些東西，也終於會寫一點點粗淺的SQL。    很多時候，命運會為你和你不愛的東西搭起一座橋（請參考「我的野蠻女 友」）。在前些日子，我就剛好遇到一個需要BTree才能解的問題。事情 是這樣子的：我需要一種資料結構，要能夠很快的判斷出來某個key值是 否已經存在，當某key值已經存在的時候，要能夠快速的找到這個key值 所對應的value。當然，我會需要把某個key:value的對應塞到這個資料 結構中，也會需要把某個key值和它所對應的value一起從這個資料結構 中移除。    沒有什麼意外的話，我會利用Java的java.util.HashMap來達到這個目的。 當資料都只需要在記憶體中處理的話，當然滿理想的。可偏偏資料量極大 ，而且即使程式終止後都必須保留住其內容－也就是persistent的意思。 這下就有點頭疼了，做HashMap的object serialization可不理想呢。這 時9分，即使是9分都可以派上用場，腦中靠著這9分硬是把BTree給召喚 了出來。嗯，我可能需要的是BTree。    因為只有9分的實力，所以還是來看看BTree抽象的外觀、把它當黑盒子看 就好了。BTree支援搜尋（serach）、建立（create）、插入（insert）、 刪除（delete）等operation。從名字上看，可以很容易明白它和 red-black tree、AVL tree一樣都是balanced tree。也就是說，它們會 盡可能的保持樹狀結構本身的高度（height）平衡，使得高度始終能和樹 中節點個數保持對數的關係，也就是log(n)的意思。高度平衡可以得到什 麼好處？當高度不會因為樹本身的節點成長而成長的太快時，意謂著即使 資料量成長到很大，我們在這種資料結構中操作資料，其時間複雜度都不 會太高。    但是，我們要的不只是一種平衡的樹，因為我們需要把資料儲存在具永續 性的儲存媒體上，也就是檔案，所以需要的是一種可以有效在磁碟上處理 的檔案結構，起碼要能夠以主記憶體RAM為主，以磁碟為輔。而BTree正是 一種基於此種目的而被發展出來的資料結構，它可以將部份或全部的資料 維護於磁碟中，並且最小化讀取磁碟的數目－因為讀取磁碟的代價實在太 昂貴了。    憑著9分的實力，從古老沉睡中的記憶喚配了BTree。接下來，我的問題就 是找到一個版權合理，而且符合我需求：Java、open source的實作品了。 這時候腦中浮起另一個印象，有一個P2P的open source計畫－JXTA，它內 部用來索引其文件的機制xindice，似乎就有一個BTree的實作品。經過一 陣翻箱倒櫃，證實我的記憶沒錯，而且看起來xindice和JXTA其他部份的相 依性還很低，可以很容易將它取出，而不必使用到JXTA的其他部份。如果 有興趣的話，可以接下去看看我是怎麼做的。    首先，下載JXTA的source code，找到net.jxta.impl.xindice下所有的東 西，包括core與util兩個sub-package，把它們拿出來獨立編譯，就可以得 到它的xindice的部份。很神奇，完全沒有和任何JXTA其他的程式相依， 所以我相信這也是從其他地方抄來的。    這樣其實就會動了。我們可以看一下下面的範例程式：    import net.jxta.impl.xindice.core.data.Key; import net.jxta.impl.xindice.core.data.Value; import net.jxta.impl.xindice.core.data.Record; import net.jxta.impl.xindice.core.filer.BTreeFiler;    public class BTreeExample { public static void main(String[] args)  { try { BTreeFiler mapping = new BTreeFiler(); boolean sync = true; mapping.setSync(sync); mapping.setLocation(".", "mapping"); if (!mapping.open()) { mapping.create(); mapping.open(); } System.out.println(System.currentTimeMillis()); for(int i=0;i<100;i ) { char ch = (char) ('A' (i&)); String key = "" ch i; Key dbKey = new Key(key); String value = Integer.toString(i); Value recordValue = new Value(value.getBytes()); mapping.writeRecord(dbKey, recordValue); } System.out.println(System.currentTimeMillis()); Key dbKey = new Key("X23"); Record record = mapping.readRecord(dbKey); Value v = record.getValue(); byte b[] = v.getData(); System.out.println(new String(b)); System.out.println(System.currentTimeMillis()); // mapping.close(); } catch(Exception e) { e.printStackTrace(); } } } 整個BTree的檔案，需要利用BTreeFiler這個物件來建立，當你呼叫其 setLocaiton()方法時，即在指定其檔案儲存的路徑以及檔案名稱。在這 個例子中，指定儲存在目前的工作目錄（.），主檔名為mapping，副檔 案則會由xindice指定為.tbl。要使用BTree檔，得先開啟 （BTreeFiler.open()），倘若檔案不存在時，得加以建立 （BTreeFiler.create()）。若想將一筆資料塞到BTree檔案中時，可以 使用BTreeFiler. writeRecord()方法。但在呼叫之前，得先建立Key與 Value的物件，藉以表示想要塞到BTree之資料的key及value值。Xindice 的value值，可以是byte陣列，所以你可以儲存任何可以轉換成byte陣列 的資料，例如String可以直接呼叫getBytes()取得，而其他的物件也可 以利用object serialization取得。接著，如果想要對BTree進行搜尋， 只要呼叫BTreeFiler. readRecord()方法，只需以Key的object來指定其 key值即可。當若在BTree中尋得資料，便會回傳型別為Value的物件，反 之則回傳null。Value物件中儲存的，即是BTree中符合你所指定key值之 資料的值本身。相關的API細節，可以查看JXTA的javadoc文件，在此不 再贅述。 我有在範例程式中加上了timestamp，大概估量了一下時間，搜尋的速度 極快。 雖然沒有花力氣找其他的實作品，也許網路上還有更好的實作品，不過 目前的這個xindice已經挺夠用的。像我這樣的懶人是不會精益求精的。 像本文所提到的問題，如果用RDBMS解，當然可以，但是太heavy了，有 牛刀之嫌，對某些需要身子瘦一點的用戶端應用程式來說，用RDBMS是不 太適用的。 這件事情另外給我們一個教訓就是，即使是9分都有9分的價值，有上課 就有保祐，雖然總共只上了幾堂課。最後還告訴我們一件事情， open source的計畫中有時藏著珍寶，沒事晃晃都會有收獲。 (全文完)