GiST ( anglicky Generalized Search Tree , Generalized Search Tree) je indexová struktura, která je zobecněným druhem R-stromu a poskytuje standardní metody pro navigaci ve stromu a jeho aktualizaci (rozdělování a mazání uzlů). GiST je vyvážený (výška) strom, jehož koncové uzly (listy) obsahují dvojice (klíč, rid), kde klíč je klíč a rid je ukazatel na odpovídající položku na datové stránce. Vnitřní uzly obsahují páry (p, ptr), kde p je nějaký predikát (používaný jako vyhledávací klíč), který běží na *všech* podřízených uzlech, a ptr je ukazatel na jiný uzel ve stromu. Tento strom definuje základní metody SEARCH, INSERT, DELETE a rozhraní pro psaní vlastních metod, které mohou ovládat činnost těchto (základních) metod.
Metoda SEARCH je řízena funkcí Consistent, která vrací 'true', pokud uzel vyhovuje predikátu, metoda INSERT je řízena funkcemi penalty, picksplit a union, které nám umožňují odhadnout složitost operace vložení do uzlu. , rozdělit uzel v případě přetečení a v případě potřeby strom znovu sestavit, metoda DELETE najde list stromu obsahující klíč, odstraní pár (klíč, zbavit) a v případě potřeby pomocí funkce union znovu sestaví rodiče uzly [1] .
GiST je přímý index používaný fulltextovým vyhledáváním PostgreSQL . To znamená, že pro každý tsvector, který popisuje všechny tokeny v dokumentu, je vytvořen podpis, který popisuje, které tokeny jsou zahrnuty v tomto tsvector. Princip fungování je podobný bitovým indexům, ale existují rozdíly.
Ukažme si to na příkladu: nechť je token w1 spojen s podpisem 001000, token w2 - 000010. Pak bude dokument obsahující pouze tokeny w1 a w2 spojen s podpisem 001010 (001000 | 000010). Na rozdíl od bitových indexů není mapování tokenů na signatury jedinečné, to znamená, že je možná existence tokenu w3 s podpisem 001000. To umožňuje značné úspory na velikosti indexu, ale vyžaduje sekundární kontrolu úplné shody mezi tokeny dotazů a dokumentů.
Za zmínku také stojí, že pokud má token požadavku podpis, například 000001, pak ho dokument s podpisem 001010 rozhodně neobsahuje, a to i přes nejednoznačnost mapování tokenů.
Výhodou GiST je rychlost tvorby a velikost indexu ve srovnání s GiN (3x), takže je výhodnější pro dynamicky neustále aktualizovaná data. Pro statická nebo zřídka aktualizovaná data je výhodnější GiN index (vyhledává 3x rychleji) [2] .