Qual é a diferença entre os métodos de índice GiST (no PostgreSQL) B-Tree e?

Question

Tenho vindo a trabalhar na otimização de meus bancos de dados PostgreSQL recentemente, e tradicionalmente, eu só nunca usar índices B-tree. No entanto, eu vi que os índices GiST suport não-exclusivas, índices de várias colunas, na documentação do PostgreSQL 8.3.

Eu não poderia, no entanto, ver o que a diferença real entre eles é. Eu estava esperando que meus companheiros codificadores pode beable para explicar, o que os prós e contras entre eles são, e mais importante, as razões pelas quais eu usaria um sobre o outro?

Answer 1

Em poucas palavras: índices B-tree um melhor desempenho, mas os índices GiST são mais flexíveis. Normalmente, você quer índices de árvore B se eles vão trabalhar para o seu tipo de dados. Houve um post recente sobre as listas de PG cerca de um desempenho enorme sucesso para a utilização de índices GiST; que é esperado para ser mais lento do B-Trees (tal é o preço de flexibilidade), mas não que muito mais lento ... trabalho é, como se poderia esperar, em curso.

A partir um post por Tom Lane, , um núcleo PostgreSQL desenvolvedor:

O ponto principal de GIST é ser capaz de consultas de índice que são simplesmente Não indexável em btree. ... seria totalmente esperar btree para bater para fora GIST para casos btree-indexáveis. Eu acho que o ponto importante aqui é que está a ganhar por um fator de um casal cem; isso é muito horrível, e pode apontar para alguns implementação problema.

Answer 2

Basicamente todo mundo certo - btree é índice de inadimplência como ele executa muito bem. GiST são um pouco diferentes animais - é mais um "framework para tipos de índices de gravação" do que um tipo de índice por conta própria. Você tem que adicionar código personalizado (no servidor) para usá-lo, mas por outro lado -. Eles são muito flexíveis

Geralmente - você não usar GiST a menos que o tipo de dados que você está usando dizer-lhe para fazê-lo. Exemplo de tipos de dados que o uso GiST:. Ltree (a partir de Contr), tsvector (Contr / tsearch até 8,2, no núcleo desde 8,3), e outros

Não é bem conhecido, e extenstion muito rápido geográfica para PostgreSQL - PostGIS ( http://postgis.refractions.net/ ) que utiliza GiST para seus propósitos.

Answer 3

índices GiST são com perdas até certo ponto, o que significa que o DBMS tem de lidar com positivos falsos / negativos, ou seja:.

índices GiST são lossy porque cada documento é representado no índice por um fixo assinatura comprimento. A assinatura é gerado por hashing cada palavra em um aleatória de bits em uma cadeia de n-bit, sendo todos estes bits de OU-ed juntos para produzir uma assinatura de documento n-bit. Quando duas palavras de hash para o mesmo bit posição, haverá uma falsa partida. Se todas as palavras na consulta têm partidas em seguida, a linha da tabela (real ou falso) devem ser recuperados para ver se o jogo está correto. b-árvores não têm este comportamento, de modo acordo com os dados que estão sendo indexados, pode haver alguma diferença de desempenho entre os dois.

Veja por comportamento de busca de texto http: //www.postgresql. org / docs / 8.3 / static / TextSearch-indexes.html e http://www.postgresql.org/docs/8.3/static/indexes-types.html para uma comparação de propósito geral.

Answer 4

GiST são índices mais gerais. Você pode usá-los para fins mais amplos que os que você usaria com B-Tree. Incluindo a capacidade de construir um B-Tree usando GIST.

IE: você pode usar GiST para o índice em pontos geográficos ou áreas geográficas, algo que você não será capaz de fazer com índices B-tree, já que a única coisa que importa em um B-Tree é a chave (ou chaves) está a indexar por diante.