Методы доступа к записям ФБД

Доступ к записям необходим как при записи данных в БД, так и при извлечении из неё. При размещении записей в файлы и на страницы они могут содержать идентификационные параметры, так называемые указатели (которые находятся в служебной части). Эти указатели используются для определения местоположения следующей записи, если установлено место положение текущей записи. Такой подход является наиболее распространенным. Однако при размещении записей и извлечении записей используются и другие методы доступа. Рассмотрим в частности, последовательный доступ и доступ по первичному ключу.

 

6.3.1. Последовательный доступ(используются для последовательных файлов).

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

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

 

Доступ по первичному ключу

Первичный ключ идентифицирует записи внутри данного файла и его значение не меняется в течение времени существования данной записи. Поэтому СУБД довольно часто реализует доступ по значению первичных ключей(как при запоминании записей, так и при их извлечении). При этом наиболее распространенным являются следующие 2 способа доступа:

1. хеширование;

2. индексирование.

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

Рис. 6.3.2.1

При извлечении записи СУБД выполняет следующие действия:

1. подключает программу хеширования;

2. эта программа вычисляет номер страницы, куда была помещена искомая запись;(возможно с помощью ДФ и ДД).

3. СУБД просматривает цепь синонимов на этой странице до нахождения нужной записи.

 

Индексирование(используется для индексно-последовательных файлов). Суть этого способа в том, что СУБД, размещая записи по страницам памяти формирует т.н. индексные таблицы которые содержат адреса этих записей и используются для извлечения нужной записи по значению первичного ключа.

Рассмотрим пример одного из вариантов индексирования.

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

ТМИ содержит: 1) Номер строки в ТМИ соответствует номеру страницы.2) Номер последней записи в соответствующей сроке.

В зависимости от объема (количества) страниц в файле могут создаваться индексные таблицы разных уровней: таблицы младших индексов (ТМИ), таблицы старших индексов (ТСИ).

Рис.6.3.2.2.

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

Предположим, что нужно найти запись под номером 210 (со значением первичного ключа). Первоначально СУБД обращается к ТСИ, последовательно просматривается ТСИ и ищется те строка (запись) ТСИ для которой выполняется условие

210 < 512 (это2-я строка).

В результате выяснено, что необходимо продолжить поиск во 2-й таблице (ТМИ2). Затем следует анализ ТМИ2, т.е. проверяются соотношения 210 и чисел ТМИ.

Для первой строки 210 </ 170

...

Для пятой строки 210 < 230 (5-я строка).

Следовательно в результате определяем из ТМИ2, что следует продолжить поиск на 5 странице, но уже таблицы данных (в пятой строке).

Далее на странице 5(в пятой строке) осуществляется последовательный просмотр записей с проверкой условия, что значений первичного ключа совпадает со значением 210.

1-ая запись 5 строки 181¹210

2-ая запись 5 строки 195¹210

1-ая запись 5 строки 210=210

Следовательно результат: нужная запись в 5-ой странице на 3-ей позиции.

 

Физическое проектирование.

Как уже рассматривалось ранее последовательность физического проектирования включает следующие этапы:

Этап 4. Перенос ГЛМД в среду СУБД.

Этап 5. Проектирование физическогопредставления Базы Данных.

Целью последнего этапа является:

Определение файловой структуры и методов доступа, которые будут использоваться для представления таблиц Базы Данных. Другими словами, определение способа хранения таблиц во вторичной памяти (т.е. в ВЗУ).

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

1. Пропускная способность транзакций.

2. Время ответа (отклика).

3. Необходимая дисковая память.

ПСТ- это количество транзакций, которые могут быть обработаны за заданный интервал времени. ВО – характеризует временной промежуток, необходимый для выполнения одной транзакции.С точки зрения пользователя, желательно сделать время ответа системы минимальным. Однако есть факторы, которые оказывают влияние на величину времени ответа, но не могут контролироваться разработчиком. Например, уровень загрузки системы.

НДП – это объём дискового пространства, необходимого для размещения файлов Базы Данных. Разработчик должен стремиться минимизировать объём используемой дисковой памяти.

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