传统上，实现一种新的索引访问方法意味着大量艰难的工作。必须理解数据库的内部机制，例如锁管理器和预写式日志。GiST接口具有很高的抽象层次，只要求访问方法实现者实现被访问数据类型的语义。GiST层本身会处理并发、日志记录以及树结构的搜索。
这种可扩展性不应与其他标准搜索树在可处理数据方面的可扩展性相混淆。例如，PostgreSQL支持可扩展的 B-树和哈希索引。这意味着你可以用PostgreSQL在任意数据类型上构建 B-树或哈希索引。但 B-树只支持范围谓词（<、=、>），而哈希索引只支持等值查询。
因此，如果你用PostgreSQL的 B-树为一个图像集合建立索引，你只能发出诸如“imagex 是否等于 imagey”、“imagex 是否小于 imagey”以及“imagex 是否大于 imagey”之类的查询。取决于你如何在这种上下文中定义“等于”、“小于”和“大于”，这可能仍然有用。不过，使用基于GiST的索引，你就可以构造出能够提出特定领域问题的查询方式，例如“找出所有马的图片”或者“找出所有曝光过度的图片”。
要让一个GiST访问方法运行起来，只需实现几个用户定义的方法，这些方法定义了树中键的行为。当然，要支持复杂查询，这些方法本身也必须足够巧妙；但对于所有标准查询（B-树、R 树等），它们都相对直接。简而言之，GiST把可扩展性与通用性、代码复用以及清晰的接口结合了起来。
一个GiST索引操作符类必须提供五个方法，另外还有六个可选方法。通过正确实现same、consistent和union方法可以保证索引的正确性，而索引的效率（大小与速度）则取决于penalty和picksplit方法。两个可选方法是compress和decompress，它们允许索引的内部树数据使用与其所索引数据不同的类型。叶子必须是被索引数据类型，而其他树节点可以是任意 C 结构体（但这里仍必须遵守PostgreSQL的数据类型规则，关于变长数据可参见varlena）。如果树的内部数据类型在 SQL 层存在，可以使用CREATE OPERATOR CLASS命令的STORAGE选项。可选的第八个方法是distance，若操作符类希望支持有序扫描（最近邻搜索），则需要它。可选的第九个方法fetch在操作符类希望支持仅索引扫描时需要，除非省略了compress方法。可选的第十个方法options在操作符类具有用户指定参数时需要。可选的第十一个方法sortsupport用于加速构建GiST索引。
consistent #给定一个索引项p和一个查询值q，该函数判断该索引项是否与该查询“一致”；也就是说，该索引项所代表的某一行是否可能使谓词“indexed_column indexable_operator q”为真。对于叶子索引项，这等同于测试该可索引条件；而对于内部树节点，这决定是否有必要扫描该树节点所表示的索引子树。当结果为true时，还必须返回一个recheck标志。它表示该谓词是确定为真，还是仅可能为真。如果recheck = false，则该索引已经精确测试了谓词条件；如果recheck = true，则该行只是候选匹配。在这种情况下，系统会自动针对实际行值计算indexable_operator，以判断它是否真的匹配。这种约定使GiST能够同时支持无损和有损的索引结构。
该函数的SQL声明必须如下所示：
CREATE OR REPLACE FUNCTION my_consistent(internal, data_type, smallint, oid, internal) RETURNS bool AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
而 C 模块中的对应代码则可以遵循如下框架：
PG_FUNCTION_INFO_V1(my_consistent);
Datum
my_consistent(PG_FUNCTION_ARGS)
{
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
data_type *query = PG_GETARG_DATA_TYPE_P(1);
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
/* Oid subtype = PG_GETARG_OID(3); */
bool *recheck = (bool *) PG_GETARG_POINTER(4);
data_type *key = DatumGetDataType(entry->key);
bool retval;
/*
* determine return value as a function of strategy, key and query.
*
* Use GIST_LEAF(entry) to know where you're called in the index tree,
* which comes handy when supporting the = operator for example (you could
* check for non empty union() in non-leaf nodes and equality in leaf
* nodes).
*/
*recheck = true; /* or false if check is exact */
PG_RETURN_BOOL(retval);
}
这里，key是索引中的一个元素，而query是在该索引中查找的值。StrategyNumber参数指示应用的是操作符类中的哪个操作符，它对应于CREATE OPERATOR CLASS命令中的某个操作符编号。
取决于你在该类中包含了哪些操作符，query的数据类型可能会随操作符而变化，因为它将是操作符右侧的类型，而这可能不同于左侧出现的被索引数据类型。（上面的代码框架假定只可能有一种类型；如果不是这样，获取query参数值的方式就必须依赖于具体的操作符。）建议在consistent函数的 SQL 声明中，对query参数使用该操作符类的被索引数据类型，即使实际类型可能因为操作符不同而有所不同。
union #该方法用于汇总树中的信息。给定一组项，该函数生成一个新的索引项，用来表示所有给定项。
该函数的SQL声明必须如下所示：
CREATE OR REPLACE FUNCTION my_union(internal, internal) RETURNS storage_type AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
而 C 模块中的对应代码则可以遵循如下框架：
PG_FUNCTION_INFO_V1(my_union);
Datum
my_union(PG_FUNCTION_ARGS)
{
GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
GISTENTRY *ent = entryvec->vector;
data_type *out,
*tmp,
*old;
int numranges,
i = 0;
numranges = entryvec->n;
tmp = DatumGetDataType(ent[0].key);
out = tmp;
if (numranges == 1)
{
out = data_type_deep_copy(tmp);
PG_RETURN_DATA_TYPE_P(out);
}
for (i = 1; i < numranges; i++)
{
old = out;
tmp = DatumGetDataType(ent[i].key);
out = my_union_implementation(out, tmp);
}
PG_RETURN_DATA_TYPE_P(out);
}
如你所见，在这个框架里，我们处理的是一种满足union(X, Y, Z) = union(union(X, Y), Z)的数据类型。对于不满足这一性质的数据类型，只需在这个GiST支持方法中实现正确的 union 算法即可。
union函数的结果必须是索引存储类型的值，不管该类型是什么（它可能与被索引列的类型相同，也可能不同）。union函数应返回一个指向新近通过palloc()分配的内存的指针。即使没有类型变化，也不能原样返回输入值。
如上所示，union函数的第一个internal参数实际上是一个GistEntryVector指针。第二个参数是一个指向整数变量的指针，可以忽略。（过去要求union函数把结果值的大小存入该变量，但现在已经不再需要。）
compress #将一个数据项转换成适合在索引页中物理存储的格式。如果省略compress方法，数据项将不经修改地存储在索引中。
该函数的SQL声明必须如下所示：
CREATE OR REPLACE FUNCTION my_compress(internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
而 C 模块中的对应代码则可以遵循如下框架：
PG_FUNCTION_INFO_V1(my_compress);
Datum
my_compress(PG_FUNCTION_ARGS)
{
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
GISTENTRY *retval;
if (entry->leafkey)
{
/* replace entry->key with a compressed version */
compressed_data_type *compressed_data = palloc(sizeof(compressed_data_type));
/* fill *compressed_data from entry->key ... */
retval = palloc(sizeof(GISTENTRY));
gistentryinit(*retval, PointerGetDatum(compressed_data),
entry->rel, entry->page, entry->offset, FALSE);
}
else
{
/* typically we needn't do anything with non-leaf entries */
retval = entry;
}
PG_RETURN_POINTER(retval);
}
当然，为了压缩叶子节点，你必须把compressed_data_type改成要转换成的具体类型。
decompress #将数据项的存储表示转换成操作符类中其他 GiST 方法能够操作的格式。如果省略decompress方法，就假定其他 GiST 方法可以直接处理存储的数据格式。（decompress不一定是compress方法的逆操作；特别是如果compress是有损的，那么decompress就不可能精确重建原始数据。decompress也不一定等同于fetch，因为其他 GiST 方法未必需要把数据完全重建出来。）
该函数的SQL声明必须如下所示：
CREATE OR REPLACE FUNCTION my_decompress(internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
而 C 模块中的对应代码则可以遵循如下框架：
PG_FUNCTION_INFO_V1(my_decompress);
Datum
my_decompress(PG_FUNCTION_ARGS)
{
PG_RETURN_POINTER(PG_GETARG_POINTER(0));
}
上述框架适用于不需要解压的情况。（当然，在这种情况下，直接完全省略该方法会更简单，而且也推荐这么做。）
penalty #返回一个值，指示把新项插入树中特定分支的“代价”。项会沿着树中penalty最小的路径插入。penalty返回的值应为非负；如果返回负值，它将被按零处理。
该函数的SQL声明必须如下所示：
CREATE OR REPLACE FUNCTION my_penalty(internal, internal, internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT; -- in some cases penalty functions need not be strict
而 C 模块中的对应代码则可以遵循如下框架：
PG_FUNCTION_INFO_V1(my_penalty);
Datum
my_penalty(PG_FUNCTION_ARGS)
{
GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
float *penalty = (float *) PG_GETARG_POINTER(2);
data_type *orig = DatumGetDataType(origentry->key);
data_type *new = DatumGetDataType(newentry->key);
*penalty = my_penalty_implementation(orig, new);
PG_RETURN_POINTER(penalty);
}
出于历史原因，penalty函数并不是直接返回一个float结果；相反，它必须把该值存储到第三个参数指示的位置。返回值本身会被忽略，不过通常会返回该参数的地址。
penalty函数对于索引的良好性能至关重要。它会在插入时用于决定在树中应沿着哪个分支向下，以便选择把新项加到哪里。在查询时，索引越平衡，查找就越快。
picksplit #当索引页必须分裂时，该函数决定页面上的哪些项留在旧页中，哪些移到新页中。
该函数的SQL声明必须如下所示：
CREATE OR REPLACE FUNCTION my_picksplit(internal, internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
而 C 模块中的对应代码则可以遵循如下框架：
PG_FUNCTION_INFO_V1(my_picksplit);
Datum
my_picksplit(PG_FUNCTION_ARGS)
{
GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
OffsetNumber maxoff = entryvec->n - 1;
GISTENTRY *ent = entryvec->vector;
int i,
nbytes;
OffsetNumber *left,
*right;
data_type *tmp_union;
data_type *unionL;
data_type *unionR;
GISTENTRY **raw_entryvec;
maxoff = entryvec->n - 1;
nbytes = (maxoff + 1) * sizeof(OffsetNumber);
v->spl_left = (OffsetNumber *) palloc(nbytes);
left = v->spl_left;
v->spl_nleft = 0;
v->spl_right = (OffsetNumber *) palloc(nbytes);
right = v->spl_right;
v->spl_nright = 0;
unionL = NULL;
unionR = NULL;
/* Initialize the raw entry vector. */
raw_entryvec = (GISTENTRY **) malloc(entryvec->n * sizeof(void *));
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
raw_entryvec[i] = &(entryvec->vector[i]);
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
{
int real_index = raw_entryvec[i] - entryvec->vector;
tmp_union = DatumGetDataType(entryvec->vector[real_index].key);
Assert(tmp_union != NULL);
/*
* Choose where to put the index entries and update unionL and unionR
* accordingly. Append the entries to either v->spl_left or
* v->spl_right, and care about the counters.
*/
if (my_choice_is_left(unionL, curl, unionR, curr))
{
if (unionL == NULL)
unionL = tmp_union;
else
unionL = my_union_implementation(unionL, tmp_union);
*left = real_index;
++left;
++(v->spl_nleft);
}
else
{
/*
* Same on the right
*/
}
}
v->spl_ldatum = DataTypeGetDatum(unionL);
v->spl_rdatum = DataTypeGetDatum(unionR);
PG_RETURN_POINTER(v);
}
注意，picksplit函数的结果是通过修改传入的v结构来传递的。返回值本身会被忽略，不过通常会返回v的地址。
和penalty一样，picksplit函数对于索引的良好性能至关重要。设计合适的penalty和picksplit实现，正是实现高性能GiST索引的难点所在。
same #如果两个索引项相同则返回真，否则返回假。（“索引项”是索引存储类型的值，不一定是原始被索引列的类型。）
该函数的SQL声明必须如下所示：
CREATE OR REPLACE FUNCTION my_same(storage_type, storage_type, internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
而 C 模块中的对应代码则可以遵循如下框架：
PG_FUNCTION_INFO_V1(my_same);
Datum
my_same(PG_FUNCTION_ARGS)
{
prefix_range *v1 = PG_GETARG_PREFIX_RANGE_P(0);
prefix_range *v2 = PG_GETARG_PREFIX_RANGE_P(1);
bool *result = (bool *) PG_GETARG_POINTER(2);
*result = my_eq(v1, v2);
PG_RETURN_POINTER(result);
}
出于历史原因，same函数并不是直接返回一个布尔结果；相反，它必须把该标志存储到第三个参数指示的位置。返回值本身会被忽略，不过通常会返回该参数的地址。
distance #给定一个索引项p和一个查询值q，该函数确定索引项与查询值之间的“距离”。如果操作符类包含任何排序操作符，就必须提供此函数。使用排序操作符的查询会优先返回“距离”值最小的索引项，因此结果必须与该操作符的语义一致。对于叶子索引项，结果仅表示到该索引项的距离；对于内部树节点，结果必须是其任意子项可能具有的最小距离。
该函数的SQL声明必须如下所示：
CREATE OR REPLACE FUNCTION my_distance(internal, data_type, smallint, oid, internal) RETURNS float8 AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
而 C 模块中的对应代码则可以遵循如下框架：
PG_FUNCTION_INFO_V1(my_distance);
Datum
my_distance(PG_FUNCTION_ARGS)
{
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
data_type *query = PG_GETARG_DATA_TYPE_P(1);
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
/* Oid subtype = PG_GETARG_OID(3); */
/* bool *recheck = (bool *) PG_GETARG_POINTER(4); */
data_type *key = DatumGetDataType(entry->key);
double retval;
/*
* determine return value as a function of strategy, key and query.
*/
PG_RETURN_FLOAT8(retval);
}
distance函数的参数与consistent函数的参数完全相同。
在确定距离时允许有一定近似，只要结果永不大于该项的实际距离即可。因此，例如在几何应用中，到外包盒的距离通常就足够了。对于内部树节点，返回的距离不能大于其任一子节点的距离。如果返回的距离不精确，函数必须将*recheck设为 true。（对内部树节点则不必这样做；对它们总是假定计算结果不精确。）在这种情况下，执行器会在从堆中取出元组后计算准确距离，并在必要时重新排序这些元组。
如果距离函数对任何叶节点都返回*recheck = true，原始排序操作符的返回类型必须是float8或float4，且距离函数的结果值必须能与原始排序操作符的结果进行比较，因为执行器会同时使用距离函数结果和重新计算得到的排序操作符结果进行排序。否则，距离函数的结果值可以是任意有限的float8值，只要这些结果值的相对顺序与排序操作符返回的顺序一致即可。（无穷大和负无穷在内部用于处理空值等情况，因此不建议distance函数返回这些值。）
fetch #为了支持仅索引扫描，将数据项的压缩索引表示转换为原始数据类型。返回的数据必须是最初被索引值的精确、无损副本。
该函数的SQL声明必须如下所示：
CREATE OR REPLACE FUNCTION my_fetch(internal) RETURNS internal AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
参数是一个指向GISTENTRY结构的指针。进入该函数时，它的key字段包含一个压缩形式的非 NULL 叶子 datum。返回值是另一个GISTENTRY结构，其key字段以原始、未压缩形式包含同一个 datum。如果该操作符类的 compress 函数对叶子项不做任何处理，fetch方法可以原样返回该参数。或者，如果该操作符类没有 compress 函数，那么fetch方法也可以省略，因为它必然是空操作。
而 C 模块中的对应代码则可以遵循如下框架：
PG_FUNCTION_INFO_V1(my_fetch);
Datum
my_fetch(PG_FUNCTION_ARGS)
{
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
input_data_type *in = DatumGetPointer(entry->key);
fetched_data_type *fetched_data;
GISTENTRY *retval;
retval = palloc(sizeof(GISTENTRY));
fetched_data = palloc(sizeof(fetched_data_type));
/*
* Convert 'fetched_data' into the a Datum of the original datatype.
*/
/* fill *retval from fetched_data. */
gistentryinit(*retval, PointerGetDatum(converted_datum),
entry->rel, entry->page, entry->offset, FALSE);
PG_RETURN_POINTER(retval);
}
如果 compress 方法对叶子项是有损的，该操作符类就不能支持仅索引扫描，并且不得定义fetch函数。
options #允许定义用户可见参数，用来控制操作符类的行为。
该函数的SQL声明必须如下所示：
CREATE OR REPLACE FUNCTION my_options(internal) RETURNS void AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
该函数会收到一个指向local_relopts结构的指针，需要在其中填充一组选项，这些选项是该操作符类特有的。其他支持函数可以使用PG_HAS_OPCLASS_OPTIONS()和PG_GET_OPCLASS_OPTIONS()宏来访问这些选项。
下面给出了 my_options() 的一个实现示例，以及其他支持函数如何使用这些参数：
typedef enum MyEnumType
{
MY_ENUM_ON,
MY_ENUM_OFF,
MY_ENUM_AUTO
} MyEnumType;
typedef struct
{
int32 vl_len_; /* varlena header (do not touch directly!) */
int int_param; /* integer parameter */
double real_param; /* real parameter */
MyEnumType enum_param; /* enum parameter */
int str_param; /* string parameter */
} MyOptionsStruct;
/* String representation of enum values */
static relopt_enum_elt_def myEnumValues[] =
{
{"on", MY_ENUM_ON},
{"off", MY_ENUM_OFF},
{"auto", MY_ENUM_AUTO},
{(const char *) NULL} /* list terminator */
};
static char *str_param_default = "default";
/*
* Sample validator: checks that string is not longer than 8 bytes.
*/
static void
validate_my_string_relopt(const char *value)
{
if (strlen(value) > 8)
ereport(ERROR,
(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
errmsg("str_param must be at most 8 bytes")));
}
/*
* Sample filler: switches characters to lower case.
*/
static Size
fill_my_string_relopt(const char *value, void *ptr)
{
char *tmp = str_tolower(value, strlen(value), DEFAULT_COLLATION_OID);
int len = strlen(tmp);
if (ptr)
strcpy(ptr, tmp);
pfree(tmp);
return len + 1;
}
PG_FUNCTION_INFO_V1(my_options);
Datum
my_options(PG_FUNCTION_ARGS)
{
local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0);
init_local_reloptions(relopts, sizeof(MyOptionsStruct));
add_local_int_reloption(relopts, "int_param", "integer parameter",
100, 0, 1000000,
offsetof(MyOptionsStruct, int_param));
add_local_real_reloption(relopts, "real_param", "real parameter",
1.0, 0.0, 1000000.0,
offsetof(MyOptionsStruct, real_param));
add_local_enum_reloption(relopts, "enum_param", "enum parameter",
myEnumValues, MY_ENUM_ON,
"Valid values are: \"on\", \"off\" and \"auto\".",
offsetof(MyOptionsStruct, enum_param));
add_local_string_reloption(relopts, "str_param", "string parameter",
str_param_default,
&validate_my_string_relopt,
&fill_my_string_relopt,
offsetof(MyOptionsStruct, str_param));
PG_RETURN_VOID();
}
PG_FUNCTION_INFO_V1(my_compress);
Datum
my_compress(PG_FUNCTION_ARGS)
{
int int_param = 100;
double real_param = 1.0;
MyEnumType enum_param = MY_ENUM_ON;
char *str_param = str_param_default;
/*
* Normally, when opclass contains 'options' method, then options are always
* passed to support functions. However, if you add 'options' method to
* existing opclass, previously defined indexes have no options, so the
* check is required.
*/
if (PG_HAS_OPCLASS_OPTIONS())
{
MyOptionsStruct *options = (MyOptionsStruct *) PG_GET_OPCLASS_OPTIONS();
int_param = options->int_param;
real_param = options->real_param;
enum_param = options->enum_param;
str_param = GET_STRING_RELOPTION(options, str_param);
}
/* the rest implementation of support function */
}
由于GiST中键的表示是灵活的，它可能依赖于用户指定的参数。例如，可以指定键签名的长度。参见gtsvector_options()。
sortsupport #返回一个比较器函数，用某种能够保持局部性的方式对数据进行排序。它由CREATE INDEX和REINDEX命令使用。所创建索引的质量取决于该比较器函数确定的排序顺序在多大程度上保持了输入的局部性。
sortsupport方法是可选的。如果未提供，CREATE INDEX会通过使用penalty和picksplit函数将每个元组插入树中来构建索引，这会慢得多。
该函数的SQL声明必须如下所示：
CREATE OR REPLACE FUNCTION my_sortsupport(internal) RETURNS void AS 'MODULE_PATHNAME' LANGUAGE C STRICT;
参数是一个指向SortSupport结构的指针。至少，该函数必须填写其中的 comparator 字段。比较器接受三个参数：两个要比较的 Datum，以及一个指向SortSupport结构的指针。这两个 Datum 就是两个被索引的值，其格式与它们在索引中的存储格式相同；也就是说，是compress方法返回的格式。完整的 API 定义在src/include/utils/sortsupport.h中。
而 C 模块中的对应代码则可以遵循如下框架：
PG_FUNCTION_INFO_V1(my_sortsupport);
static int
my_fastcmp(Datum x, Datum y, SortSupport ssup)
{
/* establish order between x and y by computing some sorting value z */
int z1 = ComputeSpatialCode(x);
int z2 = ComputeSpatialCode(y);
return z1 == z2 ? 0 : z1 > z2 ? 1 : -1;
}
Datum
my_sortsupport(PG_FUNCTION_ARGS)
{
SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
ssup->comparator = my_fastcmp;
PG_RETURN_VOID();
}
所有 GiST 支持方法通常都在短生命周期的内存上下文中被调用；也就是说，每处理完一个元组，CurrentMemoryContext都会被重置。因此通常无需过分担心释放所有通过 palloc 分配的内容。不过，在某些情况下，让支持方法在重复调用之间缓存数据是有用的。要做到这一点，可将寿命更长的数据分配在fcinfo->flinfo->fn_mcxt中，并在fcinfo->flinfo->fn_extra中保存指向它的指针。这类数据会在一次索引操作期间存活（例如一次 GiST 索引扫描、索引构建或索引元组插入）。在替换fn_extra值时要注意 pfree 旧值，否则泄漏会在整个操作期间不断累积。
如果您发现文档中有不正确的内容、与您使用特定功能的经验不符或需要进一步说明，请使用此表单来报告文档问题。