dbm之w3c-dbm

 

dbm是key-value store较常见的一种存储实现。http://en.wikipedia.org/wiki/Dbm dbm的各个实现。

 

http://aurora.regenstrief.org/~schadow/dbm-java/上有3个纯java的dbm实现。其中一个是W3C's 

Jigsaw项目中抽离出来，后面出现的w3c-dbm都是指该项目。w3c-dbm实现比较简单，不支持事务。也不保证数据的完整和可靠。

 

w3c-dbm是一个hash表。先说几个概念：

1.block：w3c-dbm 把磁盘划分一系列block进行管理。block的大小在初始化时确定，并写入文件头保存，不能更改。

 

2.dir（目录），每个dir指向一个bucket。bucket是一个元素列表。可能有多个dir指向同一个bucket.dir_size,dir的数目，dir_bits,dir_size = 2^dir_bits。

 

3.bucket_ele,bucket保存的元素，里面有5个属性：hashval，key的hash值；keystart，key开始的4个字节，用于在bucket里快速判断该key是否要查找的key；keysize；datasize；fileptr：bucket_ele里不直接包含key和value，fileptr是文件的偏移量，指向真正的key和value的位置。每个bucket的bucket_ele必须保存在同一个block里，所以bucket_ele数目上限由block大小决定。在block中处理hash冲突时采用开发地址法。

 

4.bucket_bits,记录bucket的分裂次数，初始化为0，分裂后的bucket在分裂前的值加1.

bucket_bits==dir_bits，dir不够用，需要double dir数目。

 

5.hash_value,key的hash值，32bit，其中只用上31bit，最高bit为0.在定位key时，先计算key的hash_value,右移31-dir_bits位，得到的值就是hash_value的高dir_bits+1 bit，其中最高bit是0.dir_size有dir_bits位，用该值做dir的下标来定位dir。

 

下面描述一下w3c-dbm如何管理hash表，重点是bucket分裂和dir double。

1.初始化时，dir_size为n，n=2^dir_bits,n个dir指向同一个bucket。所有的元素实际上都是在同一

bucket里。该bucket的bucket_bits=0.当bucket满时，分裂成2个，[0,n/2)的dir指向分裂后的bucket0，[n/2,n)的dir指向分裂后的bucket1。原先的bucket_ele重新分配一次，在dir的入口不变，但是dir指向的bucket变了。引入一个dir_area的概念，一个dir_area里的dir指向相同的bucket，分裂时变成2个，每个的范围只有之前的一半。一个理想状态的饱满的dir是每个dir_area范围只有1，均指向不同的bucket。

 

2.bucket分裂后bucket_bits 加1.例如dir_size=4的dir，dir_bits=2,第一次分裂成dir_area0:[0.2),dir_area1:[2,4).dir_area0再分裂dir_area0_0:[0,1),dir_area0_1:[1,2).这时的dir_area0_0和dir_area0_1指向的bucket_bits为2，等于dir_bits，表明不能再进行分裂了。如果需要再分裂这两个area，必须要增加dir的数量。

 

3.增加dir数量很简单，直接double，伪代码

new_dir[] = new dir[dir_size*2];

for(int i=0;i<dir_len;i++){

new_dir[i] = dir[i];

new_dir[i+1] = dir[i];

}

dir = new_dir;

dir_bits+=1;

 

double之后，原来的映射仍然生效。

double前old_bucket_idx = dir_bits bit.double后，new_bucket_idx = old_bucket_idx*2+(0/1), dir_bits+1 bit.

 

 

其他一些细节比较简单：

1，对于block里的空闲空间管理。

2，在bucket里元素的插入不是直接放在列表的头或尾，会有一个二次映射。删除时也会对bucket的bucket_ele做整理。这些都是内存操作，不涉及到io。