- •Содержание
- •Предисловие
- •Введение
- •1. Основные понятия баз данных
- •1.1. Банк данных и его компоненты
- •Пользователи
- •Прикладные
- •1.2. Модели данных
- •2. Целостность баз данных
- •Условие на значение “Парус” or “Волна” or “Лотос”
- •3. Внутренняя организация субд
- •3.1. Общие положения
- •3.2. Линейный список
- •3.3. Инвертированный список
- •3.4. Индексы
- •3.5. Хеширование
- •Область переполнения
- •3.6. Кластеризация
- •4. Распределенная обработка данных
- •4.1. Режимы работы с базой данных
- •Параллельный
- •4.2. Архитектура «клиент-сервер»
- •Приложения
- •4.3. Модели «клиент-сервер»
- •4.4. Управление распределенными данными
- •5. Восстановление баз данных
- •5.1. Транзакции
- •5.2. Журнал транзакций
- •5.3. Выполнение транзакций в многопользовательских системах
- •6. Защита баз данных
- •7. Основы проектирования реляционных баз данных
- •7.1. Этапы проектирования
- •7.2. Построение концептуальной модели предметной области
- •7.3. Логическое проектирование базы данных
- •7.4. Нормализация отношений
- •7.5. Автоматизированные технологии проектирования баз данных
- •Заключение
- •Библиографический список
3.2. Линейный список
Линейный (последовательный) список – последовательность записей базы данных, сформированная по некоторым логическим принципам. Например, в таблице, содержащей информацию о поступлении товаров в магазин, сведения о каждой поставке представляют собой записи, вводимые в базу данных в хронологическом порядке и размещаемые в физической памяти последовательно друг за другом (табл. 3.1):
Таблица 3.1
Сведения о поставках товаров в магазин
Номер накладной |
Название товара |
Артикул |
Количество |
Дата поставки |
37 |
Костюм |
500 |
50 |
10.12.05 |
54 |
Сапоги |
200 |
75 |
10.12.05 |
18 |
Туфли |
100 |
120 |
11.12.05 |
60 |
Костюм |
500 |
35 |
11.12.05 |
28 |
Костюм |
300 |
20 |
12.12.05 |
74 |
Костюм |
400 |
50 |
12.12.05 |
80 |
Туфли |
100 |
100 |
12.12.05 |
При поиске информации, соответствующей некоторым критериям (например, товаров с определенным названием или артикулом), линейный список необходимо просмотреть полностью от первой до последней записи. Это приводит к тому, что рассматриваемая структура хранения, обеспечивая оптимальные требования к минимальному объему выделяемой памяти на внешних устройствах, является неэффективной по быстродействию.
3.3. Инвертированный список
Инвертированные списки позволяют существенно ускорить процесс поиска необходимой информации по сравнению с линейными списками. Это достигается с помощью упорядочивания (сортировки) записей исходного списка по значениям данных в одном из неключевых полей. Инвертирование исходного списка можно выполнить для отдельных (частичное инвертирование) или всех (полное инвертирование) неключевых полей исходного списка.
Предположим, что значения номеров накладных в поле Номер накладной таблицы Сведения о поставках товаров в магазин (см. табл. 3.1) являются уникальными, т.е. данное поле является первичным ключом таблицы. Инвертированный список по полю Артикул будет выглядеть следующим образом (табл. 3.2):
Таблица 3.2
Сведения о поставках товаров в магазин
Номер накладной |
Название товара |
Артикул |
Количество |
Дата поставки |
18 |
Туфли |
100 |
120 |
11.12.05 |
80 |
Туфли |
100 |
100 |
12.12.05 |
54 |
Сапоги |
200 |
75 |
10.12.05 |
28 |
Костюм |
300 |
20 |
12.12.05 |
74 |
Костюм |
400 |
50 |
12.12.05 |
37 |
Костюм |
500 |
50 |
10.12.05 |
60 |
Костюм |
500 |
35 |
11.12.05 |
Полученный инвертированный список позволяет выполнять быстрый поиск информации по данным в поле Артикул, не требуя просмотра всех записей (например, при поиске сведений о товарах, артикулы которых менее 300, достаточно извлечь и рассмотреть только первые четыре записи).
Обеспечивая уменьшение времени выполнения запросов, инвертирование приводит к существенному увеличению объемов внешней памяти для хранения информации в результате ее дублирования. Это увеличение прямо пропорционально количеству полей, по которым производится инвертирование. Для частичного устранения данного недостатка применяется создание индексов.