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

 

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

1. В вершине-листе есть место для нового ключевого значения. Новый ключ помещается в соответствующее место этой вершины.

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

3. Вершина-предшественник также является полной. В этом случае она также делится на две и этот процесс деления вершин может распространяться на все вершины вплоть до корня, при этом высота дерева увеличивается на единицу.

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

Примеры добавления ключей для случаев 1-3 приведены на рис. 2.11, а для случая 4 – на рис. 2.12.

 

Рис.2.11

а) до добавления ключей 7, 37, 57;

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

 

 

Рис. 2.12

а) до добавления ключа 60;

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

 

 

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 и организации

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