![[Home]](/~megera/oddmuse/zen3.gif)
|
Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://www.sai.msu.su/~megera/wiki/Diglib_data_types
Дата изменения: Unknown Дата индексирования: Sun Apr 10 20:29:39 2016 Кодировка: UTF-8 |
О.С. Бартунов, Ф.Г. Сигаев
При построении современных информационных систем приходится решать разнообразные технологические задачи, связанные с хранением, доступом и поиском информации. Учитывая современные требования к производительности, надежности и шкалированию таких систем, такие задачи требуют использования достаточно сложных алгоритмов и специализированных структур данных.
В процессе работы над многими проектами такими как портал "Рамблер", федеральные порталы министерства образования, проект "Астронет" (1), "Все о Геологии" (2), "Научная Сеть" (3), авторы сталкивались с нестандартными задачами, решение которых требовало разработки новых типов данных и методов доступа к ним. В качестве БД использовалась свободно-распространяемая СУБД PostgreSQL (4), поддерживающая разработку новых типов данных. Эта база данных удовлетворяет всем практическим требованиям к современным хранилищам цифровых библиотек, активно развивается и поддерживается.
Для того, чтобы упростить процесс разработки новых типов в PostgreSQL используется GiST (5) (Обобщенное поисковое дерево), впервые предложенное проф. Хеллерстейном и др. из Беркли, и которое в дальнейшем поддерживается и развивается (6,10) авторами этой статьи. GiST автоматически предоставляет индексный доступ, конкурентность и восстановление после сбоев. В дополнение к GiST, мы разработали обобщенный обратный индекс (GIN) (7,8) , который также используется для индексной поддержки. Отметим, что все расширения являются конкурентными и поддерживают восстановление после сбоев.
Все модули распространяются с PostgreSQL и активно используются как в наших проектах, так и во многих других. Перечислим самые популярные модули и расширения, разработанные авторами при частичной поддержки РФФИ.
Этот модуль часто используется в тех случаях, когда требуется денормализовать БД для повышения производительности. Например, типичная задача построения списка документов из нескольких разделов. Классическая нормализованная схема предусматривает использование трех таблиц - messages, sections и message_section_map, которя содержит связи многие-ко-многим. Построение такого списка требует двух таблиц messages и message_section_map, что влияет на производительность и в некоторых случаях просто неприемлемо. Денормализация приводит к тому, что в таблицу messages добавляется поле sections, которое является массивом целых чисел - идентификаторов секций, к которым принадлежит данный документ. Однако, поиск будет все равно медленным из-за того, что операция "поиск в массиве" не использует индекс. Модуль intarray обеспечивает индексную поддержку для операций над целочисленными массивами - overlap, contains, contained и ряд дополнительных операторов и функций. Индексная поддержка использует разновидность RD-Tree (Russian Doll Tree)(9), реализованная с помощью GiST. Начиная с версии 8.2 можно использовать обратный индекс (GIN), который шкалируется лучше и предпочтителен для статических данных.
Добавляет тип, поддерживающий хранение деревообразных данных и их индексную поддержку с помощью GiST и B-Tree. Такие данные типичны для работы с каталогами, рубрикаторами. Стандартный способ работы с иерархическими данными, например, с каталогами, заключается в использовании таблиц связей (parent_id,child_id), что приводит ,так или иначе, к необходимости использования рекурсивных запросов, см., например, классическую книгу Joe Celko "Trees and Hierarchies in SQL for Smarties". Идея модуля ltree состоит в том, чтобы хранить иерархию связей в специальном типе данных ltree и предоставлять индексную поддержку для основных операций - поиск всех родителей, поиск всех детей и других (14). Удобство использования этого модуля и большое количество полезных функций делает ltree очень полезным для решения типичных задач цифровых библиотек.
Вспомогательный модуль для создания композитных индексов, поддерживает практические все основные типы данных используемые в PostgreSQL. Типичным примером использования является создание индекса по полнотекстовому полю и времени. Такой индекс можно использовать не только для обычного полнотекстового поиска, но и для его ускорения поиска в определенном временном интервале.
На пользовательском уровне новый тип очень похож на хеш (ключ => значение), причем синтаксис операторов и функций подобен интерфейсу к хешам в языке Perl. Модуль hstore очень полезен для хранения атрибутов, по которым не производится поиска, но нужны для показа. Например, требуется хранить несколько разнородные объекты, которые имеют только несколько общих атрибутов, что неминуемо приводит к большому количеству атрибутов, большое количество их которых имеет значение NULL. При этом, поиск производится только по некоторым из них. Модуль позволяет «упаковать» неиспользуемые атрибуты в один и обеспечивает доступ в случае показа.
Этот модуль предназначен для организации полнотекстового поиска в БД и является де-факто стандартным поисковым механизмом PostgreSQL. Его отличительной особенностью является online-индекс и полная интеграция с БД, что дает возможность проводить полнотекстовый поиск с ограничениями по атрибутам. Например, искать по документам, в зависимости от уровня доступа пользователя и дате публикации. Tsearch2 (11) поддерживает использование словарей, предоставляет API для их создания. Поддержка словарей популярных форматов ispell (для приведения слов к их нормальной форме) и стемминга на основе Портеровского алгоритма (13) позволяет использовать tsearch2 со многими языками. Гибкость настройки tsearch2, конфигурация которого хранится в базе данных и доступна с помощью стандартных команд SQL, позволяет разрабатывать различные поиски ориентированные на разные задачи. Модуль предоставляет два вида ранжирующих функций, использующие координатную информацию, и которые можно использовать для сортировки результатов поиска по их релевантности запросу.
Характерные свойства:
Отметим, что полнотекстовый поиск в PostgreSQL полностью интегрирован с ядром БД, т.е. транзакционнен, конкурентен и поддерживает восстановление после сбоев. В предстоящей версии PostgreSQL (8.3) полнотекстовый поиск будет уже встроенным и доступен без установки дополнительных модулей (12).
Часто бывает необходимо предложить пользователю возможность исправить запрос, например, из-за опечатки. Модуль pg_trgm позволяет быстро найти подходящие слова-кандидаты из заранее проиндексированного словаря, которые разбиваются на триграммы и индексируются с помощью GINи GiST. Слово из запроса также разбивается на триграммы и среди всех слов в словаре находятся слова-кандидаты, которые имеют наибольшее количество совпадающих триграмм. Чаще всего этот модуль используется в сочетании с полнотекстовым поиском.
Вопросы выбора технологической платформы является весьма важным при планировании проекта и наш положительный опыт реализации больших хранилищ с использованием свободного ПО может оказаться полезным.
Авторы выражают благодарность Российскому Фонду Фундаментальных Исследований за многолетнюю поддержку их исследований ( гранты 05-07-90225-a, 06-07-89182-а).
Ссылки:
