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。
分享到:
相关推荐
dBm-Vpp-Vrms-Watts Conversion
电磁兼容(EMC)小小家dBm - dBW - W 和 dBuV - dBV - V换算计算器电磁兼容(EMC)小小家dBm - dBW - W 和 dBuV - dBV - V换算计算器
dBm - volts - watts conversion
dbm 电压 功率 对应表格,速查手册,方便射频、硬件、通信工程师查阅。 dbm 电压 功率 对应表格,速查手册,方便射频、硬件、通信工程师查阅。
32dBm=30dBm+3dBm+3dBm+3dBm+3dBm-10dBm =1W×2×2×2×2×0.1 =1.6W 计算技巧: + 1dBm和+2dBm的计算技巧 +1dBm=+10dBm-3dBm-3dBm-3dBm =X×10×1/2×1/2×1/2 =X×1.25 例3:51dBm=30dBm+...
通过查表,迅速得出dBm-volts-watts的换算关系。免去复杂的计算。
The clusters of Eu^(3+) ion in Eu(DBM)3Phen-doped polymethyl methacrylate (PMMA) have been studied by three means. The relative fluorescence intensity ratio of the 5D0 -> 7F2 to 5D0 -> 7F1 ...
dbm和mw对应表-可快速得到相互转换的值
dBm与幅度与有效值 等之间的换算表格,可以快速查询相关数值对应的的不同单位的数值大小。
ClickHouse可视化工具DBM(Mac版)
资源来自pypi官网。 资源全名:dbm-agent-0.10.0.tar.gz
dBm到Vpp的测量单位关系换算表。 方便查找对照,可以作为工具使用。
目录数据库代理dbm是一个软件套件,包含dbm-center和dbm-agent两大组成部分;其中dbm-center可以看成一个web站点,DBA通过它可以查看监视,布局,部署各种MySQL环境。dbm-agent是dbm-center的助手,负责环境的部署,...
扩展温度范围: -40 °C ~ +85 °C 模块尺寸: 29.0 mm × 32.0 mm × 2.4 mm 重量: TBD LCC 封装 供电电压: 3.4~4.5 V,典型值 3.8 V 带宽: 1.4/3/5/10/15/20MHz 3GPP TS 27.007, 27.005 定义的命令,以及移远 ...
SAP DBM (Dealer Business Management)汽车行业解决方案概览。
dbm和vpp换算表dBm-Vpp Conversion
对于无线工程师来说更常用分贝dBm这个单位,dBm单位表示相对于1毫瓦的分贝数,dBm和W之间的关系是:dBm=10*lg(mW)1w的功率,换算成dBm就是10×lg1000=30dBm。2w是33dBm,4W是36dBm……大家发现了吗?瓦数增加一倍,...
ClickHouse可视化工具DBM(Windows版)