Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Топ:
Оснащения врачебно-сестринской бригады.
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Интересное:
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Дисциплины:
2017-11-16 | 157 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!