45. Физическая организация БД; критерии выбора физической организации данных; указатели; цепи и кольцевые структуры; способы адресации; индексно-последовательная организация.

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

Критерии выбора физической организации данных

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

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

Указатели

Цепи и кольцевые структуры

Способы адресации

Последовательное сканирование файла. Наиболее простым способом локализации записи является сканирование файла с проверкой ключа каждой записи. Этот способ, однако, требует слишком много времени и может применяться, когда каждая запись все равно должна быть прочитана.
Блочный поиск. Если записи упорядочены по ключу, то при сканировании файла не требуется чтение каждой записи. ЭВМ могла бы, например, просматривать каждую сотую запись в последовательности возрастания ключей. При нахождении записи с ключом большим, чем искомое значение, просматриваются последние 99 записей, которые были пропущены.
Двоичный поиск. При двоичном поиске в файле записей, упорядоченных по ключу, анализируется запись, находящаяся в середине поисковой области файла (изначально всего файла), а ее ключ сравнивается с поисковым ключом. Затем поисковая область делится пополам, и процесс повторяется для соответствующей половины области, пока не будет обнаружено искомое значение или длина области не станет равной 1. Число сравнений в этом случае будет меньше, чем для случая блочного поиска.
Индексно-последовательные файлы. Если файл упорядочен по ключам, то для адресации может использоваться таблица, называемая индексом,связывающая ключ хранимой записи с ее относительным или абсолютным адресом во внешней памяти.
Индексно-произвольные файлы. Произвольный (не упорядоченный по ключу) файл можно индексировать точно так же, как и последовательный файл. Однако при этом индекс должен содержать по одному элементу для каждой записи файла, а не для блока записей. Более того, в нем должны содержаться полные абсолютные (или относительные) адреса, в то время как в индексе последовательного файла адреса могут содержаться в усеченном виде, так как старшие знаки последовательных адресов будут совпадать.
Хэширование. Простым и полезным способом вычисления адреса является хэширование (перемешивание). В данном методе ключ преобразуется в квазислучайное число, которое используется для определения местоположения записи.

Индексно-последовательная организация.

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