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

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

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

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

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

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

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

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

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

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

операция

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

  Адрес корзины = h (K)

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

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

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

Адрес корзины = h (K)

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

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

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

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

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

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

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

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

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

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

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

организация

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

операция

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

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

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

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

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

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

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

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

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

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

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