В вычислениях GiST или Generalized Search Tree - это структура данных и API, которые могут использоваться для построения множества дисковых деревьев поиска . GiST - это обобщение дерева B + , обеспечивающее параллельную и восстанавливаемую инфраструктуру дерева поиска со сбалансированной высотой без каких-либо предположений о типе хранимых данных или обслуживаемых запросах. GiST можно использовать для простой реализации ряда хорошо известных индексов, включая B + деревья , R-деревья , hB-деревья , RD-деревья., и много других; он также позволяет легко разрабатывать специализированные индексы для новых типов данных. Его нельзя использовать напрямую для реализации деревьев без балансировки по высоте, таких как деревья квадратов или деревья префиксов (попытки), хотя, как и деревья префиксов, он поддерживает сжатие, включая сжатие с потерями . GiST может использоваться для любого типа данных, который может быть естественным образом упорядочен в иерархию надмножеств . Оно не только расширяемо с точки зрения поддержки типов данных и древовидной структуры, но и позволяет автору расширения поддерживать любые предикаты запроса, которые они выбирают.
GiST является примером расширяемости программного обеспечения в контексте систем баз данных: он позволяет легко развить систему баз данных для поддержки новых индексов на основе дерева. Это достигается за счет отделения своей базовой системной инфраструктуры от узкого API , которого достаточно для захвата специфических для приложений аспектов широкого спектра конструкций индексов. Код инфраструктуры GiST управляет компоновкой страниц индекса на диске, алгоритмами поиска в индексах и удалением из индексов, а также сложными деталями транзакций, такими как блокировка на уровне страницы для высокого уровня параллелизма и ведение журнала упреждающей записи для восстановления после сбоя. Это позволяет авторам новых индексов на основе дерева сосредоточиться на реализации новых функций нового типа индекса - например, способе описания подмножеств данных для поиска - не становясь экспертами по внутреннему устройству системы баз данных.
Хотя изначально GiST был разработан для ответов на логические запросы выбора, он также может поддерживать поиск ближайшего соседа и различные формы статистической аппроксимации для больших наборов данных.
Реализации
Наиболее широко используемая реализация GiST находится в реляционной базе данных PostgreSQL ; он также был реализован в Informix Universal Server и как отдельная библиотека libgist.
PostgreSQL
Реализация PostgreSQL GiST включает поддержку ключей переменной длины, составных ключей, управление параллелизмом и восстановление; эти функции наследуются всеми расширениями GiST. Есть несколько дополнительных модулей, разработанных с использованием GiST и распространяемых с PostgreSQL. Например:
- rtree_gist, btree_gist - GiST реализация R-дерева и B-дерева
- intarray - поддержка индекса для одномерного массива int4
- tsearch2 - доступный для поиска (полнотекстовый) тип данных с индексированным доступом
- ltree - типы данных, индексированные методы доступа и запросы для данных, организованных в виде древовидных структур
- hstore - хранилище для (ключа, значения) данных
- cube - тип данных, представляющий многомерные кубы
Реализация PostgreSQL GiST обеспечивает поддержку индексирования для PostGIS ( географическая информационная система ) и биоинформатической системы BioPostgres .
Рекомендации
- Джозеф М. Хеллерштейн , Джеффри Ф. Нотон и Ави Пфеффер. Обобщенные деревья поиска для систем баз данных . Proc. 21-я Международная конф. по очень большим базам данных, Цюрих, сентябрь 1995 г., стр. 562–573.
- Марсель Корнакер, К. Мохан и Джозеф М. Хеллерстайн. Параллелизм и восстановление в обобщенных деревьях поиска . Proc. ACM SIGMOD Conf. по управлению данными, Тусон, Аризона, май 1997 г., стр. 62–72.
- Пол М. Аоки. Обобщение «поиска» в обобщенных деревьях поиска . Proc. 14-я Международная конференция on Data Engineering, Орландо, Флорида, февраль 1998 г., стр. 380–389.
- Марсель Корнакер. Высокопроизводительные обобщенные деревья поиска , Proc. 24-я Международная конференция on Very Large Data Bases, Эдинбург, Шотландия, сентябрь 1999 г.
- Пол М. Аоки. Как избежать создания DataBlades, которые знают ценность всего и ничего не стоят, Proc. 11-я Международная конф. по управлению научными и статистическими базами данных, Кливленд, Огайо, июль 1999 г., стр. 122–133.
Внешние ссылки
- Сайт исследовательского проекта GiST
- Разработка PostgreSQL GiST
- Документация по поддержке GiST в PostgreSQL
- Разработка расширения PostgreSQL с помощью GiST (на русском языке)
- GiST в вики PostgreSQL
- PostGIS
- BioPostgres