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

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

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

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

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

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

Пример

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

Конец примера