Достоинства и недостатки

Ограничения целостности

Манипулирование данными

Примерный набор операций может быть следующим:

• Найти конкретную запись в наборе однотипных записей (инженера Сидорова);
• Перейти от предка к первому потомку по некоторой связи (к первому сотруднику отдела 310);
• Перейти к следующему потомку в некоторой связи (от Сидорова к Иванову);
• Перейти от потомка к предку по некоторой связи (найти отдел Сидорова);
• Создать новую запись;
• Уничтожить запись;
• Модифицировать запись;
• Включить в связь;
• Исключить из связи;
• Переставить в другую связь и т.д.

В принципе их поддержание не требуется, но иногда требуют целостности по ссылкам (как в иерархической модели).

Сильные места ранних СУБД:

• Развитые средства управления данными во внешней памяти на низком уровне;
• Возможность построения вручную эффективных прикладных систем;
• Возможность экономии памяти за счет разделения подобъектов (в сетевых системах).

Недостатки:

• Слишком сложно пользоваться;
• Фактически необходимы знания о физической организации;
• Прикладные системы зависят от этой организации;
• Их логика перегружена деталями организации доступа к БД.

Приложение

Инвертированный файл – расшифровка понятия

Инвертированный файл представляет собой структуру, которая состоит из двух часте й:

• словарь, содержащий все термы, встретившиеся в коллекции и ссылку на массив данных «пост-листа» для каждого из них. Помимо того возможно наличие специальных структур, ускоряющих поиск слова в словаре.
• пост-листы, представляющие собой массив информации обо всех вхождениях данного слова в документы коллекции.

При реализации инвертированного файла можно организовать его как отдельную структуру или на основе В+ дерева, используя наработанные механизмы работы с ними.

При организации эффективного хранения индекса и оптимизации работы с ним требуется использовать алгоритмы сжатия информации. Наибольший объем имеют пост-листы, представляющие, в простейшем случае, массив идентификаторов содержащих их документов. Также, в различных реализациях, в них может храниться вес этого документа относительно данного слова, указания на коллекцию, к которой относится документ и другие данные.

В случае, если в пост-листе хранятся идентификаторы в возрастающем порядке, компактнее будет хранить их разность, чем идентификаторы целиком. Сами же числа сохраняют с применением техник кодирования чисел:

• кодов переменной длины. Например, первые семь байтов каждого бита передают значимую часть числа, последний байт обозначает оканчивается ли на этом число или нет.
• гамма и дельта кодирование Элиса и параметрические коды Голомба.

В случаях, когда требуется эффективное сжатие коротких пост-листов, имеет смысл объединять списки для нескольких слов. В этом случае получается список идентификаторов, который может быть эффективно кодирован одним из способов компактного хранения чисел. У каждого идентификатора указывается слово или список слов из объединенного списка, которые в нем встречаются. Можно указывать их номера, сжатые методом Хаффмана.

В случае реализации индекса на основе В+ деревьев на размер пост-листа накладывается ограничение реализации. Для того, чтобы разместить длинные пост-листы в индексе применяются два метода:

1. разбиение пост-листа. Один пост-лист размещается в нескольких записях. В этом случае ключом дерева является не только слово, но и первое значение в пост-листе.

2. вынесение длинных пост-листов во внешнюю, по отношению к дереву, структуру.

Потери связанные с повторением в ключе записи слов можно компенсировать префиксным сжатием всей страницы индекса.

При получении пост-листа, разбитого на части, можно декодировать только нужную его часть, что позволяет более эффективно расходовать память.

При совершении поиска по поисковому запросу, работа с индексной информацией состоит из этапов поиска каждого слова запроса в словаре, получении для каждого пост-листа (пост-листов), раскодировании их, полном или дополнительном взвешивании документа по данному списку слов запроса, формировании результатов для пользователя.

Изменения индексной информации делятся на массовые, при которых изменяется большое число документов и имеет смысл полное перестроение индекс, и одиночные, при которых полного перестроения не происходит. Полное перестроение используется при начальной инициализации индекса. При этом в выделенной области оперативной памяти собирается индекс по части документов, при заполнении сохраняется во временных файлах, а потом многопоточным слиянием объединяется в единую индексную структуру.

В случае реализации индекса через В+ деревья эффективно происходит добавление и удаление информации, разбиение длинных пост-листов позволяет эффективно обновлять только нужные их части, не считывая остальные

Дата добавления: 2014-01-07