Суть

В вычислительной технике GiST или обобщенное дерево поиска — это структура данных и 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 — хранилище данных (ключ, значение)
• куб — ​​тип данных, представляющий многомерные кубы

Реализация PostgreSQL GiST обеспечивает поддержку индексации для PostGIS ( географической информационной системы системы BioPostgres ) и биоинформатической .

Ссылки

• Джозеф М. Хеллерстайн , Джеффри Ф. Нотон и Ави Пфеффер. Обобщенные деревья поиска для систем баз данных . Учеб. 21-я Международная конференция. по очень большим базам данных, Цюрих, сентябрь 1995 г., стр. 562–573.
• Марсель Корнакер, К. Мохан и Джозеф М. Хеллерстайн. Параллелизм и восстановление в обобщенных деревьях поиска . Учеб. Конференция ACM SIGMOD. по управлению данными, Тусон, Аризона, май 1997 г., стр. 62–72.
• Пол М. Аоки. Обобщение «поиска» в обобщенных деревьях поиска . Учеб. 14-я Международная конференция. по инженерии данных, Орландо, Флорида, февраль 1998 г., 380–389.
• Марсель Корнакер. Высокопроизводительные обобщенные деревья поиска , Учеб. 24-я Международная конференция. по очень большим базам данных, Эдинбург, Шотландия, сентябрь 1999 г.
• Пол М. Аоки. Как избежать создания блейдов данных, которые знают ценность всего и ничего не стоят , Proc. 11-я Международная конференция. по управлению научными и статистическими базами данных, Кливленд, Огайо, июль 1999 г., стр. 122–133.

Внешние ссылки

• Сайт исследовательского проекта GiST
• Разработка PostgreSQL GiST
• Документация по поддержке GiST в PostgreSQL
• Разработка расширения PostgreSQL с помощью GiST (на русском языке)
• GiST в вики PostgreSQL
• ПостГИС
• БиоПостгрес