好贷网好贷款

Linear hashing 线性哈希表

发布时间:2016-12-4 3:50:01 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Linear hashing 线性哈希表",主要涉及到Linear hashing 线性哈希表方面的内容,对于Linear hashing 线性哈希表感兴趣的同学可以参考一下。

Section 1:问题描述 最近在阅读分布式数据库的相关资料, 资料中提到分布式数据库中需要解决大数据如何高效存储的问题。 分布式或并行数据存储数据结构的设计: (1) 需要具有良好的扩展性(scalability),能够支持大规模数据存储 (2) 不允许在不同数据节点上产生数据分布不均衡的问题,即避免产生“hotspot nodes”. (3) 在存储数据增加或者缩减的情况下能够动态的存储分配空间 在这样的条件下,线性哈希表(basedon linear hashing)是一个很好的解决方案。   Section 2:线性哈希表概览 (1) 线性哈希表使用的是动态哈希算法 (2) 每一个哈希文件拥有许多容量为b的桶(bucket) (3) 使用一系列的哈希函数hi(k) (4) 典型的哈希函数为hi(k) = k mod 2i , i=1,2,3,4,…. (5) 当数据量(key的数目)增长时,使用hi+1替换hi使得旧桶分裂产生新桶 (6) 当数据量增长时,使得某个桶中包含的数据量大于b,则触发旧桶分裂。假设旧桶中的数据是均匀分布的,那么将会有b/2的数据转移到新桶 (7)当数据量减少时,不同的桶之间的数据会合并   Section3:线性哈希的数学原理[1] 假定key=5,9,13,那么key%4=1 现在我们对8求余,5%8=5,9%8=1,13%8=5 不难发现, (任意key)%n=M (任意key)%2n=M 或 (任意key)%2n=M +n   Section4: 线性哈希的实例[2] 参数说明:b-桶的容量,i-当前桶的等级(Level of buckets),p-指向待分裂的桶的指针(蓝色箭头所指)。通常情况下,i的取值为所有桶中拥有最低哈希函数标号的桶所对应的桶号。如桶0、桶1、桶2分别对应的哈希函数标号为h2、h1和h2,则i=1;p则指向最左边的拥有最低哈希函数标号的桶,沿用之前的例子那么p将指向桶1。   Fig 1. 桶0溢出 Fig 2. 分裂点p指向桶0 Fig 3. 修改哈希函数,桶0分裂,依据哈希函数h1将桶0的部分数据移至桶1,无溢出桶,分裂点p重定向指向桶0,修改i值为1(下一次分裂将启用哈希函数h2) Fig 4. 新数据依据哈希函数h1加入桶0和桶1,桶1溢出 Fig 5. 桶0分裂,依据哈希函数h2将桶0的部分数据移至桶2,桶1溢出分裂点p指向桶1 Fig 6. 新数据仍然依据哈希函数h1加入桶1 Fig 7. 桶1分裂,依据哈希函数h2将桶1的部分数据移至桶3,分裂点p指向桶1 Fig 8.无溢出桶,分裂点p重定向指向桶0,修改i值为2(下一次分裂将启用哈希函数h3)   Section 5: Key值的读取 采用hi对key进行运算(注意i的值), 如果计算出的桶号小于或等于当前分裂点,表示桶已经分裂,接下来将采用hi+1进行哈希运算,算出key对应的真正的桶号,从而从该桶中取出对应于key的value; 如果计算出的桶号大于分裂点,则表示该桶没有分裂,直接从该桶中取出对应于key的value。   引用: [1] http://blog.csdn.net/jackydai987/article/details/6673063 [2] http://www.it.uu.se/research/group/udbl/kurser/DBII_VT13/indexes.pdf

上一篇:JS对象之Table表格对象
下一篇:Android比较日期

相关文章

相关评论