二叉树搜索具有对数时间的表现有个假设:输入数据具有相当的随机性。现在我们看哈希表,这种数据结构,其在插入、删除、查询操作上也具有常数评价时间的表现,而且这种表现以统计为基础,不依赖数据的随机性。
我们先看看pg里的哈希函数,再看pg里动态哈希表“dynmaic hashtable”(我认为用“可扩展哈希表”更能体现“dynmaichashtable”的功能,更贴近中国人用词习惯,以后就用“可扩展哈希表”吧。)结构、哈希表上的操作(增删查改)以及可扩展。
说哈希函数前先澄清一下 碰撞,碰撞根据使用的场合不同有两种情况,一是哈希函数在把普通值打散/计算出哈希值时可能产生的碰撞,这个需要由哈希函数本身解决,王小云教授研究的碰撞就是这个碰撞;另一个是哈希表中根据哈希键值安排哈希键所在位置时的碰撞,解决这种碰撞的方法有一次探测(linear probing)、二次探测(quadratic probing)、开链(separate chainning)等多种解决方法,pg以开链解决这个碰撞问题。
Hash函数:
pg在hash.h中有下列hash函数
extern Datum hashchar(PG_FUNCTION_ARGS);
extern Datum hashint2(PG_FUNCTION_ARGS);
extern Datum hashint4(PG_FUNCTION_ARGS);
extern Datum hashint8(PG_FUNCTION_ARGS);
extern Datum hashoid(PG_FUNCTION_ARGS);
extern Datumhashenum(PG_FUNCTION_ARGS);
extern Datum hashfloat4(PG_FUNCTION_ARGS);
extern Datumhashfloat8(PG_FUNCTION_ARGS);
extern Datumhashoidvector(PG_FUNCTION_ARGS);
extern Datumhashint2vector(PG_FUNCTION_ARGS);
extern Datumhashname(PG_FUNCTION_ARGS);
extern Datumhashtext(PG_FUNCTION_ARGS);
extern Datumhashvarlena(PG_FUNCTION_ARGS);
extern Datumhash_any(register const unsigned char *k, register int keylen);
extern Datumhash_uint32(uint32 k);
下面这些哈希函数做将原值做一些位与或转换后,将结果作为参数调用hash_uint32继续哈希运算
hashchar()、hashint2()、hashint4()、hashint8()、hashoid()、hashenum()
下面这些哈希函数做将原值做一些位与或转换或类型转换后,将结果作为参数调用hash_any继续哈希运算
hashfloat4()、hashfloat8()、hashoidvector()、hashint2vector()、hashname()、hashtext()、hashvarlena()
这么多的哈希函数最终落到了hash_uint32和hash_any这两个哈希函数上,加上两个做散列的宏mix(a,b,c)和final(a,b,c)完成了哈希运算。hash_uint32(uint32 k)像hash_any(&k, sizeof(uint32))一样有着同样的结果,但hash_uint32更快,并且不强制调用者把k存储在内存中。
关于哈希函数研究,可以推荐两个人的书/文章看看,一个是中科院的裴定一教授,可以看他的书和文章。有优于PKI的CPK标识认证专利的南湘浩教授需要哈希函数的时候就是向裴定一教授要的。南湘浩和曲延文教授以及孙玉院士(都是大牛)合作成立了QNS工作室,我第一次路过工作室时,第一反映是这是个皮包公司,因为在租金不菲的中关村软件园里有偌大面积,但又没有几个工作人员,后来登门拜访受教才了解内情。另一个是Bob Jenkins,可以到他的网站 http://burtleburtle.net/bob/hash/index.html看。或者看他们的论文。
可扩展哈希表可以无限增长。可扩展哈希表有一个顶层的“目录”,他的每一个入口指向ssize个哈希桶的段的头部,最大哈希桶数是dsize * ssize,dsize是可以增大的。当然,哈希表里的记录数可以更大,但是我们不想要一个哈希桶里有很多记录或性能降是低。在共享内存中分配的哈希表时,因为他的地址是固定的,“目录”不能增大。目录的大小应该用hash_select_dirsize选择。非共享哈希表的目录初始化大小可以是默认的。
可扩展哈希表和几个数据结构有关,一个是HCTL,这个是创建可扩展哈希表时的信息表,一个是HTAB,这个就是哈希表结构,一个是HASHHDR,这个是哈希表头结构,包含了哈希表的所有可变信息,还有HashSegment、HashBucket、HashElement等结构,一个HashSegment是HashBucket数组的头,一个HashBucket是HashElement链表。结构定义见下面。这些结构和起来组成了可扩展哈希表。根据pg默认参数创建的可扩展哈希表结构图在下面。
typedef struct HASHCTL
{
long num_partitions;/* # partitions (must be power of 2) */
long ssize; /* segmentsize */
long dsize; /* (initial)directory size */
long max_dsize; /* limit todsize if dir size is limited */
long ffactor; /* fill factor*/
Size keysize; /* hash key length in bytes */
Size entrysize; /* total user element size in bytes*/
HashValueFunc hash; /* hashfunction */
HashCompareFuncmatch; /*key comparison function */
HashCopyFunckeycopy; /*key copying function */
HashAllocFunc alloc; /* memoryallocator */
MemoryContext hcxt; /* memorycontext to use for allocations */
HASHHDR *hctl; /* location of header in shared mem */
} HASHCTL;
struct HTAB
{
HASHHDR *hctl; /* => shared control information */
HASHSEGMENT*dir; /*directory of segment starts */
HashValueFunchash; /*hash function */
HashCompareFuncmatch; /*key comparison function */
HashCopyFunckeycopy; /*key copying function */
HashAllocFuncalloc; /*memory allocator */
MemoryContexthcxt; /*memory context if default allocator used */
char *tabname; /* table name (for error messages) */
bool isshared; /* true iftable is in shared memory */
/* We keep local copies of these fixed values to reducecontention */
Size keysize; /* hash key length in bytes */
long ssize; /* segment size ---must be power of 2 */
int sshift; /* segment shift =log2(ssize) */
};
struct HASHHDR
{
/* In a partitioned table, take this lock to touch nentriesor freeList */
slock_t mutex; /* unused if not partitioned table */
/* These fields change during entry addition/deletion */
long nentries; /* number ofentries in hash table */
HASHELEMENT*freeList; /*linked list of free elements */
/* These fields can change, but not in a partitioned table*/
/* Also, dsize can't change in a shared table, even ifunpartitioned */
long dsize; /* directorysize */
long nsegs; /* number ofallocated segments (<= dsize) */
uint32 max_bucket; /* ID of maximum bucket in use */
uint32 high_mask; /* mask to modulo into entire table */
uint32 low_mask; /* mask to modulo into lower half of table */
/* These fields are fixed at hashtable creation */
Size keysize; /* hash keylength in bytes */
Size entrysize; /* total user element size in bytes*/
long num_partitions;/* # partitions (must be power of 2), or 0 */
long ffactor; /* target fillfactor */
long max_dsize; /* 'dsize' limitif directory is fixed size */
long ssize; /* segmentsize --- must be power of 2 */
int sshift; /* segmentshift = log2(ssize) */
int nelem_alloc; /* number ofentries to allocate at once */
#ifdef HASH_STATISTICS
/*
* Count statisticshere. NB: stats code doesn't bother withmutex, so
* counts could becorrupted a bit in a partitioned table.
*/
long accesses;
long collisions;
#endif
};
typedef HASHELEMENT *HASHBUCKET;
typedef HASHBUCKET *HASHSEGMENT;
根据pg默认值创建的可扩展哈希表结构图如下:
哈希表结构图
创建过程涉及函数及功能:
根据info信息和给定名字及HashElement元素个数进行计算创建可扩展哈希表
HTAB * hash_create(const char *tabname, long nelem, HASHCTL*info, int flags)
分配相应数目(dsize)的HashSegment数组
static bool init_htab(HTAB *hashp, long nelem)
计算给定数的以2为底加1取正对数值
Int my_log2(long num)
给哈希表的HashSegment分配相应个数(ssize)的HashBucket
static HASHSEGMENT seg_alloc(HTAB *hashp)
根据entry大小计算要分的HashElement的个数
static int choose_nelem_alloc(Size entrysize)
分配HashElement+Entry并加入到HASHHDR的freelist链表
static bool element_alloc(HTAB *hashp, int nelem)
哈希表的销毁:
主要是调用MemoryContextDelete(hashp->hcxt)(参见《pg内存管理机制三》)销毁哈希表
Void hash_destroy(HTAB*hashp)
创建流程图如下:
创建可扩展哈希表流程图
上图中红色框主要是根据条件设置HTAB结构类型变量的各成员,右边黄色框中主要是计算HashSegment、HashBucket以及HashElement成员的数目并为它们分配内存。
就到这儿吧。
分享到:
相关推荐
赠送jar包:postgresql-42.3.1.jar; 赠送原API文档:postgresql-42.3.1-javadoc.jar; 赠送源代码:postgresql-42.3.1-sources.jar;...人性化翻译,文档中的代码和结构保持不变,注释和说明精准翻译,请放心使用。
《PostgreSQL修炼之道:从小工到专家》的主要内容和特色: 全面且实践性强:本书从SQL基础、安装配置、数据类型、数据库的逻辑结构等基础知识一直讲到PostgreSQL的架构、技术内幕、特色功能、Standby、数据库优化...
PostgreSQL PostgreSQL PostgreSQL学习手册 学习手册 学习手册 (数据表 数据表 ) 4 一、表的定义: 一、表的定义: 一、表的定义: . 4 PostgreSQL PostgreSQL PostgreSQL学习手册 学习手册 学习手册 (模式 Schema) ...
下面是PostgreSQL所支持的数值类型的列表和简单说明: 1. 整数类型: 类型smallint、integer和bigint存储各种范围的全部是数字的数,也就是没有小数部分的数字。试图存储超出范围以外的数值将导致一个错误。...
主要介绍了PostgreSQL教程(一):数据表详解表的定义、系统字段、表的修改、表的权限等4大部份内容,内容种包括表的创建、删除、修改、字段的修改、删除、主键和外键、约束添加修改删除等,本文讲解了,需要的朋友可以...
postgresql第三课:眼花缭乱的extension体系1
和数据库不同,模式不是严格分离的:一个用户可以访问他所连接的数据库中的任意模式中的对象,只要他有权限。 我们需要模式有以下几个主要原因: 1). 允许多个用户使用一个数据库而不会干扰其它用户。 2). 把...
PostgreSQL 14.1 手册 PostgreSQL 全球开发组 翻译:彭煜玮1,PostgreSQL中文社区2文档翻译组
赠送jar包:postgresql-42.2.2.jar; 赠送原API文档:postgresql-42.2.2-javadoc.jar; 赠送源代码:postgresql-42.2.2-sources.jar;...人性化翻译,文档中的代码和结构保持不变,注释和说明精准翻译,请放心使用。
赠送jar包:postgresql-42.2.2.jar; 赠送原API文档:postgresql-42.2.2-javadoc.jar;...人性化翻译,文档中的代码和结构保持不变,注释和说明精准翻译,请放心使用。 双语对照,边学技术、边学英语。
工具软件,基于 https://blog.csdn.net/Kafka_yx/article/details/103132469 生成的dll
PostgreSQL监视扩展从PostgreSQL数据库捕获指标,并将其显示在AppDynamics指标浏览器中。 先决条件 在安装扩展之前,需要满足提到的先决条件。 如果未满足指定的先决条件,请不要继续进行扩展安装。 安装 将“ ...
postgresql数据库管理工具,PostgreSQL Maestro是首屈一指的PostgreSQL管理工具,数据库管理,控制和开发。该应用程序还为您提供了一套强大的工具,编辑和执行SQL脚本,构建数字数据的可视化图表,撰写OLAP多维数据...
PostgreSQL Extension扩展时间定时实例,利用pg自身的时间截断函数date_trunc(),所开发.
项目中有需求要垂直分表,即按照时间区间将数据拆分到n个表中,PostgreSQL提供了分区表的功能。分区表实际上是把逻辑上的一个大表分割成物理上的几小块,提供了很多好处,比如: 1、查询性能大幅提升 2、删除历史...
PostgreSQL HTTP API服务器注意:该项目处于无限期搁置状态,并已由取代尝试在上实施类似建议的内容正在安装注意:需要node.js # npm install postgresql-http-server用法# postgresql-... --port ...
此Postgres模块引入了新的数据类型hll ,它是数据结构。 HyperLogLog是一种固定大小的,类似于集合的结构,用于以可调的精度进行不同的值计数。 例如,在1280个字节中, hll可以估计数百亿个不同值的计数,而误差...
赠送jar包:postgresql-42.2.5.jar; 赠送原API文档:postgresql-42.2.5-javadoc.jar;...人性化翻译,文档中的代码和结构保持不变,注释和说明精准翻译,请放心使用。 双语对照,边学技术、边学英语。
PostgreSQL中生成的查询规划是由1到n个规划节点构成的规划树,其中最底层的节点为表扫描节点,用于从数据表中返回检索出的数据行。然而,不同的扫描节点类型代表着不同的表访问模式,如:顺序扫描、索引扫描,以及...
该工具可以帮助用户将MySQL的表结构、数据和查询语句转换为适用于PostgreSQL的格式,以便在两个不同的数据库系统之间进行平滑迁移。 这些工具通常提供以下功能: 数据库结构转换:将MySQL的表、列、索引等结构转换...