Индексно-последовательный метод доступа

Последовательные структуры данных (ПСД)

Способы физической организации и хранения данных

ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ БАЗ ДАННЫХ

Существует два понятия: логическая и физическаяорганизация данных.

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

Физическая – отражает физическую структуру хранения данных. Представляет собой совокупность файлов. При этом связи между файлами также реализуются с помощью файлов. При хранении данных в физической памяти используют шесть основных способов доступа к памяти.

1. Последовательный способ

2. Индексно-последовательный

3. Индексно-произвольный

4. Инвертированный

5. Прямой

6. Хеширования

Введем два критерия для оценки качества физических способов доступа.

1) Эффективность доступа – это количественная величина, обратная среднему числу обращений к внешней памяти. Имеется в виду количество обращений, которые необходимы для доступа к конкретной записи.

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

(последовательный способ)

ПСД характеризуется тем, что логический порядок элементов совпадает с физическим порядком расположения элементов. Элементами ПСД являются записи.

Отметим, что ПСД могут быть упорядоченными и неупорядоченными по значению ключевого признака. Имя ключевого признака одинаково во всех записях. Записи могут быть постоянной, переменной и неопределенной длины.

Преимущества.

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

Недостатки.

1. Неудобство корректировки

2. Длительность выборного поиска.

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

Примечание. В связи с широким распространением реляционных баз данных применение последовательного способа значительно возросло. Это объясняется тем, что многие реляционные СУБД предусматривают организацию хранения каждого отношения в виде последовательного файла.

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

Рассмотрим пример. Пусть в памяти машины имеется последовательно организованный файл.

Ф.И.О.	Возраст	Должность
Бендер Паниковский Балаганов Функ		Зав. отделением Курьер Конюх Зам. председателя

Если записи будут иметь фиксированную длину, то в памяти ЭВМ необходимо отвести место, равное максимальной длине.

Паниковский 60 Курьер*********

Функ ******* 70 Зам. председателя

Память используется неэффективно. На практике используют переменную длину записи.

Бендер & 30 & зав. отделением, где & - разделитель

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

При этом каждая запись должна иметь свой разделитель.

Бендер & 30? зав. отделением!

Отметим, что при этом объем вторичной памяти не изменяется. Вместе с тем, расходуется дополнительное время на распознавание знаков.

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

Рассмотрим пример.

Табельный №

№ цеха

Профессия

Разряд

Записи основного файла условно разделим на три блока и организуем индексный файл. В индексном файле каждая запись имеет два элемента: индекс и адрес.

Индекс	Адрес

Слесарь Токарь Наладчик

Слесарь Наладчик

Слесарь Токарь

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

бл.1

Значение ключа	Адрес блока		Отметим, что индексы из нескольких исходных ключей выбираются с наибольшим значением. Каждый блок соответствует некоторому множеству записей в исходном файле. Причем распределение записей по блокам должно быть равномерным.

	*0423
		бл.2

		*0934
	3	бл.3

	*1016

Предположим, что необходимо отыскать запись с ключом 0981. При этом выполняется следующая процедура. Сначала считывается индекс 0423, требуемый адрес найти не можем, т.к. значение ключа 0423 меньше, чем 0981, затем считываем следующее значение 0934, переходим к индексу 1016. По индексу 1016 в блоке 3 отыскиваем требуемую запись.

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

Примечание. Для очень больших исходных файлов иногда используется несколько уровней индексации. Это означает, что в индексном файле делается ссылка не на блок с исходными данными, а на блок с другими индексами.

Рассмотрим пример.

	4
	5		*0318

	6

3			*0914

		.
		.
		.

. . . .

Для дополнения записи в индексно-последовательном методе используются различные приемы. Например,

1) отводится дополнительная область переполнения каждому блоку

2) организуется общая резервная область переполнения для всех блоков.