Виды адресации хранимых записей

В общем случае адреса записей БД нигде не хранятся. При поиске данных СУБД из словаря-справочника данных берёт информацию о том, в какой области памяти (например, в каком файле и/или на каких страницах памяти) расположены данные указанной таблицы. Но при этом для поиска конкретной записи (по значениям ключевых полей) система вынуждена будет прочитать всю таблицу. В РСУБД для ускорения поиска данных применяются индексы – специальные структуры, устанавливающие соответствие значений ключевых полей записи и "адреса" этой записи (КБД). Таким образом, вид адресации хранимых записей оказывает влияние на производительность, а также на переносимость БД с одного носителя на другой.

Рассмотрим три вида адресации: прямую, косвенную и относительную.

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

Указанные недостатки можно преодолеть, используя косвенную адресацию. Общий принцип косвенной адресации заключается в том, что в качестве КБД выступает не сам "адрес записи", а адрес места хранения "адреса записи".

Существует множество способов косвенной адресации. Один из них состоит в том, что часть адресного пространства страницы выделяется под индекс страницы (рис. 4.2). Число статей (слотов) в нём одинаково для всех страниц. В качестве КБД записи выступает совокупность номера нужной страницы и номера требуемого слота в индексе этой страницы (значения N, i на рис. 4.2). В i -м слоте на N -й странице хранится собственно адрес записи (смещение от начала страницы).

Рис. 4.2. Косвенная адресация с использованием индексируемых страниц

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

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

Третий способ адресации – относительная адресация. Простейший ва-риант относительной адресации может использоваться, например, в ситуации, когда данные одного объекта БД (таблицы) хранятся в отдельном файле и хранимая запись имеет формат фиксированной длины. Тогда в качестве значения КБД берётся порядковый номер записи, по которому можно вычислить смещение от начала файла. (Пример такой адресация – системы dBaseIII, dBaseIV).

Общий принцип относительной адресации заключается в том, что адрес отсчитывается от начала той области памяти, которую занимают данные объекта БД. Если память разбита на страницы (блоки), то адресом может выступать номер страницы (блока) и номер записи на странице (или смещение от начала страницы). В случае относительной адресации перемещение записи приведёт к изменению КБД и необходимости корректировки индексов, если они есть.

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