Postgres - статьи



              

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


Следует отметить, что первый рабочий прототип был реализован в СУБД Postgres Дж. Хеллерстейном и П. Аоки [GBK] и практические все коммерческие СУБД (IDS/UDO Virtual Index Interface, DB2 UDB table functions, Oracle Extensible Indexing Interface) тем или иным образом используют идеи и результаты этой исследовательской СУБД. Однако, в самом Postgres (PostgreSQL), GiST до 2000 года практически не развивался и не использовался. Более того, его реализация не поддерживала конкурентного доступа и восстановления после краха системы, что мешало его использования в промышленных системах.

Авторы этой статьи, при работе над порталом "Рамблер", начали использовать GiST и занялись исправлением ошибок и его улучшением. Так, авторы добавили поддержку ключей переменной длины, композитных ключей (multi-key), оптимизировали алгоритм вставки (однопроходный вместо рекурсивного). Кроме того, для версии 8.1 авторы добавили поддержку конкурентного доступа к GiST индексам и восстановление после краха системы, используя модифицированные алгоритмы из работы Корнакера и др. [KMH97], что окончательно сняло все ограничения, мешающие использование его в сильно нагруженных системах и работе с критическими данными. Отметим, что большое количество модулей, написанных на базе GiST, автоматически "приобрели" всю эту индустриальную мощь без какого-либо изменения !

GiST представляет собой сбалансированное (по высоте) дерево, концевые узлы (листья) которого содержат пары (key, rid), где key - ключ, а rid - указатель на соответствующую запись на странице данных. Внутренние узлы содержат пары (p,ptr), где p - это некий предикат (используется как поисковый ключ), выполняющийся для *всех* наследных узлов, а ptr - указатель на другой узел в дереве.

Для этого дерева определены базовые методы SEARCH, INSERT, DELETE, и интерфейс для написания пользовательских методов, которыми можно управлять работой этих (базовых) методов.

Метод SEARCH управляется функцией Consistent, возвращающая 'true', если узел удовлетворяет предикату, метод INSERT - функциями penalty, picksplit и union, которые позволяют оценить сложность операции вставки в узел, разделить узел при переполнении и перестроить дерево при необходимости, метод DELETE находит лист дерева, содержащий ключ, удаляет пару (key, rid) и, если нужно, с помощью функции union перестраивает родительские узлы.




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