3.5. Хеширование
Хеширование (Hashing) – алгоритмическое преобразование значений некоторого поля записей (первичного ключа или любого другого поля) в адреса их размещения на внешнем носителе.
При вводе данных СУБД вычисляет адрес страницы, на которой будет храниться запись, и заносит запись на эту страницу. При выполнении запросов реализуются аналогичные расчеты адреса страницы с последующим чтением записей с этой страницы. Достоинством такого метода является быстрый прямой доступ к данным. При этом время доступа практически не зависит от количества хранимых записей.
Рассмотрим технологию хеширования на примере данных, приводимых в табл. 3.1. Используем для вычисления адресов страниц значения данных в поле первичного ключа таблицы Номер накладной: 18, 28, 37, 54, 60, 74, 80. Предположим, что на каждой странице внешней памяти можно разместить только одну запись.
Номера накладных представляют собой целые двузначные числа. Поэтому если использовать номера накладных в качестве адресов страниц, для организации хранения информации потребуется 99 страниц с адресами от 01 до 99. Очевидно, что это нерационально, так как записей в исходной таблице всего семь и абсолютное большинство страниц останутся пустыми (приводимые рассуждения будут более убедительными, если значения данных, используемые для хеширования, пятизначные или шестизначные числа).
По указанной причине адреса страниц вычисляются с помощью специальной хеш-функции. Используем в качестве адресов страниц остаток от деления каждого значения номера накладной на простое натуральное число (например, 11), называемое сверткой ключа (обычно хеш-функции имеют более сложный вид) (табл. 3.6):
Таблица 3.6
Сведения о поставках товаров в магазин
Номер накладной | Название товара | Артикул | Количество | Дата поставки | Адрес (номер страницы) |
37 | Костюм | 500 | 50 | 10.12.05 | 4 |
54 | Сапоги | 200 | 75 | 10.12.05 | 10 |
18 | Туфли | 100 | 120 | 11.12.05 | 7 |
60 | Костюм | 500 | 35 | 11.12.05 | 5 |
28 | Костюм | 300 | 20 | 12.12.05 | 6 |
74 | Костюм | 400 | 50 | 12.12.05 | 8 |
80 | Туфли | 100 | 100 | 12.12.05 | 3 |
С помощью выполненного хеширования записи размещаются на семи страницах внешней памяти с адресами от 00 до 10.
Рассмотренный пример иллюстрирует и недостатки хеширования:
Страницы с записями во внешней памяти могут располагаться неравномерно, с различным количеством пустых страниц между ними.
Возможно совпадение рассчитанных адресов страниц для двух или нескольких записей (например адреса, вычисленные для номеров накладных 18, 29, 40, будут равны одному числу – семи).
Совпадение вычисленных адресов называется коллизией, значения данных, для которых получены одинаковые адреса – синонимами.
Существует много стратегий разрешения коллизий, но основные из них две:
а) с областью переполнения;
б) свободного замещения.
Стратегия разрешения коллизий с помощью области переполнения
Область хранения разбивается на две части: основную область и область переполнения (рис. 6).
При вводе в базу данных новой записи вычисляется значение хеш-функции, которое используется для определения места расположения страницы в основной области памяти. Например, если номер накладной равен 12, запись будет размещена на странице с адресом 1 (см. обозначения курсивом на рис. 6).
Когда страница с полученным адресом занята и возникает коллизия, новая запись заносится на первое свободное место в области переполнения. Например, запись с номером накладной 29, следовательно, значением хеш-функции, равным 7, будет размещена по адресу 500. В записи-синониме, которая находится в основной области, делается ссылка на адрес записи, размещаемой в области переполнения. В ситуациях повторения коллизий (номер накладной равен 40, значение хеш-функции – 7) вновь вводимая запись помещается на свободное место в области переполнения (например, если страница с номером 501 занята, по адресу 502). Она становится второй в цепочке синонимов (этим обеспечивается сокращение времени на размещение новых записей) с помощью изменения ссылок на адреса синонимов (см. рис. 6).
При поиске нужной записи вычисляется значение ее хеш-функции, указывающее на адрес страницы в основной памяти. Если эта запись не является искомой, последовательно просматривается цепочка синонимов до получения необходимого результата. Очевидно, что скорость поиска существенно зависит от длины цепочки синонимов. Считается, что в цепочке не должно быть более 10 синонимов [ 4 ].
При удалении записи в основной области памяти на ее место перемещается вторая запись в цепочке синонимов, при этом все ссылки на синонимы в цепочке сохраняются. Если удаляется запись в области переполнения, изменяется адрес ссылки на следующий синоним в записи, предшествующей удаляемой записи.
Основная область
Адрес (номер страницы) | Номер накладной | Название товара | Арти- кул | Коли-чество | Дата поставки | Ссылка на синонимы |
0 |
|
|
|
|
|
|
1 | 12 | Сапоги | 150 | 150 | 13.12.05 |
|
2 |
|
|
|
|
|
|
3 | 80 | Туфли | 100 | 100 | 12.12.05 |
|
4 | 37 | Костюм | 500 | 50 | 10.12.05 |
|
5 | 60 | Костюм | 500 | 35 | 11.12.05 |
|
6 | 28 | Костюм | 300 | 20 | 12.12.05 |
|
7 | 18 | Туфли | 100 | 120 | 11.12.05 | 5 02 |
8 | 74 | Костюм | 400 | 50 | 12.12.05 | 5 01 |
9 |
|
|
|
|
|
|
10 | 54 | Сапоги | 200 | 75 | 10.12.05 |
|
- Содержание
- Предисловие
- Введение
- 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. Автоматизированные технологии проектирования баз данных
- Заключение
- Библиографический список