29
правок
Изменения
Новая страница: «'''Метод расширяемого хеширования''' (''extendable hashing'') представляет собой изящный вариант осн...»
'''Метод расширяемого хеширования''' (''extendable hashing'') представляет собой изящный вариант основного метода хеширования, позволяющий устранить проблемы хеширования при увеличении размеров хешированного файла (увеличение количества коллизий и среднего времени доступа). В действительности, расширяемое хеширование гарантирует, что количество операций доступа к диску, необходимых для поиска определенной записи, никогда не превышает двух и обычно сводится только к одной операции, независимо от того, какого размера достигает сам файл. (Поэтому данный метод гарантирует также, что никогда не возникнет потребность в реорганизации файла.)
'''Примечание''': В этой схеме расширяемого хеширования значения хешированного поля должны быть уникальными, а такое условие, разумеется, будет соблюдено, если данное поле фактически является первичным ключом.
== Схема хеширования ==
# Допустим, что основной функцией хеширования является h, а значение первичного ключа некоторой конкретной записи r равно к. Хеширование значения к (т.е. вычисление выражения h(к)) приводит к получению значения s, называемого псевдоключом (pseudokey) записи к. Псевдоключи не интерпретируются непосредственно как адреса, а вместо этого применяются для косвенного поиска адресов хранения, как описано ниже.
# Файл имеет связанный с ним каталог, который также хранится на диске. Каталог состоит из заголовка, содержащего значение d (сокращение от depth — глубина каталога), наряду с 2<sup>d</sup> указателями. Указатели указывают на страницы с данными, содержащими фактические записи (на каждой странице имеется много записей). Таким образом, каталог с глубиной d позволяет управлять файлом с максимальным размером, составляющим 2<sup>d</sup> отдельных страниц с данными.[[Файл:Deit vvedenie v DB 8e.jpg|мини| Пример применения способа расширяемого хеширования]]
# Если ведущие d битов псевдоключа рассматриваются как двойное целое число без знака b, то i-й указатель в каталоге (1 < i < 2<sup>d</sup>) указывает на страницу, содержащую все записи, для которых b принимает значение i-l. Иными словами, первый указатель указывает на страницу, содержащую все записи, для которых b состоит из одних нулей, второй указатель указывает на страницу, для которой b равно 0. .. 01, и т.д. (Обычно все эти 2<sup>d</sup> указателя не являются различными; это означает, что количество различных страниц с данными, как правило, меньше чем 2<sup>d</sup>, как показано на рис.) Поэтому, чтобы найти запись, имеющую значение первичного ключа к, необходимо хешировать к для определения псевдоключа s и взять первые d битов этого псевдоключа; если эти биты имеют числовое значение i-l, осуществляется переход к i-му указателю в каталоге (первая операция доступа к диску) и переход по этому указателю к странице, содержащей требуемую запись (вторая операция доступа к диску). '''Примечание''': На практике этот каталог обычно остается достаточно небольшим для того, чтобы его можно было почти все время хранить в оперативной памяти. Поэтому упомянутые "две" операции доступа к диску обычно сводятся к одной.
#Каждая страница с данными имеет также заголовок, указывающий локальную глубину р этой страницы (р < d). Предположим, например, что d равно 3 и первый указатель в каталоге (указатель 000) указывает на страницу, для которой локальная глубина р равна 2. В данном случае локальная глубина 2 означает, что эта страница содержит не только все записи с псевдоключами, начинающимися с 000, но и содержит все записи с псевдоключами, начинающимися с 00 (т.е. теми, которые начинаются с 000, а также теми, которые начинаются с 001). Иными словами, указатель каталога 001 также указывает на эту страницу (см. рис).
#Теперь предположим, что страница с данными 000 заполнена и нужно вставить новую запись, имеющую псевдоключ, который начинается с 000 (или с 001). В этот момент указанная страница разделяется на две; это означает, что из пула свободных страниц берется новая, пустая страница, а все записи 001 изымаются из старой страницы и переносятся в новую. Указатель 001 в каталоге корректируется таким образом, чтобы он указывал на новую страницу (указатель 000 все еще указывает на старую страницу). Локальная глубина р для каждой из этих двух страниц теперь будет равна 3, а не 2.
#Теперь допустим, что страница с данными, соответствующая начальной строке битов 000, снова заполняется и должна быть опять разделена. Существующий каталог не позволяет обеспечить такое разделение, поскольку локальная глубина разделяемой страницы уже равна глубине каталога. Поэтому размер каталога удваивается; это означает, что значение d увеличивается на единицу и каждый указатель заменяется парой смежных, идентичных указателей. Теперь появляется возможность разделить страницу с данными; записи 0000 остаются на старой странице, а записи 0001 перемещаются на новую страницу; первый указатель в каталоге остается неизменным (т.е. по-прежнему указывает на старую страницу), а второй указатель корректируется таким образом, чтобы он указывал на новую страницу. Следует отметить, что операция удваивания размера каталога требует относительно небольших затрат времени, поскольку она не связана с доступом к какой-либо из страниц с данными.
== См. также ==
*[[Хеш-таблица]]
*[[Разрешение коллизий]]
*[[Хеширование кукушки]]
*[[Идеальное хеширование]]
*[[Перехеширование]]
== Источники информации ==
*[http://src-code.net/rasshiryaemyj-metod-xeshirovaniya/ http://src-code.net - Расширяемый метод хеширования]
*Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — стр. 1236
[[Категория: Дискретная математика и алгоритмы]]
'''Примечание''': В этой схеме расширяемого хеширования значения хешированного поля должны быть уникальными, а такое условие, разумеется, будет соблюдено, если данное поле фактически является первичным ключом.
== Схема хеширования ==
# Допустим, что основной функцией хеширования является h, а значение первичного ключа некоторой конкретной записи r равно к. Хеширование значения к (т.е. вычисление выражения h(к)) приводит к получению значения s, называемого псевдоключом (pseudokey) записи к. Псевдоключи не интерпретируются непосредственно как адреса, а вместо этого применяются для косвенного поиска адресов хранения, как описано ниже.
# Файл имеет связанный с ним каталог, который также хранится на диске. Каталог состоит из заголовка, содержащего значение d (сокращение от depth — глубина каталога), наряду с 2<sup>d</sup> указателями. Указатели указывают на страницы с данными, содержащими фактические записи (на каждой странице имеется много записей). Таким образом, каталог с глубиной d позволяет управлять файлом с максимальным размером, составляющим 2<sup>d</sup> отдельных страниц с данными.[[Файл:Deit vvedenie v DB 8e.jpg|мини| Пример применения способа расширяемого хеширования]]
# Если ведущие d битов псевдоключа рассматриваются как двойное целое число без знака b, то i-й указатель в каталоге (1 < i < 2<sup>d</sup>) указывает на страницу, содержащую все записи, для которых b принимает значение i-l. Иными словами, первый указатель указывает на страницу, содержащую все записи, для которых b состоит из одних нулей, второй указатель указывает на страницу, для которой b равно 0. .. 01, и т.д. (Обычно все эти 2<sup>d</sup> указателя не являются различными; это означает, что количество различных страниц с данными, как правило, меньше чем 2<sup>d</sup>, как показано на рис.) Поэтому, чтобы найти запись, имеющую значение первичного ключа к, необходимо хешировать к для определения псевдоключа s и взять первые d битов этого псевдоключа; если эти биты имеют числовое значение i-l, осуществляется переход к i-му указателю в каталоге (первая операция доступа к диску) и переход по этому указателю к странице, содержащей требуемую запись (вторая операция доступа к диску). '''Примечание''': На практике этот каталог обычно остается достаточно небольшим для того, чтобы его можно было почти все время хранить в оперативной памяти. Поэтому упомянутые "две" операции доступа к диску обычно сводятся к одной.
#Каждая страница с данными имеет также заголовок, указывающий локальную глубину р этой страницы (р < d). Предположим, например, что d равно 3 и первый указатель в каталоге (указатель 000) указывает на страницу, для которой локальная глубина р равна 2. В данном случае локальная глубина 2 означает, что эта страница содержит не только все записи с псевдоключами, начинающимися с 000, но и содержит все записи с псевдоключами, начинающимися с 00 (т.е. теми, которые начинаются с 000, а также теми, которые начинаются с 001). Иными словами, указатель каталога 001 также указывает на эту страницу (см. рис).
#Теперь предположим, что страница с данными 000 заполнена и нужно вставить новую запись, имеющую псевдоключ, который начинается с 000 (или с 001). В этот момент указанная страница разделяется на две; это означает, что из пула свободных страниц берется новая, пустая страница, а все записи 001 изымаются из старой страницы и переносятся в новую. Указатель 001 в каталоге корректируется таким образом, чтобы он указывал на новую страницу (указатель 000 все еще указывает на старую страницу). Локальная глубина р для каждой из этих двух страниц теперь будет равна 3, а не 2.
#Теперь допустим, что страница с данными, соответствующая начальной строке битов 000, снова заполняется и должна быть опять разделена. Существующий каталог не позволяет обеспечить такое разделение, поскольку локальная глубина разделяемой страницы уже равна глубине каталога. Поэтому размер каталога удваивается; это означает, что значение d увеличивается на единицу и каждый указатель заменяется парой смежных, идентичных указателей. Теперь появляется возможность разделить страницу с данными; записи 0000 остаются на старой странице, а записи 0001 перемещаются на новую страницу; первый указатель в каталоге остается неизменным (т.е. по-прежнему указывает на старую страницу), а второй указатель корректируется таким образом, чтобы он указывал на новую страницу. Следует отметить, что операция удваивания размера каталога требует относительно небольших затрат времени, поскольку она не связана с доступом к какой-либо из страниц с данными.
== См. также ==
*[[Хеш-таблица]]
*[[Разрешение коллизий]]
*[[Хеширование кукушки]]
*[[Идеальное хеширование]]
*[[Перехеширование]]
== Источники информации ==
*[http://src-code.net/rasshiryaemyj-metod-xeshirovaniya/ http://src-code.net - Расширяемый метод хеширования]
*Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — стр. 1236
[[Категория: Дискретная математика и алгоритмы]]
