B-деревья: удаление ключей

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

1. Ключ удаляется из вершины-листа и в ней по-прежнему остается не меньше k ключей (т.е. отсутствует так называемое антипереполнение). На рис. 2.13 приведен пример этого случая.

Рис.2.13

Удаление при отсутствии антипереполнения

а) до удаления ключа 5;

б) после удаления.

2. Ключ удаляется из ветвящейся вершины. Даже при отсутствии антипереполнения его необходимо заменить каким-то другим ключом в целях сохранения правого поддерева удаляемого ключа. Он замещается ключом из левой вершины-листа правого поддерева удаляемого ключа. Для этого при удалении ключа из корневой вершины приходится просмотреть максимум h вершин. Как только найдена вершина-лист, левый ключ из нее удаляется и включается в новую вершину. Если удаление ключа из вершины-листа не вызывает антипереполнения, то операция заканчивается. На рис. 2.14 приведен пример случая 2.

Рис. 2.14

Удаление ключа из ветвящейся вершины В-дерева (случай 2):

а) до удаления ключа 20;

б) после удаления ключа 20 и его замены ключом 21.

3. Удаление ключа из вершины-листа вызывает антипереполнение (в вершине остается меньше k ключей). В этом случае недостающий ключ можно занять из левой или правой соседней (подобной) вершины. При этом в целях получения сбалансированного распределения ключей между двумя соседними вершинами можно занять несколько ключей. Последнее требует наличия в двух вершинах не менее 2k ключей. Если ключей меньше 2k, то выполняется сцепление вершин: все ключи переносятся в одну из вершин, а другая вершина из дерева удаляется. Операция сцепления по своему действию противоположна операции деления вершин. Она подразумевает также пересылку в оставшуюся подобную вершину ключа из вершины-предшественника, разделяющего две соседние подобные вершины. Удаление ключа из вершины-предшественника может вызвать в ней антипереполнение, и в худшем случае оно может распространиться вверх до корневой вершины. Возможны следующие операции для случая антипереполнения:

А) перераспределение ключей в подобных вершинах (см. рис.2.15);

Рис.2.15

Удаление ключа из ветвящейся вершины В-дерева (случай 3а):

а) до удаления ключа 276;

б) после удаления ключа 276 и перераспределения ключей

в подобных вершинах.

Б) сцепление вершин на одном уровне (см. рис.2.16);

Рис.2.16

Удаление ключа из ветвящейся вершины В-дерева (случай 3б):

а) до удаления ключа 15;

б) после удаления ключа 15 и сцепления подобных вершин.

В) в худшем случае процесс сцепления вершин распространяется вверх до корня, т.е. имеет место сцепление на уровнях (см. рис.2.17).

Рис.2.17

Удаление ключа из ветвящейся вершины В-дерева (случай 3в):

а) до удаления ключа 20;

б) после первого сцепления ключей 6 и 16;

в) после второго сцепления ключей 23 и 25;

г) после третьего сцепления ключей 57 и 91 и организации

новой корневой вершины.