2.3.3. Расстановка (хеширование) записей

В некотором смысле альтернативным подходом к органи­зации физических структур данных является расстановка за­писей.Как и при использовании линейных и нелинейных струк­тур, основной задачей расстановки записей является миними­зация расходов на доступ и изменения данных во внутренней и внешней памяти.

Идея расстановки, известной в англоязычной литературе также под термином хеширование,* заключается в том, чтобы при выделении под размещение данных определенного участ­ка памяти так организовать порядок расположения записей в нем, чтобы место для новых записей и поиск старых записей можно было осуществлять на основе некоторого преобразова­ния их ключевых полей.** При образовании(добавлении)но­вой записи к значению ее ключевого поля применяется специ­альнаяхеш-функция(или иначе хеш-свертка), которая ставит в соответствие значению ключевого поля, и, следовательно, всей записи, некоторое числовое значение, обычно являющееся номером (адресом) местоположения, куда в итоге и помещается соответствующая запись (см. рис. 2.20).

* От англ. to hash – нарезать, крошить, делить месиво, т.е. равномерно перема­лывать ключи нолей в адреса (номера) записей.

** Отсюда еще одно название данного подхода—«преобразование ключей», впер­вые введенное в русской литературе еще в 1956 г. будущим академиком А. П. Ершо­вым.

Рис. 2.20. Принцип расстановки записей по значению ключей

При доступе(поиске) нужной записи над значением ее клю­чевого поля также осуществляется хеш-свертка, что сразу же даст возможность определить местоположение искомой запи­си и получить к ней доступ.

Таким образом, в идеале хеширование обеспечивает дос­туп к нужным записям за одно (!!!) обращение к области раз­мещения данных.

Функция преобразования h(Кл_j) выбирается на основе двух требований: 1) ее результат для возможного диапазона значе­ний ключевого поля должен находиться в пределах диапазона адресов (номеров) области памяти, выделяемой подданные, и 2) значения функции в пределах выделенного диапазона адре­сов должны быть равномерными. На практике наиболее широ­кое распространение нашли хеш-функции, основанные на опе­рациях деления по модулю:

h(Кл_j)=(Кл_j mod М) + 1,

где (Кл_j modМ) означает операцию деления по модулю М,*а число М выбирается исходя из необходимости попадания зна­чений хеш-функции в требуемый диапазон.

*Значением операции деления по модулю М является остаток от обычного деле­ния числа на М, например результат деления 213 по модулю 20 равен 13.

Если в качестве М выбрать число, являющееся степенью двух, то подобная хеш-функция эффективно вычисляется про­цедурами выделения нескольких двоичных цифр.

Для текстовых ключевых полей обычно применяют подоб­ные подходы, основанные на использовании операции сложе­ния по модулю значений кодов первых нескольких символов ключа.

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

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

Второй подходк разрешению коллизий основывается на использованиидополнительного преобразования ключейпо схеме:

где n– исходное конфликтующее значение адреса записи; g(Кл_i)– дополнительное преобразование ключа;n– допол­нительное значение адреса.

При этом могут встречаться ситуации, когда и такое допол­нительное преобразование приводит к коллизии, т.е. новое зна­чение nтакже оказывается уже занятым. В таких случаях дополнительное преобразование g(Кл_i)чаще всего организуют на основе рекуррентной процедуры по следующей схеме:

где f(k) –некоторая функция над номером итерации (пробы).

В зависимости от вида функции f(k) такие подходы назы­ваютлинейнымииликвадратичными пробами.

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

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

Рис. 2.21. Принцип хеширования записей но страницам файла данных

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

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

Внутренняя схема базы данных обычно скрыта от пользо­вателей информационной системы, за исключением возможно­сти установления и использования индексации полей. Вместе с тем, особенности физической структуры файлов данных и ин­дексных массивов, принципы организации и использования дис­кового пространства и внутренней памяти, реализуемые конк­ретной СУБД, должны учитываться проектировщиками банков данных, так как эти «прозрачные» для пользователей-абонен­тов особенности СУБД критично влияют на эффективность об­работки данных в информационной системе.