В чем разница между методами индексации B-Tree и GiST (в PostgreSQL)?

Question

Я недавно работал над оптимизацией своих баз данных Postgres, и традиционно я использую только индексы B-Tree. Однако я видел, что индексы GiST поддерживают неуникальные многоколоночные индексы в документации Postgres 8.3.

Я не мог, однако, увидеть, в чем же разница между ними. Я надеялся, что мои коллеги-кодеры смогут объяснить, каковы плюсы и минусы между ними и, что более важно, причины, по которым я бы использовал один над другим?

Answer 1

В двух словах: индексы B-Tree работают лучше, но индексы GiST более гибкие. Обычно вам нужны индексы B-Tree, если они будут работать для вашего типа данных. В списках PG недавно появилось сообщение об огромном падении производительности при использовании индексов GiST; ожидается, что они будут медленнее, чем B-Trees (такова цена гибкости), но не , что намного медленнее ... работа, как вы можете ожидать, продолжается.

С пост Тома Лейна , основного разработчика PostgreSQL:

Суть GIST в том, чтобы иметь возможность индексировать запросы, которые просто не индексируется в btree. ... можно было бы полностью ожидать, что btree превзойдет GIST для btree-indexable случаев. я думаю Важным моментом здесь является то, что он выигрывает в пару раз сто; это довольно ужасно, и может указывать на некоторую реализацию проблема.

Answer 2

В принципе, все правы - btree является индексом по умолчанию, поскольку он работает очень хорошо. GiST - это несколько разные звери - это скорее «основа для написания типов индексов», чем сам по себе тип индекса. Вы должны добавить пользовательский код (на сервере), чтобы использовать его, но с другой стороны - они очень гибкие.

Обычно - вы не используете GiST, если только тип данных, который вы используете, не говорит вам об этом. Пример типов данных, которые используют GiST: ltree (из contrib), tsvector (contrib / tsearch до 8.2, в ядре начиная с 8.3) и другие.

Существует хорошо известное и довольно быстрое географическое расширение PostgreSQL - PostGIS (http://postgis.refractions.net/), которое использует GiST для своих целей.

Answer 3

GiST-индексы в некоторой степени являются потерями, а это означает, что СУБД должна иметь дело с ложными положительными / отрицательными значениями, т. Е .:

GiST индексы с потерями, потому что каждый документ представлен в индексе фиксированной длина подписи. Подпись генерируется путем хеширования каждого слова в случайный бит в n-битной строке, с все эти биты ИЛИ вместе с создать n-битную подпись документа. Когда два слова хешируют в один бит положение там будет ложное совпадение. Если все слова в запросе имеют совпадения (реальное или ложное), то строка таблицы должен быть найден, чтобы увидеть, если совпадение верно. b-деревья не имеют такого поведения, поэтому в зависимости от индексируемых данных между ними может быть некоторая разница в производительности.

См. Для поведения текстового поиска http://www.postgresql.org/docs/8.3/static/textsearch-indexes.html и http://www.postgresql.org/docs/8.3/static/indexes-types.html для сравнения общего назначения.

Answer 4

GiST являются более общими показателями. Вы можете использовать их для более широких целей, чем те, которые вы бы использовали с B-Tree. Включая возможность построения B-дерева с использованием GiST.

IE: вы можете использовать GiST для индексации по географическим точкам или географическим областям, что вы не сможете сделать с индексами B-Tree, поскольку единственное, что имеет значение для B-Tree, это ключ (или ключи) вы индексируете.