PostgreSQL的全文检索有GiST和GIN两种索引方式，应该选择哪种索引类型有时让人困惑。
还好，PG手册中有一段指导很有帮助。
http://58.58.27.50:8079/doc/html/9.3.1_zh/
------------------------------------------------------------
在选择要使用的索引类型时，GiST或者GIN考虑这些性能上的差异：
GIN索引查找比GiST快约三倍
GIN索引建立比GIST需要大约三倍的时间。
GIN索引更新比GiST索引速度慢，但如果快速更新支持无效，则慢了大约10倍（详情请见节Section 57.3.1）
GIN索引比GiST索引大两到三倍
一般来说，GIN索引对静态数据是最好的，因为查找速度很快。对于动态数据， GiST索引更新比较快。具体而言，GiST索引非常适合动态数据，并且如果独特的字（词）在100,000以下， 则比较快，而GIN索引将处理100,000+词汇，但是更新比较慢。
以上是一些经验上的认识，为了更好理解GiST如何在全文检索中发挥作用，下面了解一下GiST索引的具体算法。
(GIN采用的是倒排索引算法，倒排索引在全文检索中应用太广了，就没必要多说了。）
PostgreSQL的全文检索会把文档切成由若干词元(keyword)组成的向量，即tsvector。tsvector的GiST操作符类采用类似签名文件索引的算法实现。大致如下
1.存储结构
a）页节点的索引项
页节点的索引项有3种存储格式
ARRKEY
为tsvector中的每个词元生成一个4字节的Sign值(哈希值），索引项存储这些Sign值的数组。
SIGNKEY
当词元太多导致ARRKEY形式的索引项大小超过TOAST_INDEX_TARGET(大约500多个字节)，则采用SIGNKEY形式的存储。
SIGNKEY形式的存储是一个992bit的Bit向量，把每个词元的Sign值对992取模值，模值对应的SIGNKEY的Bit位置1。
ALLISTRUE
如果在SIGNKEY形式的存储下，所有的Bit位都是1，那么采用ALLISTRUE格式，表示匹配所有关键字。ALLISTRUE格式不需要保存实际的Bit向量，可节省空间。
b)非页节点的索引项
非页节点的索引项只有SIGNKEY和ALLISTRUE 2种存储格式。
2.索引项插入节点分裂
当插入一个新的索引项时，选择一个插入后需要由0置1的索引项bit位数最少的子树作为插入位置。
当一个节点的元素满了，需要进行分裂时。选择一个能使分裂后2个子树不同的bit位最多的分裂方案。
这样可保持索引树的平衡。
src/backend/utils/adt/tsgistidx.c
相关宏定义
点击(此处)折叠或打开
...
#define SIGLENINT 31 /* >121 => key will toast, so it will not work
* !!! */
#define SIGLEN ( sizeof(int32) * SIGLENINT )
#define SIGLENBIT (SIGLEN * BITS_PER_BYTE)
typedef char BITVEC[SIGLEN];
typedef char *BITVECP;
/*
* type of GiST index key
*/
typedef struct
{
int32 vl_len_; /* varlena header (do not touch */
int32 flag;
char data[1];
} SignTSVector;
#define ARRKEY 0x01
#define SIGNKEY 0x02
#define ALLISTRUE 0x04
#define ISARRKEY(x) ( ((SignTSVector*)(x))->flag & ARRKEY )
#define ISSIGNKEY(x) ( ((SignTSVector*)(x))->flag & SIGNKEY )
#define ISALLTRUE(x) ( ((SignTSVector*)(x))->flag & ALLISTRUE )
索引的存储格式
Datum
gtsvector_compress(PG_FUNCTION_ARGS)
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
GISTENTRY *retval = entry;
if (entry->leafkey)
{ /* tsvector */
SignTSVector *res;
TSVector val = DatumGetTSVector(entry->key);
int32 len;
int32 *arr;
WordEntry *ptr = ARRPTR(val);
char *words = STRPTR(val);
//对tsvector中的每个keywork，生成4字节的哈希值（sign），放到SignTSVector中，SignTSVector的flag是ARRKEY，大小为keywork数。
len = CALCGTSIZE(ARRKEY, val->size);
res = (SignTSVector *) palloc(len);
SET_VARSIZE(res, len);
res->flag = ARRKEY;
arr = GETARR(res);
len = val->size;
while (len--)
{
pg_crc32 c;
INIT_CRC32(c);
COMP_CRC32(c, words + ptr->pos, ptr->len);
FIN_CRC32(c);
*arr = *(int32 *) &c;
arr++;
ptr++;
}
//去除重复Sign
len = uniqueint(GETARR(res), val->size);
if (len != val->size)
/*
* there is a collision of hash-function; len is always less than
* val->size
*/
len = CALCGTSIZE(ARRKEY, len);
res = (SignTSVector *) repalloc((void *) res, len);
SET_VARSIZE(res, len);
//如果Sign向量大于进行TOAST的阈值，再对Sign向量生成一个大的SIGNKEY，SIGNKEY由124（124=31*32）个字节992个bit组成，针对每个Sign值对992取模值，模值对应的SIGNKEY的Bit位置1。
/* make signature, if array is too long */
if (VARSIZE(res) > TOAST_INDEX_TARGET)
SignTSVector *ressign;
len = CALCGTSIZE(SIGNKEY, 0);//sizeof(int32)*31
ressign = (SignTSVector *) palloc(len);
SET_VARSIZE(ressign, len);
ressign->flag = SIGNKEY;
makesign(GETSIGN(ressign), res);
res = ressign;
retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
gistentryinit(*retval, PointerGetDatum(res),
entry->rel, entry->page,
entry->offset, FALSE);
}
else if (ISSIGNKEY(DatumGetPointer(entry->key)) &&
!ISALLTRUE(DatumGetPointer(entry->key)))
{
int32 i,
len;
BITVECP sign = GETSIGN(DatumGetPointer(entry->key));
//对BIT向量，如果所有BIT位都置为1了，生成一个只有数据头的SignTSVector，并设置ALLISTRUE标志，减少索引的存储空间占用。
LOOPBYTE
if ((sign[i] & 0xff) != 0xff)
PG_RETURN_POINTER(retval);
len = CALCGTSIZE(SIGNKEY | ALLISTRUE, 0);
res->flag = SIGNKEY | ALLISTRUE;
PG_RETURN_POINTER(retval);
}
特定索引项目是否满足查询条件的判断
gtsvector_consistent(PG_FUNCTION_ARGS)
TSQuery query = PG_GETARG_TSQUERY(1);
/* StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); */
/* Oid subtype = PG_GETARG_OID(3); */
bool *recheck = (bool *) PG_GETARG_POINTER(4);
SignTSVector *key = (SignTSVector *) DatumGetPointer(entry->key);
/* All cases served by this function are inexact */
*recheck = true;
if (!query->size)
PG_RETURN_BOOL(false);
if (ISSIGNKEY(key))
if (ISALLTRUE(key))
PG_RETURN_BOOL(true);
PG_RETURN_BOOL(TS_execute(
GETQUERY(query),
(void *) GETSIGN(key), false,
checkcondition_bit
));
else
{ /* only leaf pages */
CHKVAL chkval;
chkval.arrb = GETARR(key);
chkval.arre = chkval.arrb + ARRNELEM(key);
(void *) &chkval, true,
checkcondition_arr
//对SIGNKEY形式的索引项。在索引项中找到query单词的sign对应的bit位。为1则匹配。
static bool
checkcondition_bit(void *checkval, QueryOperand *val)
/*
* we are not able to find a a prefix in signature tree
*/
if (val->prefix)
return true;
return GETBIT(checkval, HASHVAL(val->valcrc));
//对ARRKEY形式的索引项，二分查找遍历索引项中的所有key的sign，如存在一致的返回true。
* is there value 'val' in array or not ?
checkcondition_arr(void *checkval, QueryOperand *val)
int32 *StopLow = ((CHKVAL *) checkval)->arrb;
int32 *StopHigh = ((CHKVAL *) checkval)->arre;
int32 *StopMiddle;
/* Loop invariant: StopLow = val StopHigh */
* we are not able to find a a prefix by hash value
while (StopLow StopHigh)
StopMiddle = StopLow + (StopHigh - StopLow) / 2;
if (*StopMiddle == val->valcrc)
return (true);
else if (*StopMiddle val->valcrc)
StopLow = StopMiddle + 1;
else
StopHigh = StopMiddle;
return (false);
key集合的合并
通过BIT向量的各bit的或操作合并key。所有非页节点的索引项的key都是BIT向量（SIGNKEY）形式。
static int32
unionkey(BITVECP sbase, SignTSVector *add)
int32 i;
if (ISSIGNKEY(add))
BITVECP sadd = GETSIGN(add);
if (ISALLTRUE(add))
return 1;
sbase[i] |= sadd[i];
int32 *ptr = GETARR(add);
for (i = 0; i ARRNELEM(add); i++)
HASH(sbase, ptr[i]);
return 0;
gtsvector_union(PG_FUNCTION_ARGS)
GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
int *size = (int *) PG_GETARG_POINTER(1);
BITVEC base;
int32 i,
len;
int32 flag = 0;
SignTSVector *result;
MemSet((void *) base, 0, sizeof(BITVEC));
for (i = 0; i entryvec->n; i++)
if (unionkey(base, GETENTRY(entryvec, i)))
flag = ALLISTRUE;
break;
flag |= SIGNKEY;
len = CALCGTSIZE(flag, 0);
result = (SignTSVector *) palloc(len);
*size = len;
SET_VARSIZE(result, len);
result->flag = flag;
if (!ISALLTRUE(result))
memcpy((void *) GETSIGN(result), (void *) base, sizeof(BITVEC));
PG_RETURN_POINTER(result);
新索引项的插入和节点分裂
新索引项的插入位置和节点分裂的策略是控制树平衡的关键。代码里通过计算Key集合签名的海明距离（对应位上编码不同的位数）来选择最优策略。。对于插入操作，尽量使插入前后的Key集合签名的海明距离最小；对于分裂操作，尽量使分裂后2个子节点间的海明距离最大。海明距离的计算通过下面的hemdistsign()函数完成。gtsvector_penalty()和gtsvector_picksplit()都调用了这个函数。
static int
hemdistsign(BITVECP a, BITVECP b)
int i,
diff,
dist = 0;
LOOPBYTE
diff = (unsigned char) (a[i] ^ b[i]);
dist += number_of_ones[diff];
return dist;
![241 Different Ways to Add Parentheses（C代码版）[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)