HASH索引简介

hash索引基于哈希表实现，它通过哈希函数将索引键值映射到哈希表中的一个位置（桶），从而快速定位数据。
关键特定：

• 等级查询：只支持等值查询（=），不支持范围查询（<,>,between等）。
• 快速查找：在理想情况下，哈希索引的查找时间复杂度为O（1）。
• 内存友好：哈希索引通常更小，可以更多地存储在内存中。
• 冲突处理：适用链地址法（每个桶是一个链表）处理哈希冲突。

hash索引的工作原理

基本结构

hash索引将数据存储在一个固定数量的桶（bucket）中，每个桶包含一个指向实际数据行的指针链表。

Hash索引结构： ┌─────────────────────────────────────────┐ │ 桶0: [指针1 -> 指针2 -> ...] │ │ 桶1: [指针3 -> 指针4 -> ...] │ │ ... │ │ 桶N-1: [指针...] │ └─────────────────────────────────────────┘

hash函数

postgresql适用内部定义的hash函数（例如，对于整数、文本等类型都有对应的哈希函数）将键值转换为一个32位的哈希码。然后，通过取模运算确定桶的位置。

bucket_index = hash_code % num_buckets

工作流程

插入流程：

1、对索引键值应用哈希函数，取得哈希码。 2、根据哈希码和桶的数量计算出桶的索引。 3、将新的元组（行）的TID（元组ID）添加到该桶的链表中。

查询流程（等值查询）：

1、对查询键值应用相同的哈希函数，得到哈希码。 2、计算桶索引。 3、遍历该桶中的链表，比较键值是否相等（因为可能有哈希冲突）。 4、返回所有匹配的TID。

hash索引的内部原理

1、初始桶数量

创建hash索引时，初始桶的数量为2，并且随着数据的插入，桶的数量会动态增长。

2、分裂与合并

当每个桶的平均元素数量超过一定阈值时，postgresql会触发桶的分裂，即增加桶的数量（通常是翻倍）并重新哈希分布元素。相反，如果删除很多数据，可能会合并桶。

3、哈希函数

postgresql为每种数据类型提供了特定的哈希函数 ，确保尽可能均匀地分布数据。

适用场景

hash索引最适用于等职查询，尤其时当查询条件非常精确时。

创建hash索引 create index idx_hash on table using hash (column); 等值查询 select * from table where column='value';

• 由于hash索引通常比b-tree索引小，因此在内存受限的环境中，hash索引可能更有效。
• 如果查询模式时随机的等值查询，而不是顺序或范围查询，hash索引可能比b-tree索引更快。
  优势：
• 等值查询速度快：在无冲突的情况下，时间复杂度为O(1)。
• 索引结构紧凑：通常为B-tree索引占用更少的空间。
• 适用于高基数列：对于有大量唯一值的列，hash索引可能更有效。
  劣势：
• 仅支持等值查询：不支持范围查询、排序等。
• 哈希冲突：冲突会降低性能，最坏情况退化为链表查询（O(n)）。
• 无顺序性：不能用于order by操作。
• 不支持多列索引：postgresql的hash索引目前只支持单列（但可以通过表达式索引实现多列的效果）。
• 重建成本高：当桶数量需要调整时，需要重新hash所有元素，成本较高。

哈希冲突： 这是计算机科学中一个基础且重要的概念。哈希冲突，也叫哈希碰撞，是指两个不同的输入（或键）经过同一个哈希函数计算后，得到了相同的哈希值。 哈希函数定义：一个哈希函数H将任意大小的数据映射到固定大小的值（哈希值）。 鸽巢原理（抽屉原理）：如果输入空间大于输出空间(通常都是这样)，那么必然存在至少两个不同的输入对应同一个输出。例如，哈希函数输出的时32为整数，只有2^32种可能，但输入可能时无限多的字符串。所以冲突不可避免。 哈希冲突会导致一些问题，特别是在哈希表这种数据结构中： 1、数据丢失：如果哈希表不处理冲突，后来的键值对可能会覆盖之前的。 2、性能下降：冲突会使得哈希表的查找、插入操作退化为线性搜索。 3、安全问题：恶意攻击者可能利用冲突进行拒绝服务攻击（如hash Dos） 解决哈希冲突的方法： 主要有两类方法：开放寻址法和链地址法。 1、开放寻址法（open addressing） 核心思想：当发生冲突时，按照某种检测序列在哈希表中寻找下一个空闲位置。 2、链地址法（separate chaining） 核心思想：每个哈希桶（bucket）存储一个链表（或其他数据结构），所有映射到同一位置的元素都放在这个链表中。

性能调优

1、调整桶数量（通过maintenance_work_mem间接影响） 2、监控冲突 select tablename，attname，null_frac,avg_width,n_distinct,most_common_vals,most_common_freqs from pg_stats where tablename='table_name' and attname='column_name'; 3、重建索引 reindex index idx_hash;