2 Проектирование структур баз данных! В 2-х кн. Кн. 3. Пер. с англ. —М.: Мир. 1985. 320 с., ил.
Труд американских ученых посвящен проблеме проектирования баз данных, В русском переводе выпускается в 2-х книгах.
В книге 2 большое внимание уделено методам доступа и сравнительному анализу * эффективности, а также вопросам реорганизации баз данных. Рассматриваются архитектура систем управления распределенными базами данных и стратегии распределения данных.
Для специалистов в области вычислительной техники.
Глава 12. Первичные методы доступа: последовательная обработка
12.1. Введение
решения, которые принимаются на этапе физического проектирования, в отличие от решений на этапе проектирования реализации, должны учитывать вопросы, связанные с организацией путей доступа. На концептуальном уровне сущности и связи описываются в терминах ассоциаций данных без учета способа организации доступа. При проектировании СУБД-ориентированной логической структуры полученная ранее информационная структура усовершенствуется с тем, чтобы учесть различные системные ограничения и минимизировать длины путей доступа для всего множества приложений пользователей. Информационная структура с помощью достаточно простых преобразований превращается в СУБД-ориентированную логическую структуру базы данных, при этом сущности преобразуются непосредственно в записи, а связи между объектами формируют основу навигационных путей доступа. Конечно, такая организация работ по созданию баз данных серьезно ограничивает гибкость концептуального проектирования. Тем не менее введение в рассмотрение связей между сущностями создает некоторые отправные точки для изучения путей доступа, хотя необходимо учесть еще много других факторов, которые действительно позволяют спроектировать новые структуры базы данных, существенно отличающиеся от первоначальной концептуальной модели.
Проектирование логической структуры базы данных (или схемы) в основном базируется на минимизации длин путей доступа и, следовательно, тесно связано с конечной физической структурой. Физическая структура предполагает, что в схеме определен базис для навигационного или другого метода доступа; выбор конкретного варианта доступа производится в соответствии с принятыми критериями эффективности. Таким образом, принятые в качестве предварительной оценки относительной эффективности системы оценки количества обращений к логическим записям (LRA) и объема передаваемой информации преобразуются в оценки количества обращений к физическим блокам и в конечном итоге в оценки времени ввода-вывода, рассматриваемые как дополнительные меры относительной эффективности. Время отклика, включающее время обслуживания ввола-вывода и ряд других компонентов, может служить оцен-011 абсолютной эффективности, которая подлежит подтвержде-
Оглавление
Глава 12. Первичные методы доступа: последовательная обработка ... 5
12.1. Введение ..................... 5
12.1.1. Методы доступа и их определение...... . , 6
12.1.2. Классификация методов доступа......... 7
122 Обработка данных при физически последовательной организа-
зации: ПОЛУЧИТЬ ВСЕ, ПОЛУЧИТЬ МНОГИЕ.....9
12.2.1. Поиск при физически последовательной организации данных .................... Ю
12.2.2. Внесение изменений при физически последовательной организации ..................13
12.2.3. Выбор параметров физически последовательной организации ....................15
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. Объем памяти ................107
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. Объем памяти................. 140
14.3.4. Сравнение производительности TRIE-структуры с В-де-ревом ................... 141
Глава 15. Вторичные методы доступа............. 1431
15.1. Введение..............т....... Щ
15.2. Мультисписковый файл................ »451
15.2.1. Производительность выборки при обработке запросов 14&
15.2.2. Производительность обобщенного обновления .... 151
15.2.3. Объем памяти................. 153,
15.2.4. Секционный мультисписок............ 154:
15.3. Инвертированный файл ............... 156
15.3.1. Производительность выборки при обработке запросов 158
15.3.2. Производительность обобщенного обновления .... 161
15.3.3. Объем памяти................. 162
15.3.4. Сравнительная оценка производительности вторичных методов доступа................ 163
15.3.5. Секционный инвертированный файл........ 165
15.4. Двусвязанное дерево................. 169
15.4.1. Производительность выборки при обработке запросов 174
15.4.2. Производительность обобщенного обновления .... 176
15.4.3. Объем памяти................. 178
15.4.4. Сравнение двусвязанного дерева с инвертированным и мультисписковым файлами............ 179
15.5. Способы организации инвертированного индекса...... 183
Глава 16. Выбор вторичного индекса............... 189J
16.1. Многоключевое (составное) индексирование ....... Ш
16.2. Классификация вторичных методов........... 193
16.3. Проблема выбора индекса.............. 198
16.4. Выбор оптимального вторичного индекса......... 202
Часть V. Специальные вопросы проектирования
Глава 17. Реорганизация....................208
17.1. Введение .....................208
17.2. Стратегии реорганизации...............21(
17.3. Роль администратора базы данных............21!
17.4. Когда проводить реорганизацию: эвристический подход . . .21'
17.5. Реструктурирование .................22
17.5.1. Сетевое реструктурирование...........22!
17.5.2. Инженерные подходы к реструктурированию.....22
Глава 18. Распределенные базы данных: обзор..........234
18.1. Введение .....................234
18.2. Архитектура распределенных СУБД...........238
18.3. Проблемы проектирования распределенных баз данных , , .241
18.3.1. Стратегии распределения данных.........242
18.3.2. Распределение сетевого справочника данных .... 248
18.3.3. Однородные и неоднородные системы баз данных . . . 249
18.4. Основы проектирования распределенной базы данных . . . 251
18.4.1. Расчленение базы данных............253
18.4.2. Размещение базы данных............255
18.5. Дифференциальные файлы ..............258
Приложение Б
Упражнения по теме «Физическое проектирование баз данных» , . . . 267
Приложение В
Список обозначений......................279
Толковый словарь........................284
Литература......................... 300
Предметный указатель....................316
Цена: 150руб.
