Пример инвертированного файла

На рис. 9.37 показана структура инвертированного файла, касающаяся примера, рассмотренного в разд. 9.7.1. Здесь записи с одинаковым значением ключа образуют связанный список и таблица индексов содержит начальные адреса таких списков. Поскольку может потребоваться также информация о студентах данной возрастной группы, то сформирован и индекс даты рождения. Каждая запись имеет длину 100 байт, однако одна сводка о студенте может состоять из нескольких записей. Каждая сводка начинается с трех обязательных ключевых полей, содержащих фамилию студента,, аббревиатуру, составленную из первых букв названий курсов, посещаемых им или ею, и последние две цифры года рождения. Для каждого поля ключа предусмотрен отдельный указатель, определяющий адрес следующей записи с таким же значением в данном поле. После ключевых полей размещаются другие данные (постоянный адрес местожительства, сведения о среднем образовании, семейное положение и т. д.), которые не используются в качестве ключей поиска.

Приводимый ниже пример иллюстрирует, как необходимая информация может быть выбрана из инвертированного файла.
Для получения информации о Смите, сначала исследуется рассортированный индекс студентов: в результате выясняется, что адрес начала сводки о Смите равен 1300. Начиная с этого адреса, с помощью указателей полей фамилии может быть просмотрена вся информация о Смите, хранящаяся в ячейках 1300, 2000 и 2400.

Если необходимо получить список всех студентов, изучающих физику, то, используя индекс курсов, можно получить адрес (1000) начала сводки о первом (по фамилии) студенте этого курса — Андерсоне. Связанный список — «Курс физики» позволяет определить фамилии других студентов этого курса: Дугласа, Ливи, Миллера, Смита, Тэйлора и Уотсона.

Индекс даты рождения указывает, что сводка о первом студенте, родившемся в 1952 г., начинается с адреса 1400. В данном случае однотипными считаются записи о Брайене, Иверсоне и Ливи.

На рис. 9.38 показаны для тех же самых данных таблицы индексов, причем в каждой таблице перечисляются адреса всех записей с идентичным значением соответствующего ключа. В этом случае поля указателей в сводках о студентах не нужны. Если в некоторой строке такой таблицы индексов не оказывается свободного места для размещения адреса вновь добавляемой записи, то в таблице заводится новая строка, либо непосредственно следующая за заполненной, либо связанная с ней через указатель, в которую будут заноситься новые адреса (см. на рисунке строки для физики).

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


Организация данных и структуры данных Метод обменной сортировки с выбором Метод турнирной сортировки Методом квадратичной сортировки Метод вставки Методы Замещения Слияние рассортированных подфайлов Осциллирующей сортировки Многофазная сортировка Сравнение методов внешней сортировки Генераторы программ сортировки слияния Информация и ее представление в вычислительных машинах Ассоциативная структура Последовательная структура Связанный список Простые операции над списками Иерархические структуры Древовидная структура Линейное представление древовидной структуры Преобразование арифметических выражений в списковые структуры Сетевая структура Системы управления базами данных Инвертированные файлы Пример инвертированного файла Поиск по нескольким ключам Элементы системы управления базой данных Работа системы управления базой данных Роль администратора базы данных Определения Организация в записи Компоненты записи Блоки Форматы блоков и записей Организация и методы доступа Последовательная организация Метод доступа с очередями Библиотечная организация Оглавление тома Метки оглавления тома Метки тома магнитной ленты Прямая организация Прямая адресация Методы рандомизации Сравнение методов рандомизации Индексно-последовательная организация Область основных данных Области переполнения Области индексов Произвольный поиск Режимы обработки Добавление новых записей Статистика Общее про методы сортировки Сортировка в основной памяти Метод сортировки посредством выбора	Пример инвертированного файла На рис. 9.37 показана структура инвертированного файла, касающаяся примера, рассмотренного в разд. 9.7.1. Здесь записи с одинаковым значением ключа образуют связанный список и таблица индексов содержит начальные адреса таких списков. Поскольку может потребоваться также информация о студентах данной возрастной группы, то сформирован и индекс даты рождения. Каждая запись имеет длину 100 байт, однако одна сводка о студенте может состоять из нескольких записей. Каждая сводка начинается с трех обязательных ключевых полей, содержащих фамилию студента,, аббревиатуру, составленную из первых букв названий курсов, посещаемых им или ею, и последние две цифры года рождения. Для каждого поля ключа предусмотрен отдельный указатель, определяющий адрес следующей записи с таким же значением в данном поле. После ключевых полей размещаются другие данные (постоянный адрес местожительства, сведения о среднем образовании, семейное положение и т. д.), которые не используются в качестве ключей поиска. Приводимый ниже пример иллюстрирует, как необходимая информация может быть выбрана из инвертированного файла. Для получения информации о Смите, сначала исследуется рассортированный индекс студентов: в результате выясняется, что адрес начала сводки о Смите равен 1300. Начиная с этого адреса, с помощью указателей полей фамилии может быть просмотрена вся информация о Смите, хранящаяся в ячейках 1300, 2000 и 2400. Если необходимо получить список всех студентов, изучающих физику, то, используя индекс курсов, можно получить адрес (1000) начала сводки о первом (по фамилии) студенте этого курса — Андерсоне. Связанный список — «Курс физики» позволяет определить фамилии других студентов этого курса: Дугласа, Ливи, Миллера, Смита, Тэйлора и Уотсона. Индекс даты рождения указывает, что сводка о первом студенте, родившемся в 1952 г., начинается с адреса 1400. В данном случае однотипными считаются записи о Брайене, Иверсоне и Ливи. На рис. 9.38 показаны для тех же самых данных таблицы индексов, причем в каждой таблице перечисляются адреса всех записей с идентичным значением соответствующего ключа. В этом случае поля указателей в сводках о студентах не нужны. Если в некоторой строке такой таблицы индексов не оказывается свободного места для размещения адреса вновь добавляемой записи, то в таблице заводится новая строка, либо непосредственно следующая за заполненной, либо связанная с ней через указатель, в которую будут заноситься новые адреса (см. на рисунке строки для физики). На рис. 9.37 показано, что элементы с одинаковыми значениями ключа образуют связанный список, упорядоченный по алфавиту в соответствии с фамилиями студентов, а в таблице индексов, представленной на рис. 9.38, такой порядок не соблюдается. Логические и физические последовательности строк таблицы индексов одни и те же на обоих рисунках. Но это не является обязательным условием. Таблица индексов сама может быть представлена в виде связанного списка или, если количество строк в ней невелико, она может быть даже не упорядочена.