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

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

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

Хэш-организация

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

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

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

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

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

операция

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

    Адрес ковша = h (K)

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

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

Переполнение ковша

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

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

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

Линейное зондирование

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

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

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

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

организация

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

операция

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

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

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

  • Вставка - Вычислить адрес корзины

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

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

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