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, достаточно извлечь и рассмотреть только первые четыре записи).
Обеспечивая уменьшение времени выполнения запросов, инвертирование приводит к существенному увеличению объемов внешней памяти для хранения информации в результате ее дублирования. Это увеличение прямо пропорционально количеству полей, по которым производится инвертирование. Для частичного устранения данного недостатка применяется создание индексов.
- Содержание
- Предисловие
- Введение
- 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. Автоматизированные технологии проектирования баз данных
- Заключение
- Библиографический список