开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> postgreSQL源码分析——索引的建立与使用——Hash索引(1) -> 正文阅读

[数据结构与算法]postgreSQL源码分析——索引的建立与使用——Hash索引(1)

2021SC@SDUSC

Hash索引的核心是构建一个Hash表，主要原理就是在Hash表中有一个Hash函数，通过查找键为参数，计算出映射到的桶号，将键值分配到各个桶中。然后仍然需要遍历桶中的内容，并仅返回具有适当哈希码的匹配ctid（行号）。由于存储的“hash code - ctid”对是有序的，因此可以高效地完成此操作。
同时Hash索引表可以分为静态Hash表和动态Hash表，静态Hash表不会增加桶的数目，而动态Hash表可以动态增加桶的数目。PostgreSQL则使用了动态Hash表的结构

Hash索引结构

每一个Hash索引结构如下所示，每一个Hash索引都有四种类型的页面，分别为元页，桶页，溢出页，位图页，接下来会介绍下关于Hash索引的相关的数据结构。
请添加图片描述

Hash的页面结构

Hash的页面结构与B-Tree相似，而其special space的字段填充为HashPageOpaqueData结构，我们从pg的源码找出该结构
 typedef struct HashPageOpaqueData
{
	BlockNumber hasho_prevblkno;	/*  前一页的块号*/
	BlockNumber hasho_nextblkno;	/*  下一页的块号*/
	Bucket		hasho_bucket;	/* 属于某个桶页的桶号*/
	uint16		hasho_flag;		/* 标注该页的所属类型 */
	uint16		hasho_page_id;	/* 该页的Hash索引Id*/
} HashPageOpaqueData;

元页

每个Hash索引都有一个元页，它是该索引的初始页面，它也不属于任何桶，它记录了Hash的版本号，Hash索引记录的索引元组数目，桶的信息，位图等相关信息，其他页的信息也与元页息息相关，我们来看一下pg源码中的元页的数据结构：

typedef struct HashMetaPageData
{
  uint32		hashm_magic;	/*Hash表的magic号*/
  uint32		hashm_version;	/* Hash版本号 */
  double		hashm_ntuples;	/*存储元组的数目*/
  uint16		hashm_ffactor;	/* 与分裂有关*/
  uint16		hashm_bsize;	/* 桶的大小*/
  uint16		hashm_bmsize;	/* 位图的大小，必须是2的幂次 */
  uint16		hashm_bmshift;	/* log2(位图数组的大小） */
  uint32		hashm_maxbucket;	/* 可用的最大桶号 */
  uint32		hashm_highmask; /* 桶号的高16位掩码*/
  uint32		hashm_lowmask;	/* 桶号的低十六位掩码 */
  uint32		hashm_ovflpoint;	/* 分裂次数 */
  uint32		hashm_firstfree;	/* 第一个可能的溢出页号*/
  uint32		hashm_nmaps;	/* 位图的个数 */
  RegProcedure hashm_procid;	/* Hash函数的OID*/
  uint32		hashm_spares[HASH_MAX_SPLITPOINTS]; /* 总共分配的溢出页数目 */
  BlockNumber hashm_mapp[HASH_MAX_BITMAPS];	/*位图的块号*/
} HashMetaPageData;

桶页，溢出页，位图页

桶页：Hash表有多个桶组成，每个桶有一个或多个页组成，每一个桶的第一个页叫做桶页，其他页面称作溢出页，桶页成2的幂次分配，当在元页中记录的splitpoint增加时，桶页成2的幂次增长。
溢出页：当一个元组的内容超过桶页的大小时，需要给该桶增加一个溢出页，溢出页和桶页是通过双向链链接起来的。
位图页：用于管理Hash索引的溢出页和位图页本身的使用情况，如果某个溢出页上的元组都被移除，则将溢出页回收。位图的页面格式如下图所示，他是用比特位来表示位图页或者溢出页是否可用，0不可用，1可用
在这里插入图片描述

和B-Tree相比的优缺点

优点

Hash索引的执行效率很快，时间复杂度低，，索引检索一次到位你，不需要和B-Tree索引一样由根节点再到叶子节点，可以用于等值查询，以及btree索引不支持的大字段类型

缺点

1.由于Hash索引指向的数据是无序的，Hash索引不能进行范围查询，而B+树可以。
2.Hash索引无法被用来避免数据的排序操作。Hash索引中存放的是经过Hash计算之后的Hash值，而且Hash值得大小关系不一定和Hash运算前的键值完全一样。
3当产生大量的Hash冲突时，Hash索引的执行效率会降低，浪费多次数据的访问。