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

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

Удаление определенного значения индексируемого поля осуществляется в следующем порядке.

· Производится поиск требуемого значения индексируемого поля и как результат в оперативную память считывается нужная листовая страница.

· Из нее удаляется соответствующее значение индексируемого поля и указатель-адрес соответствующей страницы файла данных.

· Если после удаления размер занятого пространства памяти текущей листовой страницы в сумме с размером занятого пространства левого (правого) брата больше, чем размер памяти одной страницы, то процесс заканчивается.

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

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

Описанный алгоритм удаления значений индексируемого поля соответствует одной из наиболее широко применяемых разновидностей Б-деревьев – Б* - деревьев, которые позволяют использовать в среднем до ~ 0,67 пространства всех страниц (вершин) дерева.

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

Идея расстановки записей, в англоязычной литературе- hash coding- хеширование, заключается в том, чтобы при выделении под размещение данных определенного участка памяти так организовать порядок расположения записей в нем, чтобы место для новых записей и поиск старых записей можно было производить на основе некоторого преобразования их ключевых полей. (Отсюда еще одно название данного подхода – «преобразование ключей», введенное в русской литературе в 1956 году академиком А.П. Ершовым).

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

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

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

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