前言
本篇介绍Postgresql中Hash索引的结构以及应用场景。
什么是Hash？
Hash的思想是将一个小数字(从0到N?1，总共N个值)与任何数据类型的值关联起来。这样的关联称为Hash函数。所获得的数字可以用作一个常规数组的索引，其中存储对表行(tid)的引用。这个数组的元素被称为Hash buckets(hash桶)——一个桶可以存储多个tid。
Hash函数越一致地按桶分配源值，就越好。但即使是一个好的hash函数有时也会对不同的源值产生相同的结果——这称为冲突。因此，一个桶可以存储不同键对应的tid，所以，从索引中获取的tid需要重新检查。
哈希索引结构与访问
哈希索引与Btree索引一样。对于某个数据类型的值(索引键)，我们的任务是快速查找匹配的TID。
当插入到索引中时，PostgreSQL中的哈希函数总是返回“integer”类型，取值范围是2^32≈40亿。桶的数量最初等于两个，然后根据数据大小动态增加。桶号可以使用位运算从哈希码计算出来。这个桶就是我们放置TID的桶。但是光存储TID是不够的，因为匹配不同键的tid可以放在同一个存储桶中。为了解决这个问题，除了TID之外，还可以将索引键存储在一个桶中，但这将大大增加索引大小。为了节省空间，桶中存储的不是索引键，而是索引键的哈希码。
当对索引进行检索时，我们首先用哈希函数计算输入键得到桶号，剩下的工作就是遍历桶的内容，并只返回带有适当哈希码的匹配tid。然而，两个不同的键不仅可能进入同一个桶中，而且可能具有相同的四字节哈希码——这种冲突无法避免。因此，access method要求通用索引引擎通过重新检查表行中的条件来验证每个TID(索引引擎可以通过可见性检查来完成此操作)。
Fig 1 哈希索引页结构示意图
如上图所示，哈希索引使用了四种页面(灰色矩形):
- Meta page：页码0，其中包含关于索引内部内容的信息。
- Bucket pages：索引的主页，以“哈希码 - TID”对存储数据。
- Overflow pages：与bucket page结构相同，当一个页面不足以容纳一个bucket时使用。
- Bitmap pages：跟踪当前已清除并且可以在其他存储桶中重用的Overflow page。
从索引页元素开始的向下箭头表示tid，即对表行的引用。
注意哈希索引不能减小大小。如果我们删除一些索引行，那么一旦分配了页面，就不会返回给操作系统，这些页面只会在清理后为新数据重用。减少索引大小的唯一选项是使用REINDEX重建索引或VACUUM FULL命令。
使用限制：
1、PG10版本之前，WAL日志不记录create hash index操作，在数据恢复和流复制时会出现问题。
2、有序的索引键在hash桶中不一定有序，因此只能用于等值查询。