Разделение страниц
В отличие от B-деревьев, предложенные нами BST-деревья не сбалансированы. Заметим, что так как минимальное дерево T полностью определяется множеством ключей K, которые оно хранит, мы не можем никак повлиять на его высоту. Под высотой BST-дерева подразумевается высота дерева его веток, т.к. именно этим определяется количество блоков, которые необходимо прочитать, чтобы найти вершину в худшем случае. Кроме того, нашей задачей является избежать большого числа “полупустых” блоков.
Процедура выделения места в странице подразумевает разделение страницы и вызывается только в том случае, если на странице не хватает места для вставки нового узла. Мы используем два очень простых алгоритма разделения страниц.
Первый из них вызывается в случае, если на странице расположено несколько веток. В этом случае мы разделяем ветки страницы на два непересекающихся набора P1 и P2, такие, что |∑w∈P1w(B)— ∑w∈P2w(B)| минимальна по всем возможным разделениям P1 и P2. Т.е. эти наборы должны разделять ветки примерно пополам по их общему размеру. Это можно сделать, например, с помощью жадного алгоритма. Каждый из этих наборов записывается в отдельную страницу, а ссылки обновляются. Данная операция затрагивает ровно три блока.
Второй алгоритм вызывается в случае, если на странице, в которую происходит добавление, осталась только одна ветка. В этом случае мы выделяем корень Pp этой ветки следующим образом. Находим первую вершину от корня, которая содержит N>1 ссылок. У этой вершины есть N дочерних вершин, которые будут корнями N новых веток, оставшихся на данной странице. Корневое множество вершин Pp мы удаляем из данной страницы и целиком переносим в ветку-предок. Чтобы гарантировать возможную вставку в исходную страницу, применяем к ней первый алгоритм разделения. Если исходная ветка являлась корневой, то множество вершин Pp помещается в новую страницу. Может оказаться, что в странице, хранящей ветку-предок, не хватит места для вставки Pp. В этом случае вызывается процедура выделения свободного места для страницы предка. Данная процедура затрагивает ровно три страницы без учёта возможного рекурсивного вызова.
Проблемой могут оказаться строки, по размеру превышающие h страниц, где h — высота дерева в страницах. В этом случае мы можем не найти в ветке вершину, которую можно “перенести” в верхнюю ветку. Тогда, в нашей реализации, строка разбивается на две (возможно нарушая минимальность дерева), и листовую часть строки представляется правильным вынести в отдельную страницу. Это практически является аналогом страниц переполнения для B-деревьев, но не будет приводить к постоянному чтению этой страницы, т.к. любая исходная строка сравнивается в нашем дереве не более одного раза.
