Главная » SQL, Базы данных » Расширяемый метод хэширования

0

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

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

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

Ниже приведено краткое описание рассматриваемой схемы хэширования.

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

h ( к )) приводит к получению значения з, называемого псевдоключом (pseudokey) записи к. Псевдоключи не интерпретируются непосредственно как адреса, а вместо этого применяются для косвенного поиска адресов хранения, как описано ниже.

2.             Файл имеет связанный с ним каталог, который также хранится на диске. Каталог состоит из за головка, содержащего значение d (сокращение от depth — глубина каталога), наряду с 2d указа телями. Указатели указывают на страницы с данными, содержащими фактические записи (на каждой странице имеется много записей). Таким образом,  каталог с глубиной d позволяет управлять файлом с максимальным размером, составляющим 2d отдельных страниц с данными.

3.             Если ведущие d битов псевдоключа рассматриваются как двойное целое число без знака Ь, то i-й указатель в каталоге (1  <  i  < 2d) указывает на страницу, содержащую все записи, для которых b принимает значение i-l. Иными словами, первый указатель указывает на страницу, содержа щую все записи, для которых b состоит из одних нулей, второй указатель указывает на страницу, для которой b равно 0. . . 01, и т.д. (Обычно все эти 2d  указателя не являются различными; это означает, что количество различных страниц сданными, как правило, меньше чем 2d, как пока зано на рис. Г. 15.) Поэтому, чтобы найти запись, имеющую значение первичного ключа к, необ ходимо хэшировать к для определения псевдоключа s и взять первые d битов этого псевдоклю ча; если эти биты имеют числовое значение i-l, осуществляется переход к i-му указателю в ка талоге (первая операция доступа к диску) и переход по этому указателю к странице, содержащей требуемую запись (вторая операция доступа к диску).

3  В [Г.28] применяется англоязычное написание термина "extendable" (расширяемый)  с  буквой i, т.е.

"extendible".

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

4.          Каждая страница с  данными имеет также  заголовок, указывающий  локальную  глубину р  этой страницы (р  < d).  Предположим, например, что d  равно 3  и  первый указатель  в  каталоге (указатель 000) указывает на страницу, для которой локальная глубина р равна 2. В данном случае локальная глубина 2 означает, что эта страница содержит не только все записи с псевдоключами, начинающимися с 000, но и содержит все записи с псевдоключами, начинающимися с 00 (т.е. теми, которые начинаются с 000, а также теми, которые начинаются с 001). Иными словами, указатель каталога 001 также указывает на эту страницу (см. рис. Г. 15).

Рис. Г. 15. Пример применения способа расширяемого хэширования

5.          Теперь предположим, что страница с данными 000 заполнена и нужно вставить новую  запись, имеющую псевдоключ, который начинается с 000 (или с 001). В этот момент указанная страница разделяется на две; это означает, что из пула свободных страниц берется новая, пустая страница, а все записи 001 изымаются из старой страницы и переносятся в новую. Указатель 001 в

каталоге корректируется таким образом, чтобы он указывал на новую страницу  (указатель 000 все еще указывает на старую страницу). Локальная глубина р для каждой из этих двух страниц теперь будет равна 3, а не 2.

6.        Теперь допустим, что страница с данными, соответствующая начальной строке битов 000, снова заполняется и должна быть опять разделена. Существующий каталог не позволяет  обеспечить такое разделение, поскольку локальная глубина разделяемой страницы уже  равна глубине каталога. Поэтому размер каталога  удваивается; это  означает, что  значение d  увеличивается на единицу и каждый указатель заменяется парой смежных,  идентичных указателей. Теперь появляется возможность разделить страницу с данными; записи 0000 остаются на старой странице, а записи 0001 перемещаются на новую  страницу; первый указатель в каталоге остается неизменным (т.е. по-прежнему  указывает  на старую страницу), а второй указатель корректируется таким образом, чтобы  он указывал  на новую страницу. Следует отметить, что операция удваивания размера  каталога требует относительно небольших затрат времени, поскольку она не связана с доступом к какой-либо из страниц с данными.

На  этом  описание  метода  расширяемого  хэширования  завершается.  Кроме  него,  предложено множество других дополнений к основному методу хэширования; см., например, [Г.29]—[Г.36].

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии