Изменения

'''Метод расширяемого хеширования''' (англ. ''extendable extendible hashing'') представляет собой изящный вариант основного метода хешированияпредусматривает изменение размеров блоков по мере роста базы данных, позволяющий устранить проблемы хеширования при увеличении размеров хешированного файла (увеличение количества коллизий и среднего времени доступа)но это компенсируется оптимальным использованием места. Т.к. В действительностиза один раз разбивается не более одного блока, расширяемое хеширование гарантируетнакладные расходы достаточно малы== Алгоритм ==Посмотрим, как работает алгоритм, на примере заполнения гипотетической хеш-таблицы. Первоначально в таблице имеется одна группа. Предположим, что количество операций доступа к дискукаждая группа будет содержать 10 хеш-значений и номер записи каждого хеш-значения, необходимых для поиска определенной записичтобы ее можно было извлечь. Обратите внимание, никогда что мы не превышает двух и обычно сводится только к одной операциипомещаем в группы сами ключи. При использовании 32-разрядных хеш-значений, независимо от тогомаловероятно, какого размера достигает сам файлчтобы два ключа хешировались в одно и то же значение. (Поэтому данный метод гарантирует такжеФактически это будет происходить настолько редко, что никогда не возникнет потребность в реорганизации файладля проверки ключей можно извлечь саму запись без заметного замедления всего процесса. Естественно, при этом предполагается, что используемая хеш-функция успешно справляется с рандомизацией.)

