Хеширование в СУБД: методы статического и динамического хеширования
Фиона Браун
⚡ Умное резюме
Хэширование в СУБД — это метод, который вычисляет местоположение записи на диске непосредственно по её ключу, без обхода индекса. Хэш-функция сопоставляет ключи поиска с сегментами данных, а статическое или динамическое хэширование управляет ростом этих сегментов.
Что такое хеширование в СУБД?
В СУБД хеширование — это метод прямого поиска нужных данных на диске без использования индексной структуры. Метод хеширования используется для индексирования и извлечения элементов в базе данных, поскольку поиск конкретного элемента с помощью более короткого хешированного ключа происходит быстрее, чем с помощью его исходного значения. Данные хранятся в виде блоков данных, адрес которых генерируется с помощью хеш-функции; область памяти, где хранятся эти записи, называется блоком данных. блок данных или сегмент данных.
Зачем нам хеширование?
Вот ситуации в СУБД, в которых необходимо применять метод хеширования:
- Для огромной структуры базы данных сложно выполнить поиск по всем значениям индекса на всех их уровнях, а затем добраться до целевого блока данных, чтобы получить нужные данные.
- Хэширование используется для индексирования и извлечения элементов в базе данных, поскольку поиск конкретного элемента с использованием более короткого хэшированного ключа происходит быстрее, чем с использованием исходного значения.
- Хэширование — идеальный метод для вычисления непосредственного местоположения записи данных на диске без использования индексной структуры.
- Это также полезный метод реализации словарей.
Важные термины в хешировании
Вот важные термины, используемые в хешировании:
- Корзина данных: Блоки данных — это ячейки памяти, где хранятся записи. Их также называют единицами хранения.
- Условные обозначения: a ключ СУБД Это атрибут или набор атрибутов, которые помогают идентифицировать строку (кортеж) в отношении (таблице).
- Функция хеширования: картаping функция, которая сопоставляет весь набор поисковых ключей с адресом, где фактически находятся записи.
- Линейное зондирование: Фиксированный интервал между проверками. В этом методе для записи новой записи используется следующий доступный блок данных, а не перезаписывается старая запись.
- Квадратичный зонд: Это помогает определить новый адрес корзины путем сложения последовательных значений квадратичного многочлена с начальным значением, полученным в результате исходных вычислений.
- Хэш-индекс: Адрес блока данных. Хэш-функция может быть простой или сложной математической функцией.
- Double Хеширование: Метод, используемый в хеш-таблицах для разрешения коллизий путем применения второй хеш-функции.
- Переполнение ведра: Состояние переполнения корзины называется коллизией. Это фатальная стадия для любой статической хеш-функции.
Типы методов хеширования
В системах управления базами данных (СУБД) используются два основных типа методов хеширования:
- Статическое хеширование
- Динамическое хеширование
Основное различие между ними заключается в том, является ли количество ведер фиксированным, как объясняется в следующих двух разделах.
Статическое хеширование
При статическом хешировании результирующий адрес хранилища данных всегда остается неизменным.
Следовательно, если вы сгенерируете адрес, скажем, для Идентификатор студента = 10 используя хеш-функцию мод(3), результирующий адрес сегмента всегда будет 1Поэтому вы не увидите никаких изменений в адресе хранилища.
Следовательно, при статическом методе хеширования количество блоков данных в памяти всегда остается постоянным.
Статические хеш-функции
- Вставка записи: Когда необходимо вставить новую запись в таблицу, для неё генерируется адрес с использованием её хеш-ключа. После генерации адреса запись сохраняется в указанном месте.
- Поиск: Когда необходимо получить доступ к записи, та же хеш-функция используется для получения адреса хранилища, где хранятся данные.
- Удалить запись: Используя хеш-функцию, вы сначала получаете запись, которую хотите удалить, а затем удаляете запись по этому адресу в памяти.
Статическое хеширование, в свою очередь, подразделяется на:
- Открытое хеширование
- Закрытое хеширование
Открытое хеширование
В методе открытого хеширования вместо перезаписи старой записи используется следующий доступный блок данных для записи новой записи. Этот метод также известен как линейное зондирование.
Например, A2 — это новая запись, которую вы хотите вставить. Хэш-функция генерирует адрес 222, но он уже занят другим значением. Поэтому система ищет следующий сегмент данных, 501, и присваивает ему адрес A2.
Закрытое хеширование
В методе закрытого хеширования, когда корзины заполняются, для того же хеша выделяется новая корзина, и результат связывается с предыдущей.
Динамическое хеширование
Динамическое хеширование предлагает механизм, в котором блоки данных добавляются и удаляются динамически и по запросу. В этом методе хеширования хеш-функция помогает создать большое количество значений, а структура увеличивается или уменьшается по мере поступления данных. Это делает его идеальным решением для таблиц, размер которых невозможно предсказать заранее, где статическое хеширование либо приведет к нерациональному использованию пространства, либо к переполнению.
Разница между упорядоченным индексированием и хешированием.
Ниже приведены основные различия между индексированием и хешированием:
| Параметры | Упорядоченное индексирование | хеширования |
|---|---|---|
| Сохранение адреса | Адреса в памяти сортируются по ключевому значению, называемому первичным ключом. | Адреса всегда генерируются с использованием хеш-функции для значения ключа. |
| Эффективности | По мере увеличения объема данных это значение может уменьшаться, поскольку данные хранятся в отсортированном виде, и каждое вставка, удаление или обновление изменяет их порядок. | Наилучшая производительность достигается при постоянном добавлении и удалении данных. Для больших баз данных поддержание хэш-файлов становится более затратным. |
| Использовать для | Предпочтительный вариант для извлечения данных в заданном диапазоне. | Идеально подходит для извлечения конкретной записи на основе поискового ключа и показывает хорошие результаты только в том случае, если хеш-функция применяется к поисковому ключу. |
| Управление памятью | В результате операций удаления и обновления образуется множество неиспользуемых блоков данных, которые невозможно освободить для повторного использования, поэтому требуется регулярное техническое обслуживание. | В статическом и динамическом хешировании управление памятью всегда осуществляется автоматически, а переполнение корзины обрабатывается автоматически, что расширяет возможности статического хеширования. |
Короче говоря, выбирайте упорядоченно. индексация для запросов по диапазону значений и хеширования для точного поиска по ключу.
Что такое столкновение?
Коллизия хешей — это состояние, при котором результирующие хеши двух или более элементов в наборе данных ошибочно соответствуют одному и тому же месту в нем. хеш-таблица.
Как справиться с коллизией хеширования
Существует два метода, которые можно использовать для предотвращения коллизии хешей:
- Повторное обсуждение: Этот метод вызывает дополнительную хеш-функцию, которая применяется непрерывно до тех пор, пока не будет найдено свободное место, куда можно поместить запись.
- Цепочка: Метод цепочек создает связанный список элементов, ключи которых хешируются в одно и то же значение. Этот метод требует дополнительного поля связи в каждой позиции таблицы.
