In informatica, GiST (Generalized Search Tree) o Albero di ricerca generalizzato, è una struttura dati e API che può essere usato per costruire una varietà alberi di ricerca basati sul disco.
GiST è una generalizzazione degli alberi B+, che fornisce una infrastruttura ad albero di ricerca concorrente e altamente bilanciata per il recupero senza compiere alcuna assunzione sul tipo di dato archiviato o la tipologia di interrogazioni. Può essere implementato facilmente in una serie di indici ben conosciuti, inclusi alberi B+, alberi R, alberi hB, alberi RD e molti altri; permette anche lo sviluppo di indici specializzati per nuovi tipi di dato.
Non può essere usato direttamente per implementare alberi non altamente bilanciati come Quadtree alberi a prefisso (prefix tree), sebbene come gli alberi a prefisso supporti la compressione, compresa quella con perdita. GiST può essere usato con tutti i tipi di dato che sono ordinati naturalmente in una gerarchia di superset (superinsiemi). La più utilizzata implementazione di GiST è nel gestore di basi di dati relazionali PostgreSQL, ma anche nell'Informix Universal Server, e come libreria libgist.
Voci correlate
Collegamenti esterni
