dbm之jdbm

 

jdbm的架构比较清晰，分为2层，RecordManager和BTree/HTree。

 

底层的ReocrdManager封装了IO，事务，提供record的put_record，update_record，get_record，remove_record，commit_record，rollback_record等操作。

 

BTree和HTree相当于kv的索引层。提供通过key去定位对应的record的功能。

 

RecordManager也相当于一个kv store，不过它的key固定是一个long值，在put_record是由RecordManager生成。update/get/romve _record都是通过该key去完成。这个key值包含了value在文件中的位置信息，这种处理方

式简化了如何在RecordManager对Record索引的处理。

 

RecordManager大体上的实现也是把file 划分固定大小的page来管理。事务是通过WAL来实现。在这里不对RecordManage的实现进行分析。

 

 

HTree

jdbm提供通过hash的方式索引kv。htree的子结点要么是hashBucket(hb)，要么是hashDirectory(hd).hb是存放element的容器，hd则所存放hb或下一层的hd。hb如果是leaf-node则没有元素数目上限，否则最多存放8个element。hd和hb作为一个record保存在RecordManager里。

 

htree的最大层数是3(从0开始)，共4层。每个节点最多有2^8=256个子节点。初始化时root是一个hd，指向256个hb，当某个hb的element数目达到上限时，用hd代替hb，把hb的element迁移到hd所指向的hb上。

在定位一个key的位置时，先计算32bit的hash value.因为子节点数是256，所以每8bit用于树的一层定位。写进disk时，每个hd或hb都是一个record，hd只包含所引用的hd或hb的record_id,每次更新的代价比较小。但是对于leaf-node的hb，如果element数目过多，那么每次更新的代价非常大，全部重写整个hb(包括里面的所有的element)。

 

 

BTree

BTree通过b+树索引kv。每个节点是BPage，作为1个record保存。当BPage 分裂合并，增删element时重写受影响的Bpage。

 

总结：

提到的3个dbm，w3c-dbm,sdbm,jdbm都是相对简单的实现，对并发的处理也比较简单(不支持并发或全局锁)。bdb,bdb-je,Kyoto Cabinet,Tokyo Cabinet都是更强大的dbm实现。此外：jdbm还有2个分支，jdbm2和jdbm3，提供更强的功能和性能优化。