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=)