Лекции / Л-9 - Методы доступа к данным

Основные свойства хеш-функции (2)

Второе требование является сложно выполнимым. Трудно подобрать такую хеш-функцию, которая для любого распределения значений ключа всегда выдавала бы разные адреса для разных значений.

Для реальных функций хеширования допускается совпадение значений функции h(K) для различных ключей.

Для разрешения неопределенности при совпадении адресов после вычислении h(K) используются

специальные методы.

Недостатки хеширования

Количество данных и распределение значений ключа должны быть известны заранее.

Записи обычно упорядочены по значению ключа, что приводит к дополнительным затратам при выполнении сортировки.

Преимущества хеширования

Преимущество – ускорение доступа к данным по значению ключа.

Обращение к данным происходит за одну операцию ввода-вывода, так как значение ключа с помощью хешфункции непосредственно преобразуется в адрес записи (адрес блока, в котором хранится запись).

При этом не нужны дополнительные структуры (типа индекса) и затраты памяти на их хранение.

Использование хеширования (1)

В таблице есть уникальный ключ, и большинство запросов обращается к записям по значению этого ключа:

SELECT <список выбора>

FROM <таблица>

WHERE unique_key = <значение>;

Значение, указанное в условии, хешируется.

По этому хеш-значению происходит прямой доступ к соответствующему блоку данных (обычно одно физическое чтение, если нет коллизий и запись помещается в одном блоке).

Использование хеширования (2)

Для неуникального хеш-ключа все записи с таким значением ключа помещаются в одном блоке, который также можно прочитать за один раз.

Таблица практически статична (редко обновляется).

Число записей и их средний размер можно определить заранее и сразу выделить под таблицу требуемое физическое пространство.

Хеширование не рекомендуется

Когда нельзя сразу выделить столько памяти, сколько требуется таблице. Если потребуется выделять таблице дополнительную память, эта память будет отведена под коллизионные страницы, что сильно ухудшит производительность (это следует из формулы, по которой рассчитывается адрес записи).

Большинство запросов выбирает записи в некотором интервале значений ключа. Хеширование не дает здесь преимуществ, так как записи обычно не упорядочены, и система использует последовательное чтение.

Кластеризация данных (1)

Кластеризация – хранение в одной области памяти таблиц, связанных внешними ключами (одна роди-

тельская таблица, одна/несколько подчиненных таблиц).

Для размещения записей используется значение внешнего ключа (все данные с одинаковым значением внешнего ключа будут в одном блоке данных – кластере).

Для таблиц ДЕТИ, ТРУДОВАЯ КНИЖКА, ОТПУСКА

внешним ключом будет первичный ключ Идентифи-

катор сотрудника таблицы СОТРУДНИКИ. Тогда при кластеризации все данные будут храниться в одном блоке данных.

Кластеризация данных (2)

Таблицы в кластере должны иметь общие столбцы, используемые для соединения (первичный ключ таблицы ТОВАРЫ и внешний ключ таблицы ПОСТАВКИ).

Кластерный ключ (КК) – поле (набор полей), общих для всех таблиц кластера.

Каждая таблица в кластере должна иметь поля, соответствующие типам и размерам полей КК.

Количество полей в КК ограничено (для Oracle – 16).

Некластеризованные и кластеризованные данные

Реализация кластеризации (1)

Совместное хранение данных: на одной странице или в одном блоке памяти хранятся данные из всех кластеризованных таблиц, имеющие одинаковое значение КК.

Физическая реализация: в начале страницы (блока) хранится запись из таблицы, для которой КК является первичным (уникальным), а вслед за ней располагаются записи из другой таблицы (таблиц), имеющие те же значения КК.

Фактически, данные хранятся в виде соединения таблиц по значениям КК. Соединение кластеризованных таблиц (по сравнению с раздельно хранимыми) в 3-6 раз быстрее.