Rumah > pangkalan data > tutorial mysql > PostgreSQL源码分析: 动态Hash

PostgreSQL源码分析: 动态Hash

WBOY
Lepaskan: 2016-06-07 17:58:48
asal
1452 orang telah melayarinya

1. 为什么需要动态hash 平常的hash,大多是下面这样一副面孔: 图1 一个静态hash结构 这种Hash维护着一些桶,就是图上左边的部分,每一个桶中装着hash值相同的数据。 这些具有相同hash值的数据形成一个链表。这种hash的一个最主要缺点就是桶的数目是一定的,不

1. 为什么需要动态hash

平常的hash,大多是下面这样一副面孔:



图1         一个静态hash结构

这种Hash维护着一些桶,就是图上左边的部分,每一个桶中装着hash值相同的数据。

这些具有相同hash值的数据形成一个链表。这种hash的一个最主要缺点就是桶的数目是一定的,不易扩展,随着插入数据增多,查找效率会急剧下降。

动态hash就是用来解决这个问题的,postgresql实现的动态hash保证填充因子不超过一个预定值的情况下动态地增长hash表的容量。同时每一次扩容所作的改动不大,空间利用率也比较地高。

2.      动态hash的结构

Postgresql与动态hash相关的代码分布在dynahash.c和hashfn.c这两个文件之中hashfn.c

主要是一些Hash Function,而dynahash.c才是动态hash的主要实现。

与普通hash表相比,动态hash多了一个新的行政单位: 目录。 如下图:



图2   postgresql 动态hash结构

dir是一个大小可变的数组,初始长度可以在创建时指定,以后每一次扩展其长度都会X2。dir中的每一项都指向一个长度固定的Segment, 这些Segment的长度都相同且必须是2的整数次幂,Segment数组中的元素是Bucket(桶) ,每一个桶中存放着一个链表,动态hash将所有具有相同hash值的元素都放在同一个桶中。

现在来看一下pg中 这些基本概念的定义:      

typedef struct HASHELEMENT 

    struct HASHELEMENT *link;   /* link to next entry in same bucket */ 
    uint32      hashvalue;      /* hash function result for this entry */ 
} HASHELEMENT;


/* A hash bucket is a linked list of HASHELEMENTs */ 
typedef HASHELEMENT *HASHBUCKET; 
 
 
/* A hash segment is an array of bucket headers */ 
typedef HASHBUCKET *HASHSEGMENT;
这些定义都可以和上图相对应,不再多说。

3. 给定hash value,如何找到与其对应的Bucket

先看一下实现吧:

/* Convert a hash value to a bucket number */ 
static inline uint32 
calc_bucket(HASHHDR *hctl, uint32 hash_val) 

    uint32      bucket; 
 
    bucket = hash_val & hctl->high_mask; 
    if (bucket > hctl->max_bucket) 
        bucket = bucket & hctl->low_mask; 
 
    return bucket; 

hctl->max_bucket 指的是bucket总数减1,对于图2来说,这个值为15

hctl->low_mask 是max_bucket + 1)的最大的2^K减1, 对于图2来说,这个值是16 - 1 = 15 (0000 1111)

hctl->high_mask 是2^(K + 1)减1, 对于图2来说,这个值是32 - 1 = 31 (0x0001 1111)

这几个变量要注意的是,hctl->max_bucket在hash表创建好以后,会变化,一般情况下每次增加一个,如果hctl->max_bucket变成了2的整数次幂,就需要更新hctl->low_mask和hctl->high_mask。更新代码如下:

/*
* If we crossed a power of 2, readjust masks.
*/ 
if ((uint32) new_bucket > hctl->high_mask) 

    hctl->low_mask = hctl->high_mask; 
    hctl->high_mask = (uint32) new_bucket | hctl->low_mask; 
}  

