Чтобы вставить новый элемент в , определите лист, в который должен
быть помещен новый элемент. Если этот узел содержит менее чем 2 * К ключей, то
в нем есть место для вставки нового элемента. Добавьте новый элемент в соответ-
ствующую позицию, чтобы элементы узла были упорядочены.
Если узел уже содержит 2 * К элементов, то места для нового элемента в узле
уже не остается. Чтобы создать необходимое пространство, поделите узел на два
новых узла. Теперь имеется 2 * К + 1 элементов для распределения между двумя
новыми узлами. Разместите К элементов в каждом узле, сохраняя' соответствую-
щий порядок их расположения. Переместите средний элемент в родительский узел.
Например, нужно вставить элемент Q в Б-дерево, показанное на рис. 7.15. Этот
новый элемент принадлежит второму листу, который уже заполнен. Чтобы разбить
узел, поделите элементы J, К, N, Р и Q между двумя новыми узлами. Расположите
элементы J и К в левом узле, а Р и Q - в правом. Затем переместите средний эле-
мент N в родительский узел. На рис. 7.16 изображено полученное дерево. Рис. 7.16. Б-дерево после добавления элемента Q
Деление узла на два называется дроблением сегмента. Когда оно происхо-
дит, родительский узел получает новый ключ и новый указатель. Если родитель-
ский узел уже полон, то добавление нового ключа и указателя также может при-
вести к его дроблению, что, в свою очередь, потребует добавления новой записи
на более высоком уровне и т.д. В наихудшем случае добавление элемента вызы-
вает «цепную реакцию» дробления узлов вплоть до корня.
Когда происходит дробление корня, Б-дерево становится глубже. Это един-
ственный способ увеличить его глубину. Поэтому Б-деревья обладают необычным
свойством - они всегда растут от листьев к корню.
Опубликовал Kest
October 29 2009 10:02:10 ·
0 Комментариев ·
9919 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
