Инвертированные списки

Дата добавления: 2014-11-24 | Просмотров: 1652

Два предыдущих метода ориентировались, в основном, на поиск записей с уникальным значением ключа. Однако нередко возникает задача выбора группы записей по определенным параметрам, каждый из которых не уникален. Более того, записей с каким-то фиксированным значением параметра может быть очень много. Это характерно, например, для библиотечного поиска, когда требуется подобрать книгу с заданным годом издания, автором, издательством и т.п. Для подобных задач существуют специальные методы, наиболее популярный из которых – метод инвертированных списков или инвертированный метод.

Считается, что поиск может проводиться по значениям любых полей (вторичных ключей) или их комбинации. Для каждого вторичного ключа создается индекс. В нем на каждое значение ключа формируется список указателей на записи файла с этим значением. Это не обязательно физическая ссылка, допускается и первичный ключ. Таким образом, инвертированный индекс группируется по именам полей, которые в свою очередь группируются по значениям. При поиске записи с заданным значением ключа выбирается нужный индекс, в нем каким-то способом (например, индексно-произвольным) выбирается статья с этим значением, затем выбирается все список ссылок на записи с искомым значением. Легко видеть, что поиск по комбинации значений полей сводится к выбору соответствующих списков и их пересечению (операция И) или объединению (операция ИЛИ).

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

Эффективность доступа зависит от эффективности поиска в индексе, но в любом случае она ниже 0,5 (доступ к индексу и доступ к записи файла). Для повышения эффективности следует размещать индексы в оперативной памяти.

Эффективность хранения зависит от метода хранения индекса, от числа инвертируемых полей и от множества значений каждого вторичного ключа (от длины инвертированного списка).

Пример

В приведенном примере в информационном файле (правый прямоугольник) размещается список студентов с оценками. Требуется выбрать всех студентов, имеющих одинаковое значение оценки. Левый прямоугольник символизирует индекс, в котором находится единственный вторичный ключ – «оценка». Каждому его значению соответствует список, в котором перечислены соответствующие номера записей информационного файла. Выбор всех двоечников сводится к нахождению в индексе соответствующего значения ключа «оценка» и загрузки записей, указанных в списке. Если нужно найти тех, кто получил «4» или «5», следует найти и объединить соответствующие списки. Подобные действия выполнялись бы, если бы запись содержала еще один вторичный ключ, скажем, предмет. Тогда для выборки тех, кто получил пятерки по предмету «Базы данных», следовало бы в соответствующих индексах найти списки для требуемых значений и взять их пересечение.

Контрольные вопросы

1. Для чего предназначено свойство индексированное поле?

2. Есть ли необходимость в хэш-коде при индексировании? Почему?

3. Чем отличается бинарный метод поиска от последовательного?

4. В какой схеме индексирования таблиц недостатки менее существенны?

5. Приведите четыре примера оценки эффективности доступа и хранения.

6. В чём отличие индексно-последовательного метода от метода инвертирования списков?

7. Приведите несколько несхожих примеров для каждого из трёх основных методов доступа.

РАЗДЕЛ 2.

Проектирование и использование баз данных

САМОСТОЯТЕЛЬНАЯ РАБОТА №6 (8 часов)

ТЕМА:Проектирование баз данных