27. Б-деревья и их свойства. Включение в Б-дерево. Исключение из Б-дерева

 

                Существует практическая область применения сильно ветвящихся (не бинарных) деревьев. Такие деревья удобно использовать для формирования и поддержания крупномасштабных деревьев поиска, в которых необходимо выполнять и включение новых элементов, и удаление старых, но для которых либо не хватает оперативной памяти, либо она слишком дорога, чтобы использовать ее для долговременного хранения.

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

                Если происходит обращение к одному элементу, расположенному во внешней памяти, то без больших затрат можно обратиться и к целой группе элементов; поэтому в каждой вершине дерева располагается не один элемент, а группа элементов, называемых страницей.

                Обращение к странице требует всего одного обращения к диску, что позволяет значительно сэкономить время на числе обращений и, тем самым, снизить сложность алгоритмов поиска, включения и исключения.

                Пример. Пусть дерево организовано таким образом, что каждая страница содержит 100 элементов, а вершина, в которой хранится эта страница, имеет 101-го потомка. Тогда поиск в дереве с миллионом элементов будет в среднем требовать log100(106)=3 обращения к страницам, тогда как для двоичного и не разбитого на страницы дерева это число составляет в среднем log2(106)=20 обращений.

                Конечно, если дерево растет случайным образом, то в худшем случае может потребоваться и 106/100=104 обращений. Поэтому для сильно ветвящихся деревьев также необходима некоторая схема управления их ростом.

                Рис. 1.

 

                Идеальная сбалансированность требует слишком больших затрат на балансировку. Разумный критерий был сформулирован в 1970 году Р. Бэйером и Е. Маккресттом: каждая страница (кроме, быть может, корневой) должна содержать при заданном фиксированном n от n до 2n вершин.

                Соблюдение этого критерия позволяет осуществить поиск элемента по ключу в дереве с N элементами максимум за lognN обращений к вершинам этого дерева. Кроме того, каждая страница заполнена не менее чем на половину, а значит, коэффициент использования памяти составляет не менее 50%.

                Б-деревом называется сильно ветвящееся дерево, обладающее следующими свойствами:

                1. При заданном натуральном n каждая страница, кроме корневой, содержит не менее n и не более 2n элементов. Корневая страница может содержать от 1 до 2n элементов.

                2. Каждая страница, содержащая m элементов, либо является концевой, либо имеет ровно m+1 потомка.

                3. Все концевые вершины находятся на одном уровне.

                Если спроецировать Б-дерево на горизонтальную прямую, включая ключи потомков между ключами их родительских элементов, то ключи будут расположены в порядке неубывания.

                На рис. 1 показан пример Б-дерева при n=2.

                Каждая страница Б-дерева организована в виде массива с размерностью [1..2n], причем элементы массива располагаются на странице в порядке неубывания их ключей (рис. 2).

                Рис. 2. Схема организации информации на странице Б-дерева.

 

                Подобная организация Б-деревьев представляет собой естественное развитие принципа двоичных деревьев и определяет метод поиска элемента с заданным ключом.

 

Поиск элемента в Б-дереве

 

                Считываем страницу в оперативную память и пользуемся обычным методом поиска среди ключей k1, k2, ... km. Если число m достаточно большое, то можно воспользоваться дихотомическим поиском, в противном случае можно использовать последовательный поиск. Какой вид поиска выбрать - здесь неважно, так как время, затрачиваемое на поиск в оперативной памяти, как правило, пренебрежимо мало по сравнению с временем пересылки страницы из внешней памяти в оперативную. При поиске элемента с заданным ключом x возможны следующие ситуации:

                1. x=ki при некотором i (1<=i<=m): искомый элемент найден;

                2. ki<x<ki+1 при некотором i (1<=i<m): поиск продолжается на странице с адресом pi;

                3. x<k1: поиск продолжается на странице с адресом p0;

                2. km<x: поиск продолжается на странице с адресом pm.

                Если на некотором шаге окажется, что pi=nil, то это означает, что в Б-дереве нет элемента с данным ключом х. В этом случае в ходе поиска несуществующего элемента в оперативную память будет перегружено максимум k= lognN страниц; поэтому значение n необходимо выбрать таким образом, чтобы эти k страниц поместились в оперативную память.

                На самом деле приходится учитывать возможность хранения более чем k страниц, поскольку, как мы увидим в дальнейшем, включение элементов в Б-дерево может приводить к разделению страниц. Кроме того, в оперативной памяти следует постоянно хранить корневую страницу, так как с нее всякий раз начинается любой поиск.

 

