Глава 12. Первичные методы доступа! последовательная обработка
12.1. Введение
Решения, которые принимаются на этапе физического проектирования, в отличие от решений на этапе проектирования реализации, должны учитывать вопросы, связанные с организацией путей доступа. На концептуальном уровне сущности и связи описываются в терминах ассоциаций данных без учета способа организации доступа. При проектировании СУБД-ориентированной логической структуры полученная ранее информационная структура усовершенствуется с тем, чтобы учесть различные системные ограничения и минимизировать длины путей доступа <для всего множества приложений пользователей. Информационная структура с помощью достаточно простых преобразований превращается в СУБД-ориентированную логическую структуру базы данных, при этом сущности преобразуются непосредственно в записи, а связи между объектами формируют основу навигационных путей доступа. Конечно, такая организация работ по созданию баз данных серьезно ограничивает гибкость концептуального проектирования. Тем не менее введение в рассмотрение связей между сущностями создает некоторые отправные точки для изучения путей доступа, хотя необходимо учесть еще много других факторов, которые действительно позволяют спроектировать новые структуры базы данных, существенно отличающиеся от первоначальной концептуальной модели.
Проектирование логической структуры базы данных (или схемы) в основном базируется на минимизации длин путей доступа и, следовательно, тесно связано с конечной физической структурой. Физическая структура предполагает, что в схеме определен базис для навигационного или другого метода доступа; выбор конкретного варианта доступа производится в соответствии с принятыми критериями эффективности. Таким образом, принятые в качестве предварительной оценки относительной эффективности системы оценки количества обращений к логическим записям (LRA) и объема передаваемой информации преобразуются в оценки количества обращений к физическим блокам и в конечном итоге в оценки времени ввода-вывода, рассматриваемые как дополнительные меры относительной эффективности. Время отклика, включающее время обслуживания ввода-вывода и ряд других компонентов, может служить оценкой абсолютной эффективности, которая подлежит подтвержде-
Оглавление
Глава 12. Первичные методы доступа: последовательная обработка ... 5
12.1. Введение......................R
12.1.1. Методы доступа и их определение........о
12.1.2. Классификация методов доступа.........7
122 Обработка данных при физически последовательной организа-
зации: ПОЛУЧИТЬ ВСЕ, ПОЛУЧИТЬ МНОГИЕ.....9
12.2.1. Поиск при физически последовательной организации данных .................... Ю
12.2.2. Внесение изменений при физически последовательной организации ...................13
12.2.3. Выбор параметров физически последовательной организации . ...................'5
1 12.3. Обработка данных при связанной последовательной организации 20
12.3.1. Поиск при связанной последовательной организации 20
12.3.2. Внесение изменений при связанной последовательной организации данных...............21
12.3.3 Выбор параметров при связанной последовательной организации данных................24
12.3.4, Объем памяти для последовательных структур ... 28
12.4. Общие затраты на получение ответа..........29
Глава 13. Первичные методы доступа: произвольная обработка . ... 34
13.1. Прямой доступ...................34
13.2. Хеширование идентификатора (произвольный доступ) .... 38
13.2.1. Функция хеширования.............41
13.2.2. Методы обработки переполнения.........44
13.2.3. Характеристики производительности........58
13.2.4. Таблицы хеширования . . . \.........60
13.3. Метод доступа с полным индексом (индексно-произвольный метод доступа)....................63
13.4. Индексно-последовательный метод доступа........68
13.4.1. Выборка данных из индексно-последовательного файла 71
13.4.2. Обновление индексно-последовательного файла .... 84
13.4.3. Объем памяти для индексно-последовательной организации.....................86
13.4.4. Сравнительный анализ индексно-последовательной организации ...................87
Пяава 14. Первичные методы доступа: деревья поиска и произвольная
обработка.....................91
14,1. Деревья бинарного поиска..............91
14.1.1. Производительность выборки ...'.......95
14.1.2. Производительность обновления .......... 97
14.1.3. Объем памяти ..............' \Q-J
14.2. В-дерево............'...'...... 107
14.2.1. Производительность выборки...........112
14.2.2. Производительность обновления......'...'. 116
14.2.3. Объем памяти................' .' 125
14.2.4. В*-дерево ...........'...... 126
14.2.5. В "-дерево с префиксом.............132
14.3. TRIE-структуры ...............'.'.'. 134
14.3.1. Производительность выборки...........' 137
14.3.2. Производительность обновления.......• • .' 138
14.3.3. Объем памяти.................J40
14.3.4. Сравнение производительности TRIE-структуры с В-де-ревом ................... 14,
Глава 15. Вторичные методы доступа............. . 14;
15.1. Введение ......................14;
15.2. Мультисписковый файл................14!
15.2.1. Производительность выборки при обработке запросов .14!
15.2.2. Производительность обобщенного обновления .... 15)
15.2.3. Объем памяти . . ...............15;
. 15.2.4. Секционный мультисписок............15'
15.3. Инвертированный файл ...............15(
15.3.1. Производительность выборки при обработке запросов 15!
15.3.2. Производительность обобщенного обновления .... 161
15.3.3. Объем памяти.................161
15.3.4. Сравнительная оценка производительности вторичных методов доступа................16;
15.3.5. Секционный инвертированный файл........16!
15.4. Двусвязанное дерево.................16!
15.4.1. Производительность выборки при обработке запросов 17--
15.4.2. Производительность обобщенного обновления . . . .171
15.4.3. Объем памяти.................17!
15.4.4. Сравнение двусвязанного дерева с инвертированным и
\ мультисписковым файлами............17!
15.5. Способы организации инвертированного индекса......18.'
Глава 16. Выбор вторичного индекса...............18(
16.1. Многоключевое (составное) индексирование.......18!
16.2. Классификация вторичных методов........... 19.'
16.3. Проблема выбора индекса..............19!
16.4. Выбор оптимального вторичного индекса.........201
Часть V. Специальные вопросы проектирования
Глава 17. Реорганизация...................20(
17.1. Введение....................' . 201
17.2. Стратегии реорганизации.............' . . 21(
17.3. Роль администратора базы данных........... 21,'
17.4. Когда проводить реорганизацию: эвристический подход . . .21
17.5. Реструктурирование .................22
17.5.1. Сетевое реструктурирование...........22.'
17.5.2. Инженерные подходы к реструктурированию.....22'
Глава 18. Распределенные базы данных: обзор . . ........23'
18.1. Введение .....................23<
18.2. Архитектура распределенных СУБД...........23f
18.3. Проблемы проектирования распределенных баз данных ... 24
18.3.1. Стратегии распределения данных ......... 24.'
18.3.2. Распределение сетевого справочника данных .... 24'
18.3.3. Однородные и неоднородные системы баз данных ... 24!
18.4. Основы проектирования распределенной базы данных ... 25
18.4.1. Расчленение базы данных............25,'
18.4.2. Размещение базы данных ........... . 25,'
18.5. Дифференциальные файлы ..............251
Приложение Б
Упражнения по теме «Физическое проектирование баз данных» , ... 267
Приложение В
Слисок обозначений......................2?
Толковый словарь.......................28<
Литература.........................30'
Предметный указатель....................311
