Postgres - статьи




Введение - часть 2


Вместо написания новых AM для каждого нового типа данных, Майкл Стоунбрейкер [Sto86] предложил использовать существующие, хорошо изученные структуры, такие как B+-tree и R-tree. Эта идея нашла воплощение в СУБД Postgres, развиваемой в Беркли в 80-х годах (см. детали в [B05]). Идея Стоунбрейкера заключалась в повышении степени абстракции процедур доступа и обновления записей, которые и составляют АМ. Так, например, достаточно определить операторы сравнения, чтобы использовать B+-tree AM. На примере типа данных box Стоунбрейкер показал, как B+-tree можно использовать для операций AE (равенство), AL (меньше) и AG (больше). Однако, такой подход, несмотря на свои возможности, сильно ограничен, так как несмотря на тип данных, который хранится в B+-tree, нельзя использовать запросы кроме тех, которые предоставляет B+tree. Другими словами, этот подход поддерживал расширяемость типов, но не запросов и методов доступа.

Для того, чтобы преодолеть это ограничение, Hellerstein et al. [HNP95] предложили структуру индекса, называемую GiST ( Generalized Search Tree, Обобщенное поисковое дерево), которое является обобщенной разновидностью R-tree и предоставляет стандартные методы навигации по дереву и его обновления (расщепление и удаление узлов). Было отмечено, что очень многие AM можно представить как иерархию предикатов, в которой каждый предикат выполняется для всех ключей, содержащихся в подузлах этой иерархии. Таким образом, такая структура данных может служить шаблоном для реализации многих AM, не накладывая существенных ограничений. Например, в B+-tree записи во внутренних узлах представляют диапазоны, которые задают ограничения на ключи в концевых узлах соответствующего поддерева. GiST предоставляет индексный доступ к новым типам данным и поддерживает расширяемый набор запросов. Это позволяет разрабатывать расширения экспертам в области данных, не будучи экспертами-разработчиками ядра СУБД. Кроме этого, эти новые ADT автоматически наследуют конкурентный доступ и восстановление после краха (concurrency and recovery), реализация которых с нуля, является очень большой задачей, предоставленные ядром GiST.




Содержание  Назад  Вперед