Расширяемое хеширование

Метод расширяемого хеширования (extendable hashing) представляет собой изящный вариант основного метода хеширования, позволяющий устранить проблемы хеширования при увеличении размеров хешированного файла (увеличение количества коллизий и среднего времени доступа). В действительности, расширяемое хеширование гарантирует, что количество операций доступа к диску, необходимых для поиска определенной записи, никогда не превышает двух и обычно сводится только к одной операции, независимо от того, какого размера достигает сам файл. (Поэтому данный метод гарантирует также, что никогда не возникнет потребность в реорганизации файла.)

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

Схема хеширования

1. Допустим, что основной функцией хеширования является h, а значение первичного ключа некоторой конкретной записи r равно к. Хеширование значения к (т.е. вычисление выражения h(к)) приводит к получению значения s, называемого псевдоключом (pseudokey) записи к. Псевдоключи не интерпретируются непосредственно как адреса, а вместо этого применяются для косвенного поиска адресов хранения, как описано ниже.
2. Файл имеет связанный с ним каталог, который также хранится на диске. Каталог состоит из заголовка, содержащего значение d (сокращение от depth — глубина каталога), наряду с 2^d указателями. Указатели указывают на страницы с данными, содержащими фактические записи (на каждой странице имеется много записей). Таким образом, каталог с глубиной d позволяет управлять файлом с максимальным размером, составляющим 2^d отдельных страниц с данными.
   

   Пример применения способа расширяемого хеширования
3. Если ведущие d битов псевдоключа рассматриваются как двойное целое число без знака b, то i-й указатель в каталоге (1 < i < 2^d) указывает на страницу, содержащую все записи, для которых b принимает значение i-l. Иными словами, первый указатель указывает на страницу, содержащую все записи, для которых b состоит из одних нулей, второй указатель указывает на страницу, для которой b равно 0. .. 01, и т.д. (Обычно все эти 2^d указателя не являются различными; это означает, что количество различных страниц с данными, как правило, меньше чем 2^d, как показано на рис.) Поэтому, чтобы найти запись, имеющую значение первичного ключа к, необходимо хешировать к для определения псевдоключа s и взять первые d битов этого псевдоключа; если эти биты имеют числовое значение i-l, осуществляется переход к i-му указателю в каталоге (первая операция доступа к диску) и переход по этому указателю к странице, содержащей требуемую запись (вторая операция доступа к диску). Примечание: На практике этот каталог обычно остается достаточно небольшим для того, чтобы его можно было почти все время хранить в оперативной памяти. Поэтому упомянутые "две" операции доступа к диску обычно сводятся к одной.
4. Каждая страница с данными имеет также заголовок, указывающий локальную глубину р этой страницы (р < d). Предположим, например, что d равно 3 и первый указатель в каталоге (указатель 000) указывает на страницу, для которой локальная глубина р равна 2. В данном случае локальная глубина 2 означает, что эта страница содержит не только все записи с псевдоключами, начинающимися с 000, но и содержит все записи с псевдоключами, начинающимися с 00 (т.е. теми, которые начинаются с 000, а также теми, которые начинаются с 001). Иными словами, указатель каталога 001 также указывает на эту страницу (см. рис).
5. Теперь предположим, что страница с данными 000 заполнена и нужно вставить новую запись, имеющую псевдоключ, который начинается с 000 (или с 001). В этот момент указанная страница разделяется на две; это означает, что из пула свободных страниц берется новая, пустая страница, а все записи 001 изымаются из старой страницы и переносятся в новую. Указатель 001 в каталоге корректируется таким образом, чтобы он указывал на новую страницу (указатель 000 все еще указывает на старую страницу). Локальная глубина р для каждой из этих двух страниц теперь будет равна 3, а не 2.
6. Теперь допустим, что страница с данными, соответствующая начальной строке битов 000, снова заполняется и должна быть опять разделена. Существующий каталог не позволяет обеспечить такое разделение, поскольку локальная глубина разделяемой страницы уже равна глубине каталога. Поэтому размер каталога удваивается; это означает, что значение d увеличивается на единицу и каждый указатель заменяется парой смежных, идентичных указателей. Теперь появляется возможность разделить страницу с данными; записи 0000 остаются на старой странице, а записи 0001 перемещаются на новую страницу; первый указатель в каталоге остается неизменным (т.е. по-прежнему указывает на старую страницу), а второй указатель корректируется таким образом, чтобы он указывал на новую страницу. Следует отметить, что операция удваивания размера каталога требует относительно небольших затрат времени, поскольку она не связана с доступом к какой-либо из страниц с данными.

См. также

• Хеш-таблица
• Разрешение коллизий
• Хеширование кукушки
• Идеальное хеширование
• Перехеширование

Источники информации

• http://src-code.net - Расширяемый метод хеширования
• Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — стр. 1236