В хэшированием файле записи не обязательно должны вводиться в файл
последовательно. Вместо этого для вычисления адреса страницы, на которой должна
находиться запись, используется хэш-функция (hash function), параметрами которой
являются значения одного или нескольких полей этой записи. Подобное поле
называется полем хэширования (hash field), а если поле является также ключевым
полем файла, то оно называется хэш-ключом (hash key). Записи в хэшированием
файле распределены произвольным образом по всему доступному для файла
пространству. По этой причине хэшированные файлы иногда называют файлами с
произвольным или прямым доступом (random file или direct file).
хэш-функция выбирается таким образом, чтобы записи внутри файла были
распределены наиболее равномерно. Один из методов создания хэш-функции
называется сверткой (folding) и основан на выполнении некоторых
арифметических действий над различными частями поля хэширования. При этом
символьные строки преобразуются в целые числа с использованием некоторой
кодировки (на основе расположения букв в алфавите или кодов символов ASCII).
Например, можно преобразовать в целое число первые два символа поля табельного
номера сотрудника (атрибут staffNo), а затем сложить полученное значение с
остальными цифрами этого номера. Вычисленная сумма используется в качестве
адреса дисковой страницы, на которой будет храниться данная запись. Более
популярный альтернативный метод основан на хэшировании с применением остатка
от деления. В этом методе используется функция MOD, которой передается
значение поля. Функция делит полученное значение на некоторое заранее заданное
целое число, после чего остаток от деления используется в качестве адреса на
диске.
Недостатком большинства хэш-функций является то, что они не гарантируют
получение уникального адреса, поскольку количество возможных значений поля
хэширования может быть гораздо больше количества адресов, доступных для записи.
Каждый вычисленный хэш-функцией адрес соответствует некоторой странице, или
сегменту (bucket), с несколькими ячейками (слотами), предназначенными для
нескольких записей. В пределах одного сегмента записи размещаются в слотах в
порядке поступления. Тот случай, когда один и тот же адрес генерируется для двух
или более записей, называется конфликтом (collision), a подобные записи —
синонимами. В этой ситуации новую запись необходимо вставить в другую позицию,
поскольку место с вычисленным для нее хэш-адресом уже занято. Разрешение
конфликтов усложняет сопровождение хэшированных файлов и снижает общую
производительность их работы.
Для разрешения конфликтов можно использовать следующие методы:
открытая адресация;
несвязанная область переполнения;
связанная область переполнения;
многократное хэширование.
Открытая адресация
При возникновении конфликта система выполняет линейный поиск первого
доступного слота для вставки в него новой записи. После неудачного поиска
пустого слота в последнем сегменте поиск продолжается с первого сегмента. При
выборке записи используется тот же метод, который применялся при сохранении
записи, за исключением того, что запись в данном случае рассматривается как не
существующая, если до обнаружения искомой записи будет обнаружен пустой слот.
На первый взгляд может показаться, что этот подход не дает большого выигрыша
в производительности. Однако при более внимательном анализе обнаруживается, что
при использовании открытой адресации конфликты, устраненные с помощью первого
свободного слота, могут вызвать дополнительные конфликты с записями, которые
будут иметь хэш-значение, равное адресу этого прежде свободного слота. Таким
образом, количество конфликтов будет возрастать, а производительность — падать.
С другой стороны, если количество конфликтов удастся свести к минимуму, то
линейный поиск в малой области переполнения будет выполняться достаточно быстро.
Связанная область переполнения
Как и в предыдущем методе, в этом методе для разрешения конфликтов с
записями, которые не могут быть размещены в слоте с их адресом хэширования,
используется область переполнения. Однако в данном методе каждому сегменту
выделяется дополнительное поле, которое иногда называется указателем синонима.
Оно определяет наличие конфликта и указывает страницу в области переполнения,
использованную для его разрешения. Если указатель равен нулю, то никаких
конфликтов нет.
Для более быстрого доступа к записи переполнения можно использовать указатель
синонима, который указывает на адрес слота внутри области переполнения, а не на
адрес сегмента. Записи внутри области переполнения также имеют указатели
синонима, которые содержат в области переполнения адрес следующего синонима для
такого же адреса, поэтому все синонимы одного адреса могут быть извлечены с
помощью цепочки указателей.
Многократное хэширование
Альтернативный способ разрешения конфликтов заключается в применении второй
хэш-функции, если первая функция приводит к возникновению конфликта. Цель второй
хэш-функции заключается в получении нового адреса хэширования, который позволил
бы избежать конфликта. Вторая хэш-функция обычно используется для размещения
записей в области переполнения.
При работе с хэшированными файлами запись может быть достаточно эффективно
найдена с помощью первой хэш-функции, а в случае возникновения конфликта для
определения ее адреса следует применить один из перечисленных выше способов.
Прежде чем обновить хэшированную запись, ее следует найти. Если обновляется
значение поля, которое не является хэш-ключом, то такое обновление может быть
выполнено достаточно просто, причем обновленная запись сохраняется в том же
слоге. Но если обновляется значение хэш-ключа, то до размещения обновленной
записи потребуется вычислить хэш-функцию. Если при этом будет получено новое
хэш-значение, то исходная запись должна быть удалена из текущего слота и
сохранена по вновь вычисленному адресу.
Динамическое хэширование
Динамическое хэширование
Перечисленные выше методы хэширования являются статическими, в том смысле,
что пространство хэш-адресов задается непосредственно при создании файла.
Считается, что пространство файла уже насыщено, когда оно уже почти полностью
заполнено и администратор базы данных вынужден реорганизовать его хэш-структуру.
Для этого может потребоваться создать новый файл большего размера, выбрать новую
хэш-функцию и переписать старый файл во вновь отведенное место. В альтернативном
подходе, получившем название динамического хэширования, допускается динамическое
изменение размера файла с целью его постоянной модификации в соответствии с
уменьшением или увеличением размеров базы данных.
Основной принцип динамического хэширования заключается в обработке числа,
выработанного хэш-функцией в виде последовательности битов, и распределении
записей по сегментам на основе так называемой прогрессирующей оцифровки
(progressive digitization) этой последовательности. Динамическая хэш-функция
вырабатывает значения в широком диапазоне, а именно b-битовые двоичные целые
числа, где b обычно равно 32.
Ограничения, свойственные методу хэширования
Использование метода хэширования для извлечения записей основано на полностью
известном значении хэш-поля. Поэтому, как правило, хэширование не подходит для
операций извлечения данных по заданному образцу или диапазону значений. Более
того, хэширование не подходит для поиска и извлечения данных по любому другому
полю, отличному от поля хэширования.
Знаете ли Вы, в чем фокус эксперимента Майкельсона?
Эксперимент А. Майкельсона, Майкельсона - Морли - действительно является цирковым фокусом, загипнотизировавшим физиков на 120 лет.
Дело в том, что в его постановке и выводах произведена подмена, аналогичная подмене в школьной шуточной задачке на сообразительность, в которой спрашивается: - Cколько яблок на березе, если на одной ветке их 5, на другой ветке - 10 и так далее При этом внимание учеников намеренно отвлекается от того основополагающего факта, что на березе яблоки не растут, в принципе.
В эксперименте Майкельсона ставится вопрос о движении эфира относительно покоящегося в лабораторной системе интерферометра. Однако, если мы ищем эфир, как базовую материю, из которой состоит всё вещество интерферометра, лаборатории, да и Земли в целом, то, естественно, эфир тоже будет неподвижен, так как земное вещество есть всего навсего определенным образом структурированный эфир, и никак не может двигаться относительно самого себя.
Удивительно, что этот цирковой трюк овладел на 120 лет умами физиков на полном серьезе, хотя его прототипы есть в сказках-небылицах всех народов всех времен, включая барона Мюнхаузена, вытащившего себя за волосы из болота, и призванных показать детям возможные жульничества и тем защитить их во взрослой жизни. Подробнее читайте в FAQ по эфирной физике.
