Введение

SP-GiST – это аббревиатура от Space-Partitioned GiST (GiST с секционированием пространства). SP-GiST поддерживает разбитые деревья поиска, что облегчает разработку широкого спектра различных несбалансированных структур данных, таких как квадродеревья, k-d-деревья и радиксные деревья (tries). Общая особенность этих структур заключается в том, что они многократно делят пространство поиска на разделы, которые не обязательно должны быть одинакового размера. Поиск, хорошо согласованный с правилом разбиения, может быть очень быстрым.

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

Как и GiST, SP-GiST предназначен для разработки пользовательских типов данных с соответствующими методами доступа экспертом в области типа данных, а не экспертом по базам данных.

Часть информации здесь взята с сайта проекта индексирования SP-GiST Университета Пердью. Реализация SP-GiST в PostgreSQL в основном поддерживается Федором Сигаевым и Олегом Бартуновым, и более подробная информация есть на их сайте.