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