我们回头继续看那个calc_bucket函数, 因为理解这个函数是理解动态扩展的关键。从上面关于max_bucket,low_mask和high_mask的介绍,可以得出下面的结论:

hctl->high_mask >=  hctl->max_bucket >= hctl->low_mask

反应在它们的二进制表示上,如果hctl->low_mask占m位(2^m - 1),则hctl->high_mask占m + 1位。而hctl->max_bucket是在闭区间[low_mask,high_mask]之间的。所以要取得hash_val的bucket值应优先&上high_mask,如果发现得到的bucket的序号比max_bucket还大,则再&上low_mask。这一步为后面的扩展埋下了伏笔。在扩展的时候,也就是max_bucket增加的时候,可能会造成这种情况,扩展前后同一hash_val通过calc_bucket算出的值不一样。下面在叙述扩展的时候再详细解说其解决办法 。

4.  动态扩展

在弄清楚动态hash的结构以及如何从hash值得到其所在的bucket后,hash表的查找,删除以及通常情况下的插入操作就非常地容易啦。比如删除,就先是调用 cal_bucket找到所在的桶,然后在这个桶中一个个地找,找到具有相同键值的元素,就从桶所对应的链表中删除。 下面来说一下动态扩展的问题,毕竟这才是pg动态hash的核心。

说到动态扩展,就得说扩展时机,什么时候我们的hash表需要增大容量呢? 我们增大容量是为了保证其查找的效率。而hash表的查找效率是与一个叫做填充因子东西有很大关系的。pg的填充因子定义为:

填充因子 = hctl->nentries / (hctl->max_bucket + 1)

从这个公式可以看出填充因子会随着插入元素的增多而增加, 当增大到比hctl->ffactor还要大的时候就需要扩展了,这里的扩展的意思是指hctl->max_bucket要增加1个。其步骤如下:

1) 计算出 max_bucket + 1所在的segment索引值segndx

>

2) 如果segndx没有超出已分配的segment的容量,转入5),否则继续;

3) 检查segndx是否超出了现有的dir大小,如是,将dir的大小扩展为以前的2倍;

4) 给dir[segndx]分配一个新的segment;

>

5) 计算max_bucket + 1在没有扩展前的bucket号old_bucket;

6) max_bucket++后检查max_bucket是否成了2的整数次幂,若是,修改low_mask和high_mask;

7) 计算新的bucket号new_bucket;

>

8) 遍历old_bucket链表,重新计算他们所应该在的bucket,将需要移动的移到到new_bucket中。

这个过程中只有步骤8需要说明一下。为什么只是本次扩展前的old_bucket,而没有检查,前一次,前两次扩展的old_bucket呢?这是由calc_bucket中计算bucket的方法所决定的,其实你想的没有错,是应该去遍历前一次,两次,扩展的那些old_bucket,但是没有必要,即使你这样做了,你也从这些bucket中找不到一个可以入到new_bucket中的元素。我们只需要证明经过一次扩展,留在old_bucket中的元素的hash值对应的bucket从些以后不会再改变就行了。

扩展前后bucket计算路径可以用下面矩阵来表示:

扩展后 &high_mask            扩展后 &low_mask

扩展前  &high_mask                    (1)                                     (2)

扩展前  &low_mask                      (3)                                     (4)

这其中(2)是不可能出现的,因为扩展前的high_mask与扩展后low_mask相等,如果(2)成立就出出现max_bucket > (max_bucket + 1)的矛盾。而对于 情况(1),由于high_mask和max_bucket只会增加,把以bucket号从些不会改变, 而(3)和(4)实际上就是本次扩展需要移动的项。所以已经证明那些留在 old_bucket中的元素不会变。

5.  总结

pg实现的这个动态hash保证填充因子不超过设定值,其检索效率不会因插入元素的增多而降低,同时其扩展的代价也不是十分地大,每次只需要移动一个bucket中的某些项到新的bucket中。
Label berkaitan:
sumber:php.cn
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan