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

DRH(Deep-Re-Hash)深度哈希分区算法是一种针对哈希表在海量数据及磁盘存储下的一种改进算法,它的查询时间复杂度介于常数O(1)和对数O(d*log (n-1))之间(即:O(1) <= T(n) <= O(d*log(n-1)) ,其中n为阶数,d为深度),提供了极高的数据检索、插入、修改、删除效率。DRH算法的Go语言实现代码:https://gitee.com/johng/drh-go

DRH的特点

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

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

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

4、不存在B树的Merge和Split回溯自平衡过程,使数据的插入、修改和删除更加高效(DRH的散列计算在同一分区内,不需要回溯处理,IO操作次数低效率高);

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

DRH的缺点

1、由于索引节点的存在(哈希表),会额外占用空间资源;

2、支持对底层数据进行随机遍历,但是不支持范围遍历(当然可以对DRH进行类似B+树那样改进 - DRH+,将数据层做成链表或者跳表以满足范围遍历需求);

DRH与哈希表的比较

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

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

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

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

DRH与B树的比较

1、DRH和B树有很多相似的地方,都适用于外部存储;

2、DRH对底层数据的遍历是随机的,并不支持范围遍历,但是DRH在Key-Value数据库中性能却相当优异;

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

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

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

5、DRH的深度分区计算是在单节点内循环进行,不需要进行向上回溯处理,不影响其他节点(因此写入/删除效率会更高);

DRH的定义

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

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

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

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

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

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

4)、将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,分区数为4。

这里可以看得出来,如果分区阶数和分区基数设定得太小,很容易就会加深整个数据库的深度,搜索的时候就会多一层检索。因此,适当的提高阶数(并不是越多越好,因为二分检索效率相比较于哈希表检索要低),降低深度可以极大地降低复杂度,提升检索效率,例如:一个分区基数为10000,阶数为10000的数据库,理想情况下单节点理论支持的最大数据量达到1亿(10000x10000)。

 

 

 

 

 

 

 

 

 

 

 

One Reply to “DRH(Deep-Re-Hash)深度哈希分区算法简介”

Leave a Reply

Your email address will not be published.