GiST ( Eng. Generalized Search Tree , Generalized search tree) este o structură de index care este un tip generalizat de arbore Rși oferă metode standard pentru navigarea arborelui și actualizarea lui (diviziunea și ștergerea nodurilor). GiST este un arbore echilibrat (înălțime) ale cărui noduri finale (frunze) conțin perechi (key, rid), unde cheie este cheia și rid este un pointer către intrarea corespunzătoare din pagina de date. Nodurile interne conțin perechi (p, ptr), unde p este un predicat (utilizat ca o cheie de căutare) care rulează pe *toate* nodurile descendente, iar ptr este un pointer către un alt nod din arbore. Acest arbore definește metodele de bază SEARCH, INSERT, DELETE și o interfață pentru scrierea metodelor personalizate care pot controla funcționarea acestor metode (de bază).
Metoda SEARCH este controlată de funcția Consistent, care returnează „adevărat” dacă nodul satisface predicatul, metoda INSERT este controlată de funcțiile de penalizare, picksplit și unire, care ne permit să estimăm complexitatea operației de inserare în nod. , împărțiți nodul în caz de depășire și reconstruiți arborele dacă este necesar, metoda DELETE găsește o frunză a arborelui , care conține cheia, elimină perechea (key, rid) și, dacă este necesar, folosind funcția de unire, reconstruiește părintele noduri [1] .
GiST este un index direct utilizat de căutarea de text complet PostgreSQL . Aceasta înseamnă că pentru fiecare tsvector care descrie toate jetoanele din document, este creată o semnătură care descrie ce jetoane sunt incluse în acest tsvector. Principiul de funcționare este similar cu indicatorii de biți, dar există diferențe.
Să demonstrăm printr-un exemplu: fie jetonul w1 este asociat cu semnătura 001000, jetonul w2 - 000010. Apoi documentul care conține doar jetonele w1 și w2 va fi asociat cu semnătura 001010 (001000 | 000010). Spre deosebire de indexurile de biți, maparea token-urilor în semnături nu este unică, adică este posibilă existența unui token w3 cu semnătura 001000. Acest lucru permite economii semnificative la dimensiunea indexului, dar necesită o verificare secundară pentru o potrivire completă între jetoanele de interogare și document.
De asemenea, este de remarcat faptul că, dacă jetonul de cerere are o semnătură, de exemplu, 000001, atunci documentul cu semnătura 001010 cu siguranță nu o conține, în ciuda ambiguității mapării token-ului.
Avantajul GiST este viteza de creare și dimensiunea indexului în comparație cu GiN (de 3 ori), deci este de preferat pentru date actualizate dinamic în mod constant. Pentru date statice sau rar actualizate, este de preferat un index GiN (caută de 3 ori mai repede) [2] .