欢迎来到站长教程网!

Debian

当前位置:主页 > 服务器教程 > Debian >

PostgreSQL源码分析: 动态Hash

时间:2020-06-07|栏目:Debian|点击:

1. 为什么需要动态hash

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

PostgreSQL源码分析: 动态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多了一个新的行政单位: 目录。 如下图:

PostgreSQL源码分析: 动态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;   }  

上一篇:MySQL调优三步曲(慢查询、explain profile)

栏    目:Debian

下一篇:没有了

本文标题:PostgreSQL源码分析: 动态Hash

本文地址:http://www.jh-floor.com/fuwuqijiaocheng/Debian/124720.html

您可能感兴趣的文章

广告投放 | 联系我们 | 版权申明

重要申明:本站所有的文章、图片、评论等,均由网友发表或上传并维护或收集自网络,属个人行为,与本站立场无关。

如果侵犯了您的权利,请与我们联系,我们将在24小时内进行处理、任何非本站因素导致的法律后果,本站均不负任何责任。

联系QQ:888888 | 邮箱:888888#qq.com(#换成@)

Copyright © 2002-2017 青云站长教程网 版权所有 琼ICP备xxxxxxxx号