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

Question

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

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

Answer 1

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

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

Суть суть в том, чтобы иметь возможность индексировать поисковым что просто не индексируемый в дерево....Можно было бы полностью ожидать дерево, чтобы выбить суть для дерево-режущих случаях.Я думаю, что важным моментом здесь является то, что он выигрывает с коэффициентом в пару сотен;это довольно ужасно и может указывать на некоторую проблему с реализацией .

Answer 2

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

Как правило, вы не используете 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

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

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