当前位置: 代码迷 >> 综合 >> Linear hashing 线性哈希表
  详细解决方案

Linear hashing 线性哈希表

热度:56   发布时间:2023-10-22 00:00:32.0

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
--------------------- 
作者:tjssehaige 
来源:CSDN 
原文:https://blog.csdn.net/tjssehaige/article/details/8647710 
版权声明:本文为博主原创文章,转载请附上博文链接!

  相关解决方案