При построении современных информационных систем
При построении современных информационных систем приходится решать разнообразные технологические задачи, связанные с хранением, доступом и поиском информации. Учитывая современные требования к производительности, надежности и шкалированию таких систем, такие задачи требуют использования достаточно сложных алгоритмов и специализированных структур данных (abstract data type, ADT).
Эффективный доступ к данным является одной из важнейшей задачей базы данных. Мы рассматриваем большие базы данных, которые не помещаются в оперативную память. Для таких БД эффективность доступа к данным определяется, в основном, количеством обращений к диску, поэтому основной задачей СУБД является минимизация этих обращений. Обычно, это достигается использованием индекса, который представляет собой вспомогательную структуру данных, предназначенную для ускорения получения данных удовлетворяющих определенным поисковым критериям. Индекс позволяет уменьшить количество дисковых операций необходимых для считывания данных с диска. Обычно, индекс представляет собой файл на диске, и, если этот файл становится очень большим, то может потребоваться дополнительный индекс для ускорения работы самого индекса. Методами доступа (access methods,AM), обычно, называют организацию (структуру) индексного файла и методы работы с ней. В традиционных реляционных СУБД для работы с одномерными данными, такими как строки, цифры, используются B+-tree и хэш, для которых разработаны очень эффективные алгоритмы работы. Однако, современные приложения, такие как ГИС (GIS), мультимедийные системы, CAD, цифровые библиотеки, которые по-сути используют многомерные данные, требуют других, более эффективных AM. Например, в ГИС основными типами данных являются точки, линии, полигоны. За последние годы было разработано десятки (около 70) различных специализированных AM, однако их реализация в серьезных СУБД связана с большими затратами из-за собственно программирования AM и обеспечения соответствующего уровня надежности, конкурентности, предоставляемых СУБД для обычных AM. Следует отметить, что для этого требуется работа очень квалифицированных программистов, знакомых с ядром СУБД, а также, тщательное и продолжительное тестирование.
Вместо написания новых 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.
Следует отметить, что первый рабочий прототип был реализован в СУБД 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 перестраивает родительские узлы.
