Хеширование

МЕХАНИЗМЫ РАЗМЕЩЕНИЯ ДАННЫХ И ДОСТУПА К ДАННЫМ

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

Рассмотрим основные способы доступа к данным.

• Последовательная обработка области БД. Областью БД может быть файл или другое множество страниц. Последовательная обработка предполагает, что система последовательно просматривает страницы, пропускает пустые участки и выдаёт записи в физической последовательности их хранения.
• Доступ по ключу базы данных (КБД). КБД определяет местоположение записи в памяти ЭВМ. Зная его, система может извлечь нужную запись за одно обращение к памяти.
• Доступ по структуре. Эта разновидность доступа применяется для групповых отношений и позволяет перейти к предыдущему или следующему экземпляру группового отношения, к экземпляру-владельцу группового отношения или к списку подчинённых экземпляров.
• Доступ по первичному ключу. Первичный ключ идентифицирует записи внутри типа. Если система обеспечивает доступ по первичному ключу, то он (ключ) используется также при запоминании записи и, более того, его значение в этом случае обычно используется при размещении записи в памяти. Наиболее распространённые механизмы доступа по первичному ключу – индексирование и хеширование.

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

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

Хеширование таблицы полезно в следующих случаях:

• Большинство запросов обращаются по значению уникального ключа, например:

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

Хеширование не рекомендуется в следующих случаях:

• Большинство запросов выбирают строки в некотором интервале. Хеширование не даёт здесь преимуществ, т.к. строки не упорядочены (в отличие от индекса).
• Таблица быстро меняется и постоянно растёт.
• Большинство запросов просматривают таблицу целиком.
• Нельзя заранее выделить столько пространства памяти, сколько потребуется таблице в будущем.

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

Дата добавления: 2013-12-13