GiST(通用搜索树)

定义

GiST(Generalized Search Tree,通用搜索树)是一个可扩展的索引框架,由 Joseph Hellerstein 等人于 1995 年提出,在 PostgreSQL 中得到最著名的工程实现。它把平衡树索引的公共骨架(页管理、分裂、并发、恢复)与具体数据类型的语义解耦。

原理

开发者只需为数据类型实现少量回调函数,如 consistent(判断子树是否可能包含匹配项)、union(合并键)、penalty(插入代价)、picksplit(节点分裂)等,即可获得一个完整的索引类型。B 树、R 树在该框架下都可视为特例。

应用

PostgreSQL 中大量索引能力构建于 GiST 之上:PostGIS 的空间索引、范围类型索引、pg_trgm 的模糊匹配、ltree 层级查询、全文检索(tsvector)以及排除约束(EXCLUDE)等。KNN-GiST 扩展还支持"按距离排序取最近邻"查询。

意义

GiST 使数据库无需修改内核就能为新数据类型提供索引,是数据库可扩展性设计的经典范例。