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
版权声明：本文为博主原创文章，转载请附上博文链接！