Включение элемента в Б-дерево

 

                Включение нового элемента осуществляется только на концевые страницы, т.е. страницы нижнего уровня.

                I случай. Новый элемент е нужно поместить на страницу с m<2n элементами. В этом случае процесс включения затрагивает только эту страницу. Алгоритм включения:

                1. Установить, что элемент е отсутствует в дереве.

                2. Определить страницу и позицию r на странице, в которую следует поместить элемент е.

                3. Сдвинуть на одну позицию вправо элементы этой страницы с r-го по m-й.

                4. Вставить новый элемент е в позицию r.

                5. Увеличить размер страницы на единицу.

                II случай. Новый элемент е нужно поместить на страницу с m=2n элементами. Алгоритм включения:

                Рис. 3.

                1. Установить, что элемент е отсутствует в дереве.

                2. Определить страницу А в которую следует поместить элемент и убедиться, что эта страница уже полна.

                3. Создать чистую страницу В.

                4. Элементы со страницы А вместе с новым элементом е (всего их 2n+1) поровну распределяются между страницами А и В, причем элемент со средним ключом переносится на один уровень вверх на родительскую страницу.

                5. Размеры страниц А и В положить равными n, увеличить на единицу размер родительской страницы.

                Если включение в родительскую страницу вновь приводит к переполнению страницу, то разделение надо повторить уже на уровне родительской страницы. В крайнем случае разделение придется проводить на всех уровнях, включая корневой. Фактически только тогда может появиться новая корневая страница, и, следовательно, увеличиться высота Б-дерева. Так что Б-деревья растут несколько странно: от листьев к корню.

 

Исключение элемента из Б-дерева

 

                I случай. Исключаемый элемент е находится на концевой странице Р. Пусть удаляемый элемент занимает позицию r. Алгоритм исключения:

                1. Удалить со страницы Р элемент е.

                2. Сдвинуть на одну позицию влево элементы этой страницы с r+1-го по m-й.

                3. Уменьшить размер страницы Р на единицу.

 

                II случай. Исключаемый элемент е с ключом ki находится не на концевой странице. В этом случае его следует заменить одним из двух лексикографически смежных элементов. Поиск смежного элемента похож на поиск при исключении из двоичного дерева: сначала спускаемся вниз влево на дочернюю страницу в направлении ссылки pi-1, а затем продолжаем спускаться вниз вдоль самых правых ссылок до листовой страницы Р. Алгоритм исключения:

                1. В качестве смежного элемента взять самый правый элемент со страницы Р.

                2. Заменить исключаемый элемент на смежный.

                3. Уменьшить размер страницы Р на единицу.

 

                В обоих случаях может оказаться, что размер страницы Р сократился до n-1, т.е. на странице Р осталось недопустимо мало элементов. В этом случае надо попытаться позаимствовать недостающий элемент на соседней с Р странице Q. Если размер страницы Q больше n, то это можно сделать. Более того, уж если приходится вызывать дополнительную страницу в оперативную память, то лучше взять не один, а несколько элементов, распределив элементы страниц Р и Q поровну на обе страницы. Этот процесс, называемый балансировкой страниц, затрагивает также и родительский элемент страниц Р и Q: возможно, что он спустится на одну из этих страниц, а на его место поднимется элемент снизу.

                В худшем случае слияние страниц может распространиться вверх до самой корневой страницы. Если корень сократился до нулевого размера, то он удаляется, и высота Б-дерева уменьшается.