PostgreSQL索引详解3——hash索引

1、简介

现代许多编程语言都将哈希表作为基本的数据类型。哈希表是根据键（Key）而直接访问在内存储存位置的数据结构。它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做哈希表。
在PostgreSQL中的hash索引也是类似的机构。其主要思想是：将少量的数字（从0到N -1，总共N个值）与任何数据类型的值相关联。这样的关联称为哈希函数。所获得的数字可用作常规数组的索引，其中将存储对表行ctid的引用。该数组的元素称为哈希表的bucket，如果相同的索引值出现在不同的行中，则一个bucket中可以存储多个ctid。
哈希函数按存储桶分配源值的方式越统一，效果越好。但是，即使是一个良好的哈希函数，有时也会对不同的源值产生相等的结果——这称为冲突。一个bucket可以存储对应于不同键的ctid，但因此需要重新检查从索引获得的ctid。

2、索引结构

hash索引其主要目的就是对于某些数据类型（索引键）的值，我们的任务是快速找到匹配的行的ctid。
当插入索引时，让我们计算键的哈希函数。PostgreSQL中的哈希函数总是返回integer类型，其范围为2的32次方≈40亿个值。存储桶的数量最初等于2，然后根据数据大小动态增加。bucket编号可以使用位算法从哈希码中计算出来。这是我们将放置ctid的bucket。
当搜索索引时，我们计算键的哈希函数并获取bucket编号。现在，仍然需要遍历bucket的内容，并仅返回具有适当哈希码的匹配ctid。由于存储的“hash code - ctid”对是有序的，因此可以高效地完成此操作。

如图所示，哈希索引包含4种页：meta page, primary bucket page, overflow page, bitmap page。

• metapage（0号页） , 包含了HASH索引的控制信息，指导如何找到其他页面（每个bucket的primary
  page），以及当前存储概貌。其他索引的0号页基本都是这一个套路。
• primary bucket page，hash
  index将存储划分为多个bucket（逻辑概念），每个bucket中包含若干page（每个bucket的page数量不需要一致），当插入数据时，根据计算得到的哈希，通过映射算法，映射到某个bucket，也就是说数据首先知道应该插入哪个bucket中，然后插入bucket中的primary
  page