GiST ( Eng. Generalized Search Tree , Generalized search tree) är en indexstruktur som är en generaliserad sorts R-träd och tillhandahåller standardmetoder för att navigera i trädet och uppdatera det (dela och ta bort noder). GiST är ett balanserat (höjd)träd vars ändnoder (löv) innehåller par (nyckel, rid), där nyckel är nyckeln och rid är en pekare till motsvarande post på datasidan. De interna noderna innehåller (p, ptr) par, där p är något predikat (används som en uppslagsnyckel) som körs på *alla* avkomliga noder, och ptr är en pekare till en annan nod i trädet. Det här trädet definierar de grundläggande metoderna SÖK, INFOGA, DELETE och ett gränssnitt för att skriva anpassade metoder som kan styra driften av dessa (grundläggande) metoder.
SEARCH-metoden styrs av Consistent-funktionen, som returnerar "true" om noden uppfyller predikatet, INSERT-metoden styrs av penalty-, picksplit- och unionsfunktionerna, vilket gör att vi kan uppskatta komplexiteten av infogningsoperationen in i noden , dela noden i händelse av översvämning och bygg om trädet om det behövs, DELETE-metoden hittar ett blad av trädet , som innehåller nyckeln, tar bort paret (nyckel, red) och, om nödvändigt, med hjälp av unionsfunktionen, bygger om föräldern noder [1] .
GiST är ett direktindex som används av PostgreSQL fulltextsökning . Det betyder att för varje tsvector som beskriver alla tokens i dokumentet skapas en signatur som beskriver vilka tokens som ingår i denna tsvector. Funktionsprincipen liknar bitindex, men det finns skillnader.
Låt oss demonstrera med ett exempel: låt token w1 associeras med signaturen 001000, token w2 - 000010. Då kommer dokumentet som bara innehåller tokens w1 och w2 att associeras med signaturen 001010 (001000 | 000010). Till skillnad från bitindex är mappningen av tokens till signaturer inte unik, det vill säga förekomsten av en token w3 med signaturen 001000. Detta möjliggör betydande besparingar på indexets storlek, men kräver en sekundär kontroll för en fullständig matchning mellan fråge- och dokumenttoken.
Det är också värt att notera att om begäranstoken har en signatur, till exempel 000001, så innehåller dokumentet med signatur 001010 det definitivt inte, trots oklarheten i tokenmappning.
Fördelen med GiST är dess skapelsehastighet och indexstorlek jämfört med GiN (3 gånger), så det är att föredra för dynamiskt ständigt uppdaterad data. För statiska eller sällan uppdaterade data är ett GiN-index att föredra (det söker 3 gånger snabbare) [2] .