СУБД - Хеширование

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

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

Организация хеширования

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

• Hash Function - хеш-функция, h, функция отображения, которая отображает весь набор ключей поиска Kпо адресу, по которому размещены фактические записи. Это функция от ключей поиска до адресов корзины.

Статическое хеширование

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

Операция

• Insertion - Когда требуется ввести запись с использованием статического хеша, хеш-функция h вычисляет адрес корзины для ключа поиска K, где будет храниться запись.

  Адрес сегмента = h (K)

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

• Delete - Это просто поиск с последующей операцией удаления.

Ковш переполнен

Состояние переполнения ковша известно как collision. Это фатальное состояние для любой статической хеш-функции. В этом случае можно использовать цепочку переполнения.

• Overflow Chaining- Когда сегменты заполнены, новое ведро выделяется для того же результата хеширования и связывается после предыдущего. Этот механизм называетсяClosed Hashing.

• Linear Probing- Когда хеш-функция генерирует адрес, по которому уже хранятся данные, ей выделяется следующая свободная корзина. Этот механизм называетсяOpen Hashing.

Динамическое хеширование

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

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

Организация

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

Операция

• Querying - Посмотрите на значение глубины хэш-индекса и используйте эти биты для вычисления адреса корзины.

• Update - Выполните запрос, как указано выше, и обновите данные.

• Deletion - Выполните запрос, чтобы найти нужные данные и удалить их.

• Insertion - Вычислить адрес ведра

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

Хеширование неблагоприятно, если данные организованы в определенном порядке и для запросов требуется диапазон данных. Когда данные дискретны и случайны, лучше всего работает хэш.

Алгоритмы хеширования более сложны, чем индексация. Все операции хеширования выполняются в постоянное время.