DRH(Deep-Re-Hash)深度哈希分区算法简介

DRH(Deep-Re-Hash)深度哈希分区算法是一种针对哈希表在海量数据及磁盘存储下的一种改进算法,它的时间复杂度介于常数O(1)和对数O(log n)之间(即:O(1) <= T(n) <= O(log n) ),提供了极高的数据检索、插入、修改、删除效率。

DRH的特点

1、不存在哈希表的哈希碰撞攻击问题;

2、更适合海量非关系型数据的磁盘化存储及操作;

3、采用了哈希表深度分区,并保证每一次分区时的数据散列;

4、不存在B+树的Merge和Split自平衡过程,使数据的插入、修改和删除更加高效;

5、与B+树类似,适当提高阶数,降低深度可以极大地降低复杂度,提升操作效率;

DRH的缺点

1、由于索引节点的存在,会额外占用部分空间资源;

2、支持对底层数据进行随机遍历,但是不支持范围遍历;

DRH与哈希表的比较

1、DRH以哈希表作为索引的底层数据结构;

2、DRH可以无限递增节点,新节点对原有分区数据进行重新散列,因此不存在哈希碰撞攻击问题;

3、相比较于单一的哈希表结构,DRH提供了分区化的数据管理方式,支持更大的数据存储和操作,更适合数据磁盘化存储;

例如:针对10亿条数据,如果都存放在一张哈希表中,很明显会极大占用内存;如果都存放在磁盘上,反复大容量数据读写使得IO性能也会很弱。DRH将数据划分为若干分区,按需将对应分区的小块内容载入内存进行计算,占用内存低,操作效率高。

DRH与B+树的比较

1、DRH和B+树有很多相似的地方,不过DRH对底层数据的遍历是随机的,并不支持范围遍历,但是DRH在Key-Value数据库中性能却相当优异;

2、在每个节点中,DRH增加了一层索引哈希表,每条数据包含一条固定长度的索引值,存放在索引哈希表中,可以按照O(1)的时间复杂度进行分区检索;

3、在索引哈希表中的分区中,仍然采用数组形式存放,不过存放的是固定长度索引值,按照二分查找进行数组检索,不过由于DRH的索引值是定长的,因此二分检索能够按照二进制进行检索(与数据结构无关),而不是基于数据结构的检索。在B+树中,每个节点的数组元素项存放的是特定的数据结构,当存放的数据结构存在变长的情况时(例如Key-Value数据库中的键名数据),这些数据被从磁盘中读取到内存后,会有一个数据结构的解析过程,而DRH没有,因此在对磁盘化的变长数据进行操作时,DRH的检索效率会更高。如果数据结构是定长的,那么两者的检索效率理论相等。

4、由于DRH底层数据结构是哈希表,并且数据存放是散列的,因此DRH不需要B+树那样的Merge和Split自平衡过程,这使得DRH对数据的插入、修改、删除操作更加高效;

5、DRH的深度分区计算是在单节点内循环进行,不需要进行向上递归处理,不影响其他节点;

DRH的定义

1、DRH的节点由索引哈希表构成,表被划分为若干分区,每一个分区存放固定长度的检索数组,支持二分检索,检索数组中的每一个元素项均指向叶子节点数组中的一个数据项;

2、设定分区基数为n分区阶数m分区增量为i,那么根节点有且仅有n个分区,每个分区的检索数组最多只能存放m条索引项,每个非根节点的分区数为 n+i,其中根节点的 i=0,除根节点外,所有节点的分区数(即n+i)必须为奇数;

3、当数据插入后,节点中分区p的索引数组长度达到m时,需要对p进行深度分区,深度分区算法如下:

1)、新增一个节点q,q的分区增量k为p的分区增量+1,即 k=i+1;

2)、保证q的分区数 n+k 为奇数,否则分区增量k继续递增;

3)、对p的检索数组按照q的分区数进行重新分区,将p的索引项散列到q的分区中(分区散列采用取模实现);

4)、如果重新散列后,q中存在任一分区的索引数组长度>=m,重复步骤2)、3)继续递增q的分区增量k,直到q中所有分区的索引数组长度<m;

5)、将p标记为已分区,并保存指向到新节点q的地址指针,当下一次检索到p时,便能直接跳转到q中进行检索;

DRH的示例

我们来举一个简单的示例说明DRH的分区过程。

1、我们写入几个Key-Value数据,键名分别为2,3,1,4,0,5,键值与键名相同,设定表的哈希函数生成的哈希值与键名相同,并且设定分区基数为2,分区阶数为2,那么连续写入这几条数据后,数据库结构是这样的:

图1:写入数据2,3,1,4,0,5

可以看到对于根节点的分区中数据长度达到2的时候会对该分区进行重新的深度分区,并且分区后的新节点分区数必须为奇数,这里计算出新节点的分区增量为1,那么分区数即为3,并将数据进行重新的散列计算。

深度分区完成后,根节点中对应的分区分别指向对应的新节点,当检索请求进入的时候会首先进入根节点进行检索,匹配到对应的分区后,会根据分区中对应的节点位置进一步进行检索,直到检索到对应的数据节点。

 

2、接着继续写入一条数据为6,这个时候数据库的结构如下:

图2:继续写入数据6

可以看到HashTable1的part0分区达到了阶数上限,因此再一次进行了重新的深度分区,计算出新节点的分区增量为2,分区数为5。

这里可以看得出来,如果分区阶数和分区基数设定得太小,很容易就会加深整个数据库的深度,搜索的时候就会多一层检索。因此,适当的提高阶数,降低深度可以极大地降低复杂度,提升检索效率,例如:一个分区基数为10000,阶数为10000的数据库,单节点理论支持的数据量达到1亿(10000×10000)。

 

 

 

 

 

 

 

 

 

 

 

Leave a Reply

Your email address will not be published.