Физическая организация баз данных. Файлы: последовательные, с прямым доступом, с хеш-адресацией, индексно-последовательные, В-деревья

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

Существуют три группы методов доступа:

1. Последовательные;

2. Индексные;

3. Адресные.

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

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

a) Последовательный доступ с фиксированной длиной записи.

A_i = A₀ + (i - 1)L

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

b) Последовательный доступ с записями переменной длины. В этом случае каждая запись содержит значение длины записи.

c) Последовательный доступ с записями неопределенной длины. В этом случае в конец каждой записи помечается определенным символом.

d) Простой линейный список.

· Со встроенными указателями

Y3

Данные

Данные

Y2

Y1

Данные

· С внешними указателями

e) Циклический однонаправленный список. Связь от последней записи идет к первой, поэтому доступ можно получить к любой записи начиная с любой записи

f) Двунаправленный список. Каждая запись имеет два указателя.

2. Индексные методы доступ. В дополнение к основному файлу создается индексный файл, который содержит значения ключей. Индексный файл упорядочен по значению ключа.

a) Метод доступа с полным индексом. Используется, когда основной файл не очень велик.

Основной файл

Индексный файл

Замечания: Если надо упорядочить исходный файл по нескольким ключам, то для него создается столько же индексных файлов. Т.к. значения вторичных ключей не уникальны, то индексный файл организуется по методу b) или c) последовательного доступа. Основной эффект с инвертированным массивом (вторичные ключи) применяется при поиске файлов по нескольким условиям. Алгоритм поиска строится так чтобы обращаться к индексным файлам. Наибольший эффект достигается тогда, когда индексный файл помещается в оперативной памяти.

b) Индексно-последовательный. Основной файл всегда упорядочен по первичному ключу, индексный файл содержит не на каждую запись как c) или d), а на группу или блок записей, т.е. на значение одного из ключей группы. Повторение ключей в группе недопустимо. В группе должно быть одинаковое число записей. Обычно при таком подходе индексный файл ещё меньше.

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

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

Поиск в B-дереве - это прохождение от корня к листу в соответствии с заданным значением ключа. Заметим, что поскольку деревья сильно ветвистые и сбалансированные, то для выполнения поиска по любому значению ключа потребуется одно и то же (и обычно небольшое) число обменов с внешней памятью. Более точно, в сбалансированном дереве, где длины всех путей от корня к листу одни и те же, если во внутренней странице помещается n ключей, то при хранении m записей требуется дерево глубиной log_n(m). Если n достаточно велико (обычный случай), то глубина дерева невелика, и производится быстрый поиск.

3. Адресные методы доступа. В этих методах значение ключа с помощью специальной функции преобразуется в значение адреса записей такой функции называется адресной. Существует два вида адресной функции:

a) Реализует взаимнооднозначное соответствие Адрес ↔ Ключ (прямой доступ).

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

b) Реализует однозначное соответствие Ключ ↔ Адрес (хеширование - перемешивание).