第一篇文章介绍了PostgreSQL索引引擎 ，第二篇文章介绍了访问方法的接口 ，现在我们准备讨论特定类型的索引。 让我们从哈希索引开始。

杂凑

结构形式

一般理论

许多现代编程语言都将哈希表作为基本数据类型。 在外部，哈希表看起来像一个常规数组，该索引使用任何数据类型（例如字符串）而不是整数进行索引。 PostgreSQL中的哈希索引的结构类似。 如何运作？

通常，数据类型的允许值范围非常大：在“文本”类型的列中我们可能会设想多少个不同的字符串？ 同时，某个表的文本列中实际存储了多少个不同的值？ 通常情况下，没有那么多。

散列的思想是将少量（从0到N -1，总共N个值）与任何数据类型的值相关联。 这样的关联称为哈希函数 。 所获得的数字可用作常规数组的索引，其中将存储对表行（TID）的引用。 该数组的元素称为哈希表存储桶 -如果相同的索引值出现在不同的行中，则一个存储桶可以存储多个TID。

哈希函数按存储区分配源值的方式越统一，效果越好。 但是，即使是一个好的哈希函数，有时对于不同的源值也会产生相等的结果-这称为碰撞 。 因此，一个桶可以存储对应于不同密钥的TID，因此，需要重新检查从索引获得的TID。

举例来说：我们可以想到字符串的哪些哈希函数？ 假设存储桶数为256。例如，存储桶号，我们可以采用第一个字符的代码（假设单字节字符编码）。 这是一个很好的哈希函数吗？ 显然不是：如果所有字符串都以相同的字符开头，则所有字符串都将放入一个存储桶中，因此毫无疑问是统一的，将需要重新检查所有值，并且散列将毫无意义。 如果我们将所有以256为模的字符的代码相加怎么办？ 这会好得多，但远非理想。 如果您对PostgreSQL中此类哈希函数的内部结构感兴趣，请查看hashfunc.c中hash_any（）的定义。

索引结构

让我们回到哈希索引。 对于某些数据类型的值（索引键），我们的任务是快速找到匹配的TID。

当插入索引时，让我们计算键的哈希函数。 PostgreSQL中的哈希函数始终返回“整数”类型，其范围为2 32≈40亿个值。 存储桶的数量最初等于2，然后动态增加以适应数据大小。 可以使用位算法从哈希码中计算出存储桶编号。 这是我们放置TID的存储桶。

但这还不够，因为可以将与不同密钥匹配的TID放入同一存储桶中。 我们该怎么办？ 除了TID之外，还可以将键的源值存储在存储桶中，但这会大大增加索引大小。 为了节省空间，存储桶存储了密钥的哈希码，而不是密钥。

搜索索引时，我们计算键的哈希函数并获取存储桶编号。 现在，它仍然需要遍历存储桶的内容，并仅返回具有适当哈希码的匹配TID。 由于存储的“哈希码-TID”对是有序的，因此可以高效地完成此操作。

但是，可能会发生两种不同的密钥，不仅会进入一个存储桶，而且还会具有相同的四字节哈希码-没有人能消除冲突。 因此，访问方法要求通用索引引擎通过重新检查表行中的条件来验证每个TID（引擎可以与可见性检查一起执行此操作）。

将数据结构映射到页面

如果我们从缓冲区缓存管理器而不是从查询计划和执行的角度看待索引，那么事实证明所有信息和所有索引行都必须打包到页面中。 这样的索引页存储在缓冲区高速缓存中，并从那里与表页完全相同的方式从中退出。



如图所示，哈希索引使用四种页面（灰色矩形）：

• 元页面-页面号零，其中包含有关索引内部内容的信息。
• 存储桶页面-索引的主页，将数据存储为“哈希码-TID”对。
• 溢出页面-与存储桶页面的结构相同，并且当一个页面不足以存储桶时使用。
• 位图页面-跟踪当前清除的溢出页面，并且可以将其重新用于其他存储桶。

从索引页元素开始的向下箭头表示TID，即对表行的引用。

每次索引增加，PostgreSQL即时创建的存储桶（因此，页面）数量是上次创建的存储桶数量的两倍。 为了避免一次分配可能潜在的大量页面，版本10使大小增加更加平滑。 对于溢出页面，它们会根据需要进行分配，并在位图页面中进行跟踪，位图页面也会根据需要进行分配。

请注意，哈希索引的大小不能减小。 如果我们删除一些索引行，则一旦分配的页面将不会返回到操作系统，而只会在VACUUMING之后重新用于新数据。 减小索引大小的唯一选择是使用REINDEX或VACUUM FULL命令从头开始重建索引。

例子

让我们看看如何创建哈希索引。 为了避免设计自己的表格，从现在开始，我们将使用航空运输的演示数据库 ，这次我们将考虑航班表。

demo=# create index on flights using hash(flight_no); 

 WARNING: hash indexes are not WAL-logged and their use is discouraged CREATE INDEX 

 demo=# explain (costs off) select * from flights where flight_no = 'PG0001'; 

  QUERY PLAN ---------------------------------------------------- Bitmap Heap Scan on flights Recheck Cond: (flight_no = 'PG0001'::bpchar) -> Bitmap Index Scan on flights_flight_no_idx Index Cond: (flight_no = 'PG0001'::bpchar) (4 rows) 