Начнем вставлять в таблицу хеш-значения вместе с номерами их записей. При наличии только одной группы их можно вставить только в одно место, поэтому после 10 вставок группа заполняется. Разобьем заполненную группу на две группы одинаковых размеров и повторим вставку всех элементов исходной группы в две новые группы. Причем все элементы, которые завершаются нулевым разрядом, поместим в одну группу, а завершающиеся единичным разрядом - в другую. Эти две группы имеют так называемую разрядную глубину (англ. ''bit-depth'Примечание''': В этой схеме расширяемого хеширования значения хешированного поля должны быть уникальными, а такое условие, разумеется), равную одному разряду. Теперь при каждой вставке пары хеш-значение/номер записи она будет соблюденопомещаться в первую или во вторую группу, если данное поле фактически является первичным ключомв зависимости от последнего разряда хеш-значения.== Схема хеширования ==# ДопустимСо временем мы заполним еще одну группу. Предположим, что основной функцией хеширования является hэто группа, в которую мы вставляли все хеш-значения, а значение первичного ключа некоторой конкретной записи r равно кзавершающиеся 0. Снова разобьем группу на две отдельные группы. Хеширование На этот раз все элементы, хеш-значения к (которых заканчиваются двумя нулевыми разрядами, т.е. вычисление выражения h(к)) приводит к получению 00, будут помещаться в первую группу, а завершающиеся разрядами 10 - во вторую группу. Обе группы имеют разрядную глубину, равную 2. Поэтому для определения места вставки необходимо проверять два младших разряда хеш-значения s. Теперь у нас имеются три группы: в первую вставляются элементы, завершающиеся разрядами 00, во вторую -разрядами 10, называемого псевдоключом (pseudokey) записи ка в третью - просто 1. Предположим, что мы продолжаем вставку и заполняем группу 10. Мы снова разбиваем заполненную группу на две и повторяем вставку ее элементов в две новые группы. На этот раз две новые группы будут принимать элементы, завершающиеся разрядами 010 и 110. Псевдоключи не интерпретируются непосредственно как адресаТаким образом, теперь у нас имеются четыре группы: одна с разрядной глубиной, равной 1, в которую выполняется вставка хеш-значений, завершающихся 1, одна с разрядной глубиной равной 2, содержащая хеш-значения, которые завершаются разрядами 00, и две группы с разрядной глубиной, равной 3, а вместо этого применяются которые предназначены для косвенного поиска адресов храненияхеш-значений, как описано нижезавершающихся разрядами 010 и 110.# Файл имеет связанный Для поддержания отображения того, какие хеш-значения помещаются в те или иные группы, используется структура, называемая каталогом (англ. ''catalogue''). По существу каталог содержит список всех возможных окончаний групп и связных с ним ними номеров групп. Вместо того чтобы поддерживать какой-либо причудливый набор значений разрядной глубины и номеров групп, выбранный методом проб и ошибок, каталогподдерживает собственное значение разрядной глубины, который равное максимальной разрядной глубине группы, и имеет ячейку для каждого значения этой разрядной глубины. В рассмотренном нами примере максимальная разрядная глубина группы была равна 3, поэтому разрядная глубина каталога также хранится на дискеравна этому значению. Три разряда позволяют образовать восемь комбинаций разрядов: 000, 001, 010, 011, 100, 101, 110 и 111. Каталог состоит из заголовкаВсе комбинации, содержащего значение d которые завершаются 1 (сокращение от depth — глубина каталогат.е. вторая, четвертая, шестая и восьмая), наряду с 2^d указателями. Указатели указывают на страницы с даннымиодну и ту же группу, принимающую элементы, хеш-значения которых завершаются 1. Аналогично, содержащими фактические записи (каталога для значений 000 и 100 указывают на каждой странице имеется много записей). Таким образомодну и ту же группу, каталог в которую помещаются элементы с глубиной d позволяет управлять файлом с максимальным размеромхеш-значениями, составляющим 2^d отдельных страниц с даннымизавершающимися разрядами 00. [[Файл:Deit vvedenie v DB 8e7_1.jpgpng|400px|мини| Пример применения способа расширяемого хешированияВставка в расширяемую хеш-таблицу]]# Если ведущие d битов псевдоключа рассматриваются как двойное целое число без знака bОднако эта схема не учитывает ряд особенностей. Две записи каталога, то i-й указатель в каталоге (1 < i < 2^d) указывает которые указывают на страницугруппу для элементов, содержащую все записихеш-значения которых завершаются разрядами 00, для которых b принимает значение i-lразделены тремя другими записями. Иными словами, первый указатель указывает на страницуАналогично единственной группе, содержащую принимающей все записиэлементы, для хеш-значения которых b состоит из одних нулейзавершаются 1, второй указатель указывает на страницусоответствуют четыре записи, для которой b равно 0равномерно распределенные по каталогу. При разбиении группы дополняющие друг друга группы не будут размещаться в каталоге по соседству.. 01, и т.д. (Обычно все эти 2^d указателя не являются различными; это означаетДля дальнейших рассуждений было бы проще предположить, что количество различных страниц с даннымизаписи каталога, как правилосоответствующие одной группе, меньше чем 2^dрасполагаются по соседству, как показано на рисчтобы при разбиении группы дополняющая первую группа помещалась непосредственно за ней.  Для достижения этого следует инвертировать последние разряды хеш-значения при вычислении индексной записи каталога.) ПоэтомуТак, чтобы найти записьнапример, имеющую если хеш-значение первичного ключа завершается разрядами 001, при поиске мы обратимся не кзаписи 001 каталога, необходимо хешировать а к для определения псевдоключа s и взять первые d битов этого псевдоключа; если эти биты имеют числовое значение iзаписи 100 (4, которая соответствует инвертированному значению 001). В результате использование каталога значительно упрощается. В нашем примере хеш-lзначения, которые завершаются разрядами 00, осуществляется переход к i-му указателю помещаются в каталоге запись каталога 000 (первая операция доступа к диску0) и переход по этому указателю к странице, содержащей требуемую запись или 001 (вторая операция доступа к диску1). '''Примечание''': На практике этот каталог обычно остается достаточно небольшим для тогоХеш-значения, которые завершаются разрядами 010, чтобы его можно было почти все время хранить помещаются в оперативной памяти. Поэтому упомянутые "две" операции доступа к диску обычно сводятся к одной.#Каждая страница с данными имеет также заголовок, указывающий локальную глубину р этой страницы запись каталога 010 (р < d2). ПредположимХеш-значения, напримеркоторые завершаются разрядами 011, что d равно 3 и первый указатель помещаются в каталоге запись каталога 011 (указатель 0003) указывает на страницу. И, для которой локальная глубина р равна 2. В данном случае локальная глубина 2 означаетнаконец, что эта страница содержит не только все записи с псевдоключамихеш-значения, начинающимися с 000которые завершаются разрядом 1, но и содержит все помещаются в записи с псевдоключами100, 101, начинающимися с 00 110 или 111 (т.е. теми4, которые начинаются с 0005, а также теми6, которые начинаются с 0017). Иными словами Вернемся немного назад, и вставим элементы в пустую хеш-таблицу, указатель как это было сделано ранее. Выполняемые при этом действия показаны на рис. Мы начинаем с каталога 001 также указывает на эту страницу только с одной записью с индексом 0 (см. риса).#Теперь предположимПринято считать, что страница с данными 000 заполнена в подобной ситуации разрядная глубина равна 0. Мы заполняем единственную группу (назовем ее А) и теперь ее нужно вставить новую записьразбить. Вначале мы увеличиваем разрядную глубину каталога до 1. Иначе говоря, имеющую псевдоключ, который начинается с 000 теперь он будет содержать две записи (или с 001b). В этот момент указанная страница разделяется на результате будут созданы две; это означаетгруппы, что на первую из пула свободных страниц берется новая, пустая страницакоторых указывает запись 0 (исходная запись А), а все записи 001 изымаются из старой страницы и переносятся в новую. Указатель 001 в каталоге корректируется таким образомна вторую - запись 1, чтобы он указывал на новую страницу В (указатель 000 все еще указывает на старую страницус). Локальная глубина р для каждой из этих двух страниц теперь будет равна 3Все элементы, хеш-значения которых завершаются разрядом 0, помещаются в группу А, а не 2остальные - в группу В. Снова заполним группу A.#Теперь допустим, что страница разрядную глубину каталога необходимо увеличить с данными1 до 2, соответствующая начальной строке битов 000чтобы получить четыре группы, снова заполняется и должна быть опять разделенадоступных для вставки. Существующий каталог не позволяет обеспечить такое разделение, поскольку локальная глубина разделяемой страницы уже равна глубине Перед разделением заполненной группы записи каталога. Поэтому размер каталога удваивается; это означает00 и 01 будут указывать на исходную группу А, что значение а записи 10 и 11 - на группу В (d увеличивается ). Группа А разбивается на единицу группу, которая принимает хеш-значения с окончанием 00 (снова А), и каждый указатель заменяется парой смежныхгруппу, которая принимает хеш-значения с окончанием 10, идентичных указателейС. Теперь появляется возможность разделить страницу с данными; записи 0000 остаются на старой страницеНа группу А будет указывать запись 00 каталога, а записи 0001 перемещаются на новую страницу; первый указатель в каталоге остается неизменным группу С - запись 01 (т.еe). по-прежнему указывает на старую страницу)И, а второй указатель корректируется таким образомнаконец, чтобы он указывал группа С (на новую страницукоторую указывает запись 01 каталога) заполняется. Следует отметить, что операция удваивания размера Нужно снова увеличить разрядную глубину каталога требует относительно небольших затрат времени, поскольку она не связана с доступом к какой-либо из страниц с даннымина этот раз до трех разрядов.

[[Категория: Дискретная математика и алгоритмы]][[Категория: Структуры данных]]