Обобщенное древо поиска GiST: структура данных и API для индексирования.

Введение

В вычислительной технике, GiST (Generalized Search Tree) или обобщённое дерево поиска, — это структура данных и API, которые можно использовать для создания различных дисковых деревьев поиска. GiST является обобщением B+-дерева, предоставляющего конкурентную и восстанавливаемую, сбалансированную по высоте инфраструктуру дерева поиска, не делая никаких предположений о типе хранимых данных или обрабатываемых запросах. GiST может быть использован для простой реализации широкого спектра известных индексов, включая B+-деревья, R-деревья, hB-деревья, RD-деревья и многие другие; он также позволяет легко разрабатывать специализированные индексы для новых типов данных. Он не может быть использован напрямую для реализации несбалансированных по высоте деревьев, таких как квадродеревья или префиксные деревья (три), хотя, как и префиксные деревья, он поддерживает сжатие, включая сжатие с потерями. GiST может использоваться для любого типа данных, который можно естественным образом упорядочить в иерархию супермножеств. Он расширяем не только в отношении поддержки типов данных и структуры дерева, но и позволяет разработчику расширения поддерживать любые выбранные им предикаты запросов. GiST является примером расширяемости программного обеспечения в контексте систем баз данных: он позволяет легко развивать систему баз данных для поддержки новых индексов, основанных на деревьях. Это достигается за счёт отделения основной инфраструктуры системы от узкого API, достаточного для охвата специфических аспектов применения широкого спектра конструкций индексов. Код инфраструктуры GiST управляет структурой индексных страниц на диске, алгоритмами поиска и удаления из индексов, а также сложными деталями транзакций, такими как блокировка на уровне страниц для обеспечения высокой конкуренции и предварительная запись журнала для восстановления после сбоев. Это позволяет авторам новых индексов, основанных на деревьях, сосредоточиться на реализации новых функций нового типа индекса — например, способа описания подмножеств данных для поиска — без необходимости становиться экспертами во внутреннем устройстве систем баз данных. Хотя изначально GiST был разработан для ответа на булевы запросы отбора, он также может поддерживать поиск ближайших соседей и различные формы статистического приближения для больших наборов данных.

In computing, GiST or Generalized Search Tree, is a data structure and API that can be used to build a variety of disk based search trees. GiST is a generalization of the B+ tree, providing a concurrent and recoverable height balanced search tree infrastructure without making any assumptions about the type of data being stored, or the queries being serviced. GiST can be used to easily implement a range of well known indexes, including B+ trees, R trees, hB trees, RD trees, and many others; it also allows for easy development of specialized indexes for new data types. It cannot be used directly to implement non height balanced trees such as quad trees or prefix trees (tries), though like prefix trees it does support compression, including lossy compression. GiST can be used for any data type that can be naturally ordered into a hierarchy of supersets. Not only is it extensible in terms of data type support and tree layout, it allows the extension writer to support any query predicates that they choose. GiST is an example of software extensibility in the context of database systems: it allows the easy evolution of a database system to support new tree based indexes. It achieves this by factoring out its core system infrastructure from a narrow API that is sufficient to capture the application specific aspects of a wide variety of index designs. The GiST infrastructure code manages the layout of the index pages on disk, the algorithms for searching indexes and deleting from indexes, and complex transactional details such as page level locking for high concurrency and write ahead logging for crash recovery. This allows authors of new tree based indexes to focus on implementing the novel features of the new index type — for example, the way in which subsets of the data should be described for search — without becoming experts in database system internals. Although originally designed for answering Boolean selection queries, GiST can also support nearest neighbor search, and various forms of statistical approximation over large data sets.

Реализация

Наиболее широко используемая реализация GiST присутствует в реляционной базе данных PostgreSQL; она также была реализована в Informix Universal Server и в виде автономной библиотеки libgist.