dbm之sdbm
sdbm是 http://amisha.pragmaticdata.com/~schadow/dbm-java/ 上一个dbm的实现。sdbm主要由dir和page组成。它和w3c-dbm(见dbm之w3c-dbm)有所不同，w3c-dbm由dir和block组成。w3c-dbm的element保存时是区分索引和kv_content的，并且kv_content 可以跨block w3c-dbm_block的，所以对kv的大小没限制。sdbm_page有点像hashmap的bucket，处理hash冲突时采用拉链法。因为sdbm_page是定长的，并且kv不能跨page，所以对于kv的大小限制受page大小影响。另一个区别是两者对dir的组织也不一样。w3c-dbm对dir的处理更像普通的hashmap，bucket数组，满时double dir。sdbm把dir作为一棵binary tree处理。此外，w3c-dbm使用一个文件来保存dir和kv的信息，sdbm则使用两个文件，一个保存dir信息，dir_file，另一个保存page，page_file。sdbm之page：
page_file被划分一个个page，对应project的class Page。Page 有3个属性：1.pag:bytes array;2.pageSize:size of pag;3.bno:page num，唯一，通过bno可以确定对应的page在page_file的偏移量。off(page)=page.bno*PAGE_SIZE。Page 还支持put_kv,get_kv,reove_kv 和 split_page等操作。
page在page_file的格式：
* +--------------------------------+
* ino | n | keyoff | datoff | keyoff |
* +------------+--------+--------+
* | datoff | - - - ----> |
* +--------+----------------------+
* | F R E E A R E A |
* +--------------+----------------+
* | <---- - - - | data |
* +--------+-----+----+----------+
* | key | data | key |
* +--------+----------+-----------+
在page头的page_n(n)，keyoff，datoff都是占2byes的short value。尾部的key，data则是kv的content。z中间则是可用空间。当插入一个新kv时，根据图示的两个箭头方向收缩可用空间。
页:
[1]