当前哈希索引实现的不便之处在于，带有索引的操作未记录在预写日志中（PostgreSQL在创建索引时会发出警告）。 因此，哈希索引在失败后将无法恢复，并且不参与复制。 此外，哈希索引的通用性远低于“ B树”，其效率也值得怀疑。 因此，现在使用这样的索引是不切实际的。

但是，这将在PostgreSQL的第10版发布后最早于今年秋天（2017年）改变。 在此版本中，哈希索引最终获得了对预写日志的支持； 此外，还优化了内存分配，并发工作更加高效。

没错 由于PostgreSQL 10哈希索引得到了全面的支持，因此可以不受限制地使用。 该警告不再显示。

散列语义

但是，为什么哈希索引从PostgreSQL诞生到9.6不能使用几乎都可以生存？ 问题是DBMS广泛使用了散列算法（特别是用于散列连接和分组），并且系统必须知道将哪种散列函数应用于哪种数据类型。 但是这种对应关系不是静态的，并且不能一劳永逸地设置，因为PostgreSQL允许动态添加新的数据类型。 这是一种通过散列的访问方法，其中存储了此对应关系，表示为辅助功能与操作员家族的关联。

 demo=# select opf.opfname as opfamily_name, amproc.amproc::regproc AS opfamily_procedure from pg_am am, pg_opfamily opf, pg_amproc amproc where opf.opfmethod = am.oid and amproc.amprocfamily = opf.oid and am.amname = 'hash' order by opfamily_name, opfamily_procedure; 

  opfamily_name | opfamily_procedure --------------------+-------------------- abstime_ops | hashint4 aclitem_ops | hash_aclitem array_ops | hash_array bool_ops | hashchar ... 

尽管未记录这些函数，但可以将它们用于为适当数据类型的值计算哈希码。 例如，如果将“哈希文本”函数用于“ text_ops”运算符系列：

 demo=# select hashtext('one'); 

  hashtext ----------- 127722028 (1 row) 

 demo=# select hashtext('two'); 

  hashtext ----------- 345620034 (1 row) 

物产

让我们看一下哈希索引的属性，其中此访问方法向系统提供有关其自身的信息。 我们上次提供了查询。 现在，我们将超越结果：

  name | pg_indexam_has_property ---------------+------------------------- can_order | f can_unique | f can_multi_col | f can_exclude | t name | pg_index_has_property ---------------+----------------------- clusterable | f index_scan | t bitmap_scan | t backward_scan | t name | pg_index_column_has_property --------------------+------------------------------ asc | f desc | f nulls_first | f nulls_last | f orderable | f distance_orderable | f returnable | f search_array | f search_nulls | f 

散列函数不保留顺序关系：如果一个键的散列函数的值小于另一个键的散列函数的值，则无法得出任何键本身如何排序的结论。 因此，通常哈希索引可以支持唯一的操作“等于”：

 demo=# select opf.opfname AS opfamily_name, amop.amopopr::regoperator AS opfamily_operator from pg_am am, pg_opfamily opf, pg_amop amop where opf.opfmethod = am.oid and amop.amopfamily = opf.oid and am.amname = 'hash' order by opfamily_name, opfamily_operator; 

  opfamily_name | opfamily_operator ---------------+---------------------- abstime_ops | =(abstime,abstime) aclitem_ops | =(aclitem,aclitem) array_ops | =(anyarray,anyarray) bool_ops | =(boolean,boolean) ... 

因此，哈希索引无法返回有序数据（“ can_order”，“ orderable”）。 出于同样的原因，哈希索引不会处理NULL：“等于”操作对于NULL（“ search_nulls”）没有意义。

由于哈希索引不存储键（而仅存储其哈希码），因此它不能用于仅索引访问（“可返回”）。

此访问方法也不支持多列索引（“ can_multi_col”）。

内部构造

从版本10开始，可以通过“ pageinspect ”扩展名查看哈希索引的内部结构。 它将是这样的：

 demo=# create extension pageinspect; 

元页面（我们获得索引中的行数和已用的最大存储桶数）：

 demo=# select hash_page_type(get_raw_page('flights_flight_no_idx',0)); 

  hash_page_type ---------------- metapage (1 row) 

 demo=# select ntuples, maxbucket from hash_metapage_info(get_raw_page('flights_flight_no_idx',0)); 

  ntuples | maxbucket ---------+----------- 33121 | 127 (1 row) 

存储桶页面（我们获得活动元组和死元组的数量，即可以清除的元组的数量）：

 demo=# select hash_page_type(get_raw_page('flights_flight_no_idx',1)); 

  hash_page_type ---------------- bucket (1 row) 

 demo=# select live_items, dead_items from hash_page_stats(get_raw_page('flights_flight_no_idx',1)); 

  live_items | dead_items ------------+------------ 407 | 0 (1 row) 

依此类推。 但是，在不检查源代码的情况下几乎不可能找出所有可用字段的含义。 如果希望这样做，则应从README开始。

继续阅读 。