между Ki и Ki+i, следует загрузить в оперативную память узел, на который указывает Pi, и продолжить процесс. Если аргумент поиска меньше Кх, используется указатель Ро," при аргументе, большем Kj, для продолжения поиска применяется указатель Pj. Если Р, = Л, значит, поиск завершился неудачно.

Приятная особенность S-деревьев заключается в простоте вставки. Рассмотрим, например, рис. 30. Каждый лист соответствует месту, где может быть выполнена новая вставка. Чтобы вставить новый ключ 337, просто заменим соответствующий узел

со t~. О М -Ч*

узлом

о М -н t- t-О - « М «г

со М со М со

с другой стороны, при попытке вставить новый ключ 071 (программистам на С/ C-f-f: не примите случайно это число (071) за восьмеричную запись числа 57 :-). - Прим. перев.) можно обнаружить, что места для него нет, поскольку соответствующий узел на втором уровне заполнен до отказа. Однако эта неприятность легко преодолевается путем разбиения узла на две части с тремя ключами в каждой и передачи среднего ключа на первый уровень:

со , (О , О! .

о / о \ о

□□□□□□□□

•-ч t- Ф со со

«Г Ю t- t- 00

ООО ООО

□аой □□□□

В целом, чтобы вставить новый элемент в S-дерево порядка т, в котором все листья расположены на уровне /, необходимо вставить новый ключ в подходящее место на уровне / - 1. Если соответствующий узел содержит m ключей, т. е. имеет вид (1) с j = т, разбиваем его на два узла

>-ir-

и вставляем ключ Кгп/2] в родительский по отношению к данному узлу узел (другими словами, указатель Р в родительском узле заменяется последовательностью Р, Кт/!], Р)- Такая вставка может привести к аналогичному делению родительского узла (см. рис. 27, на котором показан случай д.пя m = 3). При необходимости разделить корневой узел - сироту без родителя - просто создаем новый корневой узел, содержащий единственный ключ Кгп/2] i дерево при этом прибавляет в росте и становится на единицу выше.

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

Операция удаления из В-дерева немногим сложнее вставки (см. упр. 6).

307 313 331 347

Рис. 30. В-дерево порядка 7 с листьями, расположенными на третьем уровне. Каждый узел содержит 3, 4, 5 или 6 ключей. Лист, предшествующий ключу 449, помечен символом А (см. (8)).

Верхняя граница времени работы. Посмотрим теперь, к скольким узлам потребуется обратиться в наихудшем случае при поиске в В-дереве порядка т. Предположим, что имеется 7V ключей и на уровне / имеется 7V-I-1 лист. Тогда количество узлов на уровнях 1,2,3,... равно как минимум 2, 2 [т/2], 2 [т/2], ...; следовательно,

7V+1 > 2[m/2l-i. (5)

Другими словами,

<i + logr/2i(-); (6)

это означает, например, что если N = 1999 998 и m = 199, то I не превышает 3. Поскольку в процессе поиска нам необходим доступ по крайней мере к I узлам, данная формула гарантирует, что время работы алгоритма весьма мало.

При вставке нового узла может потребоваться разделить до / узлов, однако среднее количество таких разделений существенно меньше. Общее количество разделений равно общему количеству внутренних узлов минус I. При наличии в дереве р внутренних узлов имеется как минимум 1 -I- ([т/2] - 1)(р - 1) ключей. Следовательно,

Таким образом, среднее количество разделений узлов при построении дерева, содержащего 7V ключей, меньше 1/("т/2] - 1) разделений на узел.

Усовершенствования и изменения. Существует несколько возможностей улучшить методы работы с В-деревьями при небольших изменениях их определения.

Прежде всего, заметим, что все указатели на уровне / - 1 равны Л, а все указатели на других уровнях не равны Л. Зачастую это приводит к значительной потере пространства, так что можно "покорить пространство и время" убрав все Л и использовав другое значение m для всех "нижних" узлов. Подобное применение двух различных т, однако, не ухудшает алгоритма вставки, так как обе половины разделенного узла остаются на том же уровне, что и оригинал. Можно даже определить обобщенное В-дерево порядков mi,m2,m3,..., потребовав, чтобы все некорневые узлы на уровне I - 1 имели от т*,/2 до тпк потомков. Такое В-дерево имеет различные m на каждом уровне, однако алгоритм вставки при этом, в сущности, не меняется.

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

Обратимся вновь к рис. 30 и представим себе, что все записи файла хранятся в листьях и лишь несколько ключей продублировано в узлах ветвей. В таком случае крайний слева лист содержит все записи, для которых ключ < 011; лист, помеченный символом А, содержит записи, удовлетворяющие соотношению

439 <К < 449 (8)