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