Методы доступа к данным.

Метод доступа – это средство, которое использует СУБД для детального управления физическим доступом к БД. Метод доступа реализуется набором подпрограмм, назначение которых состоит в том, чтобы скрыть все детали управления устройствами от СУБД и обеспечить СУБД интерфейсом хранимых записей.

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

Адрес хранимой записи в последующем может использоваться СУБД для прямой выборки этого экземпляра записи.

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

1. Хэширование – алгоритмическое определение адреса физической записи по значению ее ключа.

2. Физический последовательный метод доступа предполагает хранение физических записей в логической последовательности.

Эффективность метода доступа физической последовательности крайне низка. Для выборки нужной записи нужно просмотреть все предшествующие ей записи БД.

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

(v,b) – первая запись в блоке с адресом b имеет ключ v.

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

(v,a) – а – адрес записи.

5. Инвертированный используется для поиска. Хранение (обновление) с помощью других методов доступа.

6. Прямой устанавливает взаимно-однозначное соответствие между ключом записи и ее адресом.

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

Сортированный файл называется главным, другой файл состоит из пар (v,b) – файлом индексов. Кроме выполнения операций включения, удаления, модификации с файлами индексов, нужно получать ответы на запросы следующего вида: при заданном значении ключа v₁ для индексного файла найти в индексе такую запись (v₂,b), что v₂<v₁ и либо (v₂,b) является последней записью в индексе, либо следующая запись (v₃,b) удовлетворяет условию v₁<v₃ (говорят, что v₂ покрывает v₁).

Поиск. Пусть необходимо найти запись (v₂,b) такую, что v₂ покрывает заданное значение ключа v₁. Используется двоичный поиск. Если задано значение ключа v₁ и индекс над блоками В₁, В₂,…, В_n , то рассматривается средний блок В_n/2 и сравнивается v₁ со значением ключа v₂ в первой записи этого блока.

Если v₁<v₂, то рассматривается В₁,…, В_n/2. Если v₁v₂, то процесс повторяется над блоками В_n/2,…, В_n. В конце концов для рассмотрения останется один блок. Т.к. на каждом этапе число блоков уменьшается вдвое, то не более чем за log₂(n+1) шагов поиск локализуется до одного блока. Внутри блока нужная запись ищется линейным поиском.

Модификация. Используется сначала поиск. Если модификация изменяет ключ, будем интерпретировать ее как удаление с последующим включением. В противном случае это перезапись данной записи.

Включение записи со значением ключа v₁:

1. применяется процедура поиска, чтобы найти блок В_i, в котором должна находиться эта запись;

2. если в блоке В_i есть свободное место, то все записи сдвигаются. Если места нет, то ищется свободный блок и в нем сдвигаются записи; а блок В_i смещается на блок В_i+1. Если В_i последний блок, то создается новый блок.

Удаление аналогично включению.

Адрес – идентификация месторасположения хранящихся данных.

В реляционных СУБД обычно используются два основных метода доступа к данным: последовательный и поиск по индексу.

При последовательном поиске данных осуществляется перебор всех записей файла БД.

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

Структуру файлов рассмотрим на примере dbf (FoxPro, Clipper, dBase). Большинство СУБД и интегрированных пакетов имеют средства экспорта и импорта этих файлов.

заголовок

Дескрипторы

32 0÷255 записи,

байта терм. символ имеют fix длину

Дескриптор содержит:

а) имя поля;

б) тип (используются коды ASCII символов C, N, F, D (дата), L, M);

в) длина поля.

Список записей. Каждая запись начинается с односимвольного флага удаления записи (‘ ‘ – не удалена, ‘*’ – удалена). За флагом удаления идут значения полей записи БД в том порядке, как они следуют в списке дескрипторов. Специальных символов разграничения полей нет.