3. Физическая организация бд

3.1. Основы физической организации бд

Факторы, влияющие на выбор физической организации БД

При выборе того или иного метода доступа учитываются следующие факторы:

1. Скорость поиска данных (главный фактор).

2. Скорость модификации данных.

3. Общий объем БД.

4. Реализация ограничений целостности на данные.

5. Обеспечение многопользовательского доступа к данным.

Перечисленные требования к физической организации БД являются противоречивыми (требуется компромисс).

Классификация методов доступа.

Выбор метода доступа зависит от пользовательских запросов.

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

1. Получить все или многие записи. При ответе на запрос требуется просмотреть от X % до 100 % записей. Величина X зависит от класса СУБД (Oracle: X  25 %) (осуществяется последовательный просмотр файлов БД без использования поиска по ключам). Методы доступа, соответствующие этому классу, должны реализовать эффективную последовательную обработку (физически смежный последовательный файл, связанные списки).

2. Получить уникальную запись. Требуется одна запись по значению первичного ключа. Для решения этой задачи ориентированы практически все индексные методы доступа: индексно-последовательный, индексно-произвольный, иерархические индексные файлы, Б-дерево). А также прямой метод доступа и хеширование.

3. Получить некоторые записи (0 % – X %). Для реализации таких запросов используются инвертированные файлы, мультисписки, индексы-соединения.

3.2. Индексно-последовательный метод доступа

Основное назначение этого метода – поиск уникальных записей по значению ключа (2-й класс запросов). Однако, в отличие от других индексных методов, реализуется достаточно эффективно последовательный доступ (1-й класс запросов).

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

Поиск записи

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

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

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

Дополнение записей

Определяется местоположение дополняемой записи в соответствии с возрастание первичного ключа. Если она не помещается в найденный блок, то последние записи, не поместившиеся в блок, перемещаются в область переполнения: отдельное пространство на диске. Там они не сортируются, а связываются в цепочку в соответствии с возрастанием первичного ключа: перемещенные записи становятся первыми в цепочке, соответствующей данному блоку. В данном случае используется стандартный прием в методах доступа – организация области переполнения. Кроме того, используется метод отведенного свободного пространства: в каждом блоке при первоначальной загрузке файла резервируется пустое пространство в конце блока (примерно 30 %). Такая процедура дополнения требует операций сопровождения основного файла: его периодическую перезагрузку.