Удаление

Вставка.

Модификация.

Пример.

Поиск.

Операции на В-деревьях.

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

Текущий узел=корень.

While текущий узел не лист

Begin

Путь=Путь + Текущий узел

Адрес = адрес из записи, покрывающей значение v.

Текущий узел=извлечь блок(адрес)

end;

Путь=Путь + Текущий узел

В результате текущий блок является блоком основного файла, поэтому искомая запись со значением v ищется в нем.

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

Если модифицируются не ключевые атрибуты, то выполняется операция поиска, после чего вносятся изменения в поля записи, и блок перезаписывается на диск.

Изначально необходимо найти блок В, в котором должна располагаться новая запись. Если В содержит меньше, чем 2е-1 записей, то запись размещается в блоке так, чтобы не нарушить сортировку. Очевидно, что новая запись не будет первой записью блока, кроме случая самого левого блока. Следовательно, нет необходимости изменять значения ключей в индексных блоках по иерархии.

Если в блоке уже 2е-1 записей, то в файле выделяется новый блок В1 и все записи блока В делятся поровну между блоками В и В1 (первые е записей остаются в блоке В, остальные переносятся в В1). При начальном поиске уже был найден путь от корня до блока В1. Теперь необходимо повторить процедуру вставки для всех блоков в обратном направлении к корню для регистрации блока В1 в индексах. В результате на определенном уровне индексный блок также может разделиться, если до вставки в нем уже было 2d-1 записей. Процесс разделения блоков может затронуть и корневой блок, в этом случае увеличивается количество уровней иерархии, так как в корне дерева должен лежать только один блок.

При удалении необходимо найти блок В, в котором содержится запись v. Если после удаления в блоке осталось е или более записей, то после удаления найденной записи и сдвига всех остальных операция закончена.

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

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

Дата добавления: 2015-05-09