PostgreSQL源代码剖析: 动态性Hash
摘要： PostgreSQL源代码剖析: 动态性Hash|频道：Debian|点一下： 次1. 为何必须动态性hash平时的hash，大多数是下边那样一副脸孔:图1 一个静态数据hash构造这类Hash维护保养着一些桶，便是图上左侧...
1. 为何必须动态性hash
平时的hash，大多数是下边那样一副脸孔:
图1 一个静态数据hash构造
这类Hash维护保养着一些桶，便是图上左侧的一部分，每个桶上装着hash值同样的数据信息。
这种具备同样hash值的数据信息产生一个链表。这类hash的一个最关键缺陷便是桶的数量是一定的，不容易拓展，伴随着插进数据信息增加，搜索高效率会大幅度降低。
动态性hash便是用于处理这一难题的,postgresql完成的动态性hash确保添充因素不超出一个预订值的状况下动态性地提高hash表的容积。同时每一次扩充所做的修改并不大，室内空间运用率也较为地高。
2. 动态性hash的构造
Postgresql与动态性hash有关的编码遍布在dynahash.c和hashfn.c这2个文档当中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 是 = (hctl- 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; }
