PostgreSQL GIN 索引

GIN(Generalized Inverted Index, 通用倒排索引) 是一个存储对(key, posting list)集合的索引结构，其中key是一个键值，而posting list 是一组出现过key的位置。如(‘hello', '14:2 23:4')中，表示hello在14:2和23:4这两个元祖出现过，在PG中这些位置实际上就是元组的tid(行号，包括数据块ID（32bit）,以及item point(16 bit) )。

对于表中的每一个属性，在建立对应 gin 索引时，都可能会被解析为多个键值，所以同一个元组的tid可能会出现在多个key的posting list中。

一、索引的逻辑结构

GIN索引在逻辑上可以看成一个relation，该relation有两种结构：

1. 只索引基表的一列的情况：

key	value
Key1	Posting list( or posting tree)
Key2
…

2. 索引基表的多列(复合、多列索引)：

column_id
Column1 num
Column2 num
Column3 num
...

这种结构，对于基表中不同列的相同的key，在GIN索引中也会当作不同的key来处理。

二、索引的物理结构

GIN索引在物理存储上包含如下内容：

1. Entry：GIN索引中的一个元素，可以认为是一个词位，也可以理解为一个key

2. Entry tree：在Entry上构建的B树

3. posting list：一个Entry出现的物理位置(heap ctid, 堆表行号)的链表

4. posting tree：在一个Entry出现的物理位置链表(heap ctid, 堆表行号)上构建的B树，所以posting tree的KEY是ctid，而entry tree的KEY是被索引的列的值

5. pending list：索引元组的临时存储链表，用于fastupdate模式的插入操作

KINGBASE研究院