¿Cuál es la diferencia entre los métodos de índice B-Tree y GiST (en PostgreSQL)?

Question

He estado trabajando en la optimización de mis bases de datos Postgres recientemente, y tradicionalmente, solo he usado índices de B-Tree. Sin embargo, vi que los índices GiST soportan índices multicolumna no únicos en la documentación de Postgres 8.3.

No pude, sin embargo, ver cuál es la diferencia real entre ellos. Tenía la esperanza de que mis compañeros codificadores pudieran explicar, cuáles eran los pros y los contras entre ellos, y más importante, las razones por las cuales usaría uno sobre el otro.

Answer 1

En pocas palabras: los índices B-Tree funcionan mejor, pero los índices GiST son más flexibles. Por lo general, quiere índices B-Tree si funcionan para su tipo de datos. Hubo una publicación reciente en las listas de PG sobre un gran impacto en el rendimiento por usar índices GiST; se espera que sean más lentos que B-Trees (tal es el precio de la flexibilidad), pero no que mucho más lento ... el trabajo es, como era de esperar, en curso.

De a post by Tom Lane, un núcleo de desarrolladores de PostgreSQL:

El punto principal de los GIST es ser capaz de consultas de índice que simplemente son no indexable en árbolB. ... Se podría esperar por completo para vencer a GIST en los casos de indexación btree. Creo que el punto significativo de aquí es que está ganando por un factor de un par cien; eso es bastante horrible, y podría apuntar a algún problema de implementación .

Answer 2

índices TEGI son con pérdida a un grado, lo que significa que el DBMS tiene que lidiar con falsos positivos/negativos, es decir:

índices TEGI son con pérdidas porque cada documento está representado en el índice por un fijo firma de longitud La firma es generada al mezclar cada palabra en un bit aleatorio en una cadena de n bits, con todos estos bits OR-ed juntos en producen una firma de documento de n bits. Cuando dos palabras hash al mismo bit posición habrá una coincidencia falsa. Si todas las palabras de la consulta tienen coincidencias (real o falsa), debe recuperarse la fila de la tabla para ver si la coincidencia es correcta. b-trees no tienen este comportamiento, por lo que dependiendo de los datos indexados, puede haber alguna diferencia de rendimiento entre los dos.

Véase, por el comportamiento de búsqueda de texto y http://www.postgresql.org/docs/8.3/static/textsearch-indexes.htmlhttp://www.postgresql.org/docs/8.3/static/indexes-types.html para una comparación de propósito general.

Answer 3

GiST son índices más generales. Puede usarlos para fines más amplios que los que usaría con B-Tree. Incluyendo la capacidad de construir un B-Tree usando GiST.

IE: puede usar GiST para indexar puntos geográficos o áreas geográficas, algo que no podrá hacer con los índices de B-Tree, ya que lo único que importa en un B-Tree es la clave (o claves) en las que está indexando.

Answer 4

Básicamente todo el mundo está bien - btree es el índice predeterminado, ya que funciona muy bien. GiST son bestias algo diferentes: es más un "marco para escribir tipos de índice" que un tipo de índice en sí mismo. Tienes que agregar un código personalizado (en el servidor) para usarlo, pero por otro lado, son muy flexibles.

En general, no utiliza GiST a menos que el tipo de datos que está utilizando le indique que lo haga. Ejemplo de tipos de datos que usan GiST: ltree (de contrib), tsvector (contrib/tsearch hasta 8.2, en core desde 8.3) y otros.

Existe una extensión geográfica bien conocida y bastante rápida para PostgreSQL - PostGIS (http://postgis.refractions.net/) que usa GiST para sus propósitos.