Основы физической организации БД
Физическая организация БД
Факторы, влияющие на выбор физической организации БД
При выборе того или иного метода доступа учитываются следующие факторы:
1. Скорость поиска данных (главный фактор).
2. Скорость модификации данных.
3. Общий объем БД.
4. Реализация ограничений целостности на данные.
5. Обеспечение многопользовательского доступа к данным.
Перечисленные требования к физической организации БД являются противоречивыми (требуется компромисс).
Классификация методов доступа.
Выбор метода доступа зависит от пользовательских запросов.
Следовательно, классифицировать будем пользовательские запросы, и эту классификацию применим к методам доступа. В основе классификации – количество исходных записей, отнесенных к общему количеству записей.
1. Получить все или многие записи. При ответе на запрос требуется просмотреть от X % до 100 % записей. Величина X зависит от класса СУБД (Oracle: X @ 25 %) (осуществяется последовательный просмотр файлов БД без использования поиска по ключам). Методы доступа, соответствующие этому классу, должны реализовать эффективную последовательную обработку (физически смежный последовательный файл, связанные списки).
|
|
2. Получить уникальную запись. Требуется одна запись по значению первичного ключа. Для решения этой задачи ориентированы практически все индексные методы доступа: индексно-последовательный, индексно-произвольный, иерархические индексные файлы, Б-дерево). А также прямой метод доступа и хеширование.
3. Получить некоторые записи (0 % – X %). Для реализации таких запросов используются инвертированные файлы, мультисписки, индексы-соединения.
Основное назначение этого метода – поиск уникальных записей по значению ключа (2-й класс запросов). Однако, в отличие от других индексных методов, реализуется достаточно эффективно последовательный доступ (1-й класс запросов).
Все записи в основном файле упорядочены по возрастанию первичного ключа. Основной файл разбит на блоки фиксированной длины, содержащие целое количество записей. Для каждого блока формируется запись в индексном файле, содержащая значение ключа последней записи блока (так как упорядочены по возрастанию – наибольшее значение в блоке) и адрес начала блока. Индексный файл имеет аналогичную блочную структуру.
Поиск записи
Поиск в индексном файле: последовательный просмотр блоков индексного файла со сравнением искомого значения ключа с ключами в индексном файле. После обнаружения ключа в файле больше искомого – переход на соответствующий блок основного файла и поиск записи в блоке.
|
|
Индексно-последовательная организация является эффективной по памяти (короткий индекс). Использование метода доступа ISAM для IBM 360-370 позволяет сделать эффективным поиск данных. Один блок – одна дорожка устройства, последовательность друг за другом идущих блоков – цилиндр устройства, то есть последовательный просмотр осуществляется без перемещения считывающих головок.
Проблемы использования этого метода доступа появляются при необходимости модификации файла: самая трудоемкая операция – добавление новой записи.
Дополнение записей
Определяется местоположение дополняемой записи в соответствии с возрастание первичного ключа. Если она не помещается в найденный блок, то последние записи, не поместившиеся в блок, перемещаются в область переполнения: отдельное пространство на диске. Там они не сортируются, а связываются в цепочку в соответствии с возрастанием первичного ключа: перемещенные записи становятся первыми в цепочке, соответствующей данному блоку. В данном случае используется стандартный прием в методах доступа – организация области переполнения. Кроме того, используется метод отведенного свободного пространства: в каждом блоке при первоначальной загрузке файла резервируется пустое пространство в конце блока (примерно 30 %). Такая процедура дополнения требует операций сопровождения основного файла: его периодическую перезагрузку.