Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Топ:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Интересное:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Дисциплины:
2017-11-16 | 154 |
5.00
из
|
Заказать работу |
|
|
Операция добавления ключей в В-дерево начинается с выполнения операции поиска, когда аргумент поиска равен значению нового ключа. Если ключ действительно новый, то поиск завершится неудачно обнаружением некоторой вершины-листа. При этом возможны 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 и организации
новой корневой вершины.
|
|
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!