Главная » SQL, Базы данных » ХЭШИРОВАНИЕ БАЗЫ ДАННЫХ

0

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

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

■       Для первоначального сохранения рассматриваемой записи СУБД вычисляет хэшированный адрес для новой записи и передает диспетчеру файлов команду на размещение этой записи по указанному адресу.

■       Для последующей выборки записи с использованием значения хэшированного поля СУБД проводит  такие же  вычисления, как  и  прежде, и  выдает диспетчеру   файлов команду чтения/записи по вычисленному адресу.

В качестве простого примера предположим, что значения номеров поставщиков составляют S100, S200, S300, S400, S500 (а не SI, S2, S3, S4, S5) и для каждой записи поставщика  требуется целая отдельная страница, а также рассмотрим следующую хэш-функцию:

хэшированный адрес (т.е. номер страницы) = остаток после деления числовой части значения S# на 13

Это — простейший пример очень широко применяемого класса хэш-функций, называемых функциями  хэширования с  использованием остатка  от  деления,  или  просто  хэш-функциями  "деление/остаток"   — "division/remainder"  hash function. (По причинам, описание которых  выходит за рамки данного приложения, в качестве  делителя в хэш-функции  "деление/остаток"  обычно используется простое число, как в данном примере.)  Таким  образом,  номера страниц для этих пяти поставщиков,  соответственно, принимают значения 9, 5, 1, 10, 6, в результате чего создается отображение между номерами поставщиком и номерами страниц, показанное на рис. Г. 14.

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

прямого хэширования  — direct hashing. В отличие от этого, с файлом может быть связано произвольное количество структур косвенного хэширования — indirect hash. См. [Г.24].)

Рассматриваемый пример показывает не только  принципы работы метода хэширования,  но и

позволяет понять, почему требуется хэш-функция. Было бы теоретически возможно  использовать

"идентичную" хэш-функцию,  иными словами, в качестве хэшированного адреса  непосредственно

применять значение первичного ключа (при этом, безусловно, подразумевается, что первичный ключ

является числовым). Но такой метод обычно не может использоваться на практике,  поскольку

диапазон возможных значений первичного ключа чаще всего намного превышает диапазон доступных

адресов. Например, предположим, что фактически номера поставщиков находятся в пределах от S000 до

S999, как показано в приведенном выше примере. В таком случае количество возможных различных

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

затрат пространства памяти в идеале следует найти такую хэш-функцию, которая будет преобразовывать

любое значение в диапазоне 000—999 в одно значение (скажем) в диапазоне 0-9. Но для  создания

небольшого резерва для будущего роста обычно принято расширять целевой диапазон адресов примерно

на 20%; именно поэтому в данном примере выбрана функция, которая вырабатывает  значения в

диапазоне 0-12, а не 0-9.

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

Примечание. Безусловно, всегда возможно наложить любую желаемую логическую последовательность на хэшированный файл с помощью индекса; а в действительности, возможно наложить несколько таких последовательностей с помощью нескольких индексов, по одному на каждую такую последовательность. См. также [Г.35] и [Г.37], где рассматриваются  возможности создания схем хэширования, сохраняющих логическую последовательность записей в хранимом файле.

Еще одним недостатком метода хэширования в целом является то, что всегда остается возможность коллизий, т.е. появления двух или нескольких разных записей ("синонимов"),  хэширование которых происходит по одному и тому же адресу. Например, предположим, что файл поставщиков (с данными о поставщиках S100, S200 и т.д.) включает также поставщика с номером S1400. При использовании хэшфункции, рассматриваемой в данном примере  ("поделить на 13 и взять остаток"), запись этого поставщика будет конфликтовать с записью поставщика S100, находящейся по хэшированному адресу

9.  Таким образом, очевидно, что хэш-функция в том виде, в котором она здесь описана, не обеспечивает нормальной работы и должна быть каким-то образом дополнена, чтобы  можно  было справиться с проблемой коллизий.

В терминах данного первоначального примера одним возможным дополнением является то, что остаток от деления на 13 должен рассматриваться не как хэшированный адрес как таковой, а скорее как отправная точка для последовательного просмотра. Таким образом, чтобы вставить запись поставщика S1400 (при условии, что записи поставщиков S100—S500 уже существуют), необходимо перейти на страницу 9 и выполнить поиск вперед от этой позиции до первой свободной страницы. Допустим, что новая запись поставщика будет сохранена на странице 11. В дальнейшем для выборки данных об этом поставщике необходимо пройти аналогичную процедуру. Такой метод, называемый линейным поиском (linear search), может оказаться вполне приемлемым, если на каждой странице хранится немного записей (как обычно и бывает на практике). Предположим, что на каждой странице может находиться п записей. В таком случае все п первых записей с одним и тем же хэшированным адресом р, попавших в коллизию, будут сохранены на странице р, а линейный поиск среди этих записей будет полностью ограничиваться одной этой страницей. Но следующая, (п+1)-я коллизия, безусловно, приведет к тому, что соответствующую запись придется сохранить на какой-то отдельной странице переполнения и потребуется еще одна операция ввода—вывода.

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

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

По теме:

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