 |
Индексно-произвольная организация
|
|
|
|
Этот способ организации данных используется, когда надо обеспечить доступ по нескольким первичным ключам. Поскольку, в общем случае, невозможно упорядочить линейный список сразу по нескольким ключам, требуется применять особые методы оптимизации поиска.
В таком случае список упорядочивается по тому ключу, по которому предполагаются наиболее частые запросы. По этому ключу организуется индекс как в случае индексно-последовательной организации (см. предыдущий раздел). Остальные значения первичных ключей формируют дополнительный файл – также индекс. Они включаются в индекс в полном составе из исходного файла и упорядочиваются. Кроме того, в индекс записываются ссылки на эти элементы в основном файле в виде порядковых номеров записей.
Пусть основной файл вновь соответствует реляционной модели для сущности кафедра из рассмотренного ранее примера и имеет вид:
кафедра
| название | шифр в вузе |
| АПП | |
| СУиВТ | |
| ТАМ | |
| Экономики |
В данной модели, как отмечалось ранее, два первичных ключа – название и шифр в вузе. Пусть предполагается искать данные по обоим ключам, причем, в основном поиск будет вестись по ключу название. Тогда по этому ключу упорядочиваются записи в файле (что и сделано в таблице). Видно, что второй ключ имеет неупорядоченные значения.
Формируются два индекса: первый – для ключа название – аналогичен предыдущему примеру:
| название | № п/п |
| СУиВТ | |
| Экономики |
Второй индекс имеет вид:
| шифр в вузе | № п/п |
Видно из второй таблицы, что значения ключа шифр в вузе упорядочены по возрастанию. Это позволяет данный индекс рассматривать как упорядоченный последовательный файл и применять к нему рассмотренные методы доступа в разделе «Последовательная организация».
|
|
|
Цепь подобных записей
К исходному файлу не предъявляется никаких требований. К нему достраиваются дополнительные файлы – индексы - в количестве, соответствующем числу вторичных ключей. Записи таких файлов имеют два поля: первое – значение вторичного ключа из основного файла, второе – ссылка на первую запись в основном файле с таким же значением вторичного ключа (в качестве ссылки используется порядковый номер записи в файле). Сами записи файла также модифицируются: они дополняются полями в количестве, соответствующем числу вторичных ключей. Каждое поле служит для организации цепочек записей с одним значением вторичного ключа.
Пусть основной файл имеет вид:
сотрудник
| ФИО | ученая степень | научное звание | контактные данные | название (кафедры) | название (должности) |
| Иванов И.И. | к.т.н. | доцент | СУиВТ | доцент | |
| Петров П.П. | к.т.н. | нет | ТАМ | доцент | |
| Сидоров С.С. | нет | нет | СУиВТ | ассистент | |
| Яковлев Я.Я. | д.т.н. | профессор | ТАМ | профессор |
Вторичными ключами являются ученая степень, научное звание, название (кафедры), название (должности). Построим индексы для этих ключей:
| ученая степень | № п/п | научное звание | № п/п | название (кафедры) | № п/п | название (должности) | № п/п | |||
| д.т.н. | доцент | СУиВТ | ассистент | |||||||
| к.т.н. | нет | ТАМ | доцент | |||||||
| нет | профессор | профессор |
Как видно из таблиц, каждый индекс содержит поле со всеми значениями соответствующего вторичного ключа из основного файла и поле (озаглавлено № п/п), в котором указывается номер записи основного файла, где впервые встречается соответствующее значение вторичного ключа. Значения вторичных ключей в индексах упорядочены по возрастанию, так что с индексами можно работать как с упорядоченными файлами (в роли первичных ключей таких файлов выступают вторичные ключи основных файлов).
|
|
|
Модифицируем также и основной файл. Для удобства поместим дополнительные поля (они выделены заливкой) справа от соответствующего вторичного ключа. Получим таблицу:
сотрудник
| ФИО | ученая степень | № п/п | научное звание | № п/п | контактные данные | название (кафедры) | № п/п | название (должности) | № п/п |
| Иванов И.И. | к.т.н. | доцент | - | СУиВТ | доцент | ||||
| Петров П.П. | к.т.н. | - | нет | ТАМ | доцент | - | |||
| Сидоров С.С. | нет | - | нет | - | СУиВТ | - | ассистент | - | |
| Яковлев Я.Я. | д.т.н. | - | профессор | - | ТАМ | - | профессор | - |
Рассмотрим, как выполняется задача поиска нужной записи.
Пусть надо найти фамилии и инициалы всех сотрудников, работающих в должности ассистента. Очевидно, Кдоступ = < название (должности) = ассистент>. Поиск осуществляется последовательным выполнением шагов:
1) по индексудля ключа название (должности) определяется запись со значением первого поля, равным ассистент (поскольку индекс – это упорядоченный файл, к нему применяются рассмотренные ранее методы, например, метод последовательного сканирования, анализ работы которых в данном случае не приводится). Это первая запись индекса;
2) по полю № п/п выясняется номер записи основного файлас искомым ключом доступа – это запись с номером 3;
3) в основном файле выбирается третья запись. Выводится фамилия и инициалы сотрудника – это Сидоров С.С.;
4) в соответствии со значением поля № п/п для поля название (должности) в основном файле определяется номер следующей записи основного файла с аналогичным значением вторичного ключа – поскольку данное поле не содержит ссылки, это означает, что цепочка записей закончилась, следовательно, список сотрудников сформирован; алгоритм заканчивает работу.
Если доступ планируется одновременно по нескольким вторичным ключам, можно оптимизировать эту процедуру. Оптимизация состоит в том, что каждый индекс дополняется полем, в котором указывается число записей в цепочке, и тогда вначале обращение осуществляется к тому индексу, в котором длина цепочки минимальна.
|
|
|
Например, основной список представлен таблицей:
сотрудник
| ФИО | ученая степень | № п/п | научное звание | № п/п | контактные данные | название (кафедры) | № п/п | название (должности) | № п/п |
| Иванов И.И. | к.т.н. | доцент | - | СУиВТ | доцент | ||||
| Петров П.П. | к.т.н. | - | нет | ТАМ | доцент | - | |||
| Сидоров С.С. | нет | - | нет | - | СУиВТ | - | ассистент | - | |
| Яковлев Я.Я. | д.т.н. | - | профессор | - | ТАМ | - | профессор | - |
Индексы модифицированы и показаны в таблицах (дополнительные поля показаны заливкой):
| ученая степень | № п/п | длина цепочки | научное звание | № п/п | длина цепочки | название (кафедры) | № п/п | длина цепочки | название (должности) | № п/п | длина цепочки | |||
| д.т.н. | доцент | СУиВТ | ассистент | |||||||||||
| к.т.н. | нет | ТАМ | доцент | |||||||||||
| нет | профессор | профессор |
Значения полей длина цепочки – это количество записей основного файла с соответствующим значением вторичного ключа.
Пусть надо определить, какие сотрудники работают в должности доцентов и не имеют ученой степени. Очевидно, Кдоступ = < название (должности) = доцент, ученая степень = нет). Задача решается следующим образом:
1) в индексах для вторичных ключей название (должности) и ученая степень ищутся записи со значениями полей доцент и нет: это, соответственно, записи с номерами 2 и 3;
2) анализируется, для какого индекса поле длина цепочки имеет минимальное значение: очевидно, длина цепочки для ключа со значением нет короче, чем для ключа со значением доцент, поэтому для поиска в основном файле определяется ключ ученая степень со значением нет;
3) в соответствии со значением поля № п/п выбранного ключа осуществляется обращение к элементу с номером 3 основного файла;
4) у выбранного элемента анализируется поле название (должности): его значение равно ассистент: данная запись не удовлетворяет условиям поиска, а потому никакого вывода данных пользователю не происходит;
|
|
|
5) в соответствии со значением поля № п/п для поля ученая степень определяется номер следующей записи основного файла с аналогичным значением вторичного ключа. Поскольку это поле не содержит ссылки, это означает, что цепочка записей закончилась, следовательно, список сотрудников сформирован (он пуст); алгоритм заканчивает работу.
Инвертированные файлы
Основной файл не изменяется. Строятся индексы в нужном количестве. В индекс включаются все значения соответствующего вторичного ключа, а также все ссылки на записи основного файла с данным значением вторичного ключа.
Пусть основной файл показан в таблице:
сотрудник
| ФИО | ученая степень | научное звание | контактные данные | название (кафедры) | название (должности) |
| Иванов И.И. | к.т.н. | доцент | СУиВТ | доцент | |
| Петров П.П. | к.т.н. | нет | ТАМ | доцент | |
| Сидоров С.С. | нет | нет | СУиВТ | ассистент | |
| Яковлев Я.Я. | д.т.н. | профессор | ТАМ | профессор |
Соответствующие индексы показаны в таблицах:
| ученая степень | № п/п | научное звание | № п/п | название (кафедры) | № п/п | название (должности) | № п/п | |||
| д.т.н. | доцент | СУиВТ | 1, 3 | ассистент | ||||||
| к.т.н. | 1, 2 | нет | 2, 3 | ТАМ | 2, 4 | доцент | 1, 2 | |||
| нет | профессор | профессор |
Расположение всех ссылок для некоторого вторичного ключа в одном поле позволяет исключить перебор записей в цепочке записей при их поиске.
Рассмотрим, как выполняется задача поиска нужной записи.
Пусть надо определить список всех сотрудников, работающих в должности доцента, Кдоступ = < название (должности) = доцент>. Поиск осуществляется последовательным выполнением шагов:
1) по индексу для ключа (название должности) находится соответствующий элемент: это вторая запись в файле;
2) выбираются ссылки для этой записи: это множество {1, 2};
3) по основному файлу выбираются последовательно записи с номерами 1 и 2 и выводится содержимое поля ФИО для этих записей; получаем список - Иванов И.И. и Петров П.П. Работа алгоритма закончена.
[1] Напомним, что записи файла упорядочены по возрастанию первичного ключа
|
|
|
