Qual è la differenza tra i metodi di indice B-Tree e GiST (in PostgreSQL)?

Question

Ho lavorato di recente sull'ottimizzazione dei miei database Postgres e, tradizionalmente, ho sempre usato solo gli indici B-Tree. Tuttavia, ho visto che GiST indicizza suport non univoci, gli indici multicolore, nella documentazione di Postgres 8.3.

Non ho potuto, tuttavia, vedere quale sia la differenza effettiva tra loro. Speravo che i miei colleghi programmatori potessero spiegare, quali sono i pro e i contro tra loro e, cosa ancora più importante, i motivi per cui userei l'uno sull'altro?

Answer 1

In breve: gli indici B-Tree funzionano meglio, ma gli indici GiST sono più flessibili. Di solito, vuoi gli indici B-Tree se funzioneranno per il tuo tipo di dati. C'era un recente post sugli elenchi PG di un enorme successo in termini di prestazioni per l'utilizzo degli indici GiST; dovrebbero essere più lenti di B-Trees (tale è il prezzo della flessibilità), ma non che molto più lento ... il lavoro è, come ci si potrebbe aspettare, in corso.

Da a post by Tom Lane, un nucleo PostgreSQL sviluppatore:

Il punto principale di GIST è quello di essere in grado di query indice che semplicemente sono non indicizzabile in btree. ... Uno sarebbe completamente aspettarsi btree per battere GIST per casi indicizzabili btree. Penso che il punto significativo qui è che sta vincendo da un fattore di una coppia centinaia; è abbastanza orribile, e potrebbe indicare qualche problema di implementazione .

Answer 2

indici GiST sono lossy in una misura, il che significa che il DBMS deve affrontare falsi positivi/negativi, cioè:

indici GiST sono lossy perché ogni documento è rappresentato nell'indice da un fisso firma della lunghezza. La firma è generata da hashing di ogni parola in un bit casuale in una stringa n bit, con tutti questi bit OR-ed insieme a producono una firma di documento n bit. Quando hash di due parole sulla stessa posizione di bit ci sarà una corrispondenza falsa. Se tutte le parole nella query corrispondono a (reale o falso), è necessario recuperare la riga della tabella per verificare se la corrispondenza è corretta. b-tree non hanno questo comportamento, quindi, a seconda dei dati da indicizzare, potrebbe esserci qualche differenza di prestazioni tra i due.

Vedi per il comportamento di ricerca del testo http://www.postgresql.org/docs/8.3/static/textsearch-indexes.html e http://www.postgresql.org/docs/8.3/static/indexes-types.html per un confronto di uso generale.

Answer 3

GiST sono indici più generali. Puoi usarli per scopi più ampi di quelli che useresti con B-Tree. Compresa la possibilità di costruire un B-Tree usando GiST.

IE: puoi usare GiST per indicizzare su punti geografici o aree geografiche, qualcosa che non sarai in grado di fare con gli indici B-Tree, poiché l'unica cosa che importa su B-Tree è la chiave (o chiavi) su cui stai indicizzando.

Answer 4

Fondamentalmente tutti hanno ragione: btree è l'indice predefinito in quanto funziona molto bene. Le GiST sono animali alquanto diversi: è più un "framework per scrivere i tipi di indice" che un tipo di indice a sé stante. Devi aggiungere codice personalizzato (nel server) per usarlo, ma d'altra parte - sono molto flessibili.

In genere, non si utilizza GiST a meno che il tipo di dati che si sta utilizzando non indichi di farlo. Esempio di tipi di dati che utilizzano GiST: ltree (da contrib), tsvector (contrib/tsearch fino a 8.2, in core da 8.3) e altri.

C'è un'estensione geografica ben nota e piuttosto veloce a PostgreSQL - PostGIS (http://postgis.refractions.net/) che usa GiST per i suoi scopi.