Область переполнения
Адрес (номер страницы) | Номер накладной | Название товара | Арти- кул | Коли-чество | Дата поставки | Ссылка на синонимы |
5 00 | 29 | Брюки | 750 | 90 | 13.12.05 |
|
501 | 96 | Сапоги | 220 | 120 | 13.12.05 |
|
5 02 | 40 | Костюм | 300 | 35 | 14.12.05 | 5 00 |
503 |
|
|
|
|
|
|
504 |
|
|
|
|
|
|
505 |
|
|
|
|
|
|
Рис. 6. Пример хеширования с областью переполнения
Стратегия разрешения коллизий с помощью свободного замещения
В рамках данной стратегии память не разделяется на отдельные области. Если в базу данных вводится новая запись и значение хеш-функции соответствует адресу пустой страницы, запись помещается на этой странице и становится первой в цепочке синонимов. Когда возникает коллизия, новая запись размещается на первом свободном месте в памяти. С помощью ссылок создается цепочка синонимов, при этом используются те же принципы, что и в стратегии с областью переполнения.
Технологии поиска и удаления записей в обеих стратегиях также аналогичны.
При реализации стратегии разрешения коллизий с помощью свободного замещения может возникнуть ситуация, когда запись, размещаемая на первой свободной странице в памяти, занимает место, на которое позднее будет претендовать запись, значение хеш-функции которой соответствует адресу этой страницы. В такой ситуации запись, занимающая свое место «незаконно», перемещается на другую страницу, при этом изменяются ссылки в цепочке синонимов.
Основной проблемой хеширования является сложность выбора оптимальной хеш-функции. При выполнении данной работы анализируются размеры записей и страниц внешней памяти, вероятное распределение получаемых адресов. Неудачно выбранная хеш-функция может вызвать неравномерное распределение записей в памяти или формирование слишком длинных цепочек синонимов.
Весьма сложной является ситуация, когда количество запоминаемых записей больше, чем предполагалось, и необходимо увеличить место в памяти для их хранения или размеры таблицы хеширования. В этой ситуации потребуется выполнить полное повторное хеширование.
Следует иметь в виду, что хеширование позволяет организовать быстрый поиск информации только по одному полю, данные которого использовались для хеширования. Нельзя хранить записи в порядке, определяемом несколькими хеш-функциями.
Несмотря на отмеченные недостатки хеширования, данный способ организации хранения и быстрого извлечения необходимых данных широко применяется, в первую очередь в объектно-ориентированных базах данных [ 12 ].
- Содержание
- Предисловие
- Введение
- 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. Автоматизированные технологии проектирования баз данных
- Заключение
- Библиографический список