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 и организации
новой корневой вершины.
Дата добавления: 2017-11-04; просмотров: 638;