Последовательный способ доступа к памяти. Пример

Физ. Организация БД. Основные способы доступа к памяти и критерии оценки их качества.

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

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

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

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

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

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

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

5. Прямой

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

 

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

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

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

Индексно-произвольный метод доступа. Пример

 

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

Возможны два варианта:

а) индекс упорядочен по возрастанию ключа.

 

бл.1

Индекс	Адрес
	3 2 1
	бл.2

 

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

Выводы.

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

2. Эффективность доступа выше. Если индексный файл полностью помещается в оперативной памяти, эффективность доступа равна единице.

Последовательный способ доступа к памяти. Пример

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

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

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

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

Недостатки.

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

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

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

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

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

Пример

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

 

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

 

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

 

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

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

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

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

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

 

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

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

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