Составители:
76
вторая – соседняя вершина с числом 13. Суммарное число элементов в
этих вершинах не превышает максимального размера вершины, значит,
нам следует произвести слияние вершин. При слиянии элемент 12 ро-
дителя попадает в результирующий узел и удаляется из родителя (рис.
22, в).
Теперь переходим к родителю, из которого был удален элемент, и
проверяем, не является ли он порожним. Опять имеем порожнюю вер-
шину, и необходимо выбрать две соседние вершины (в данном случае:
вершину, из которой был удален элемент 12 и вершину с элементом 17)
и произвести слияние двух вершин. При слиянии получается вершина
с элементами 14 и 17, где 14 позаимствовано у родителя. Естественно,
элемент 14 из родителя удаляется (рис. 22, г).
Поскольку опять был удален элемент родителя, то переходим к роди-
телю и повторяем процесс проверки и слияния. Получаем вершину с
элементами 5 и 11, где 5 позаимствовано у родителя и удалено из него
(рис. 22, д).
Опять переходим к родителю. Поскольку родитель оказывается кор-
нем, то цикл обработки порожних вершин заканчивается. Осталось про-
верить, не пуст ли корень дерева. Корень дерева пуст, поэтому его мож-
но удалить. Новым корнем дерева будет та единственная вершина, на
которую есть ссылка в старом корне. Это вершина с элементами 5 и 11
(рис. 22, е).
В этом случае, как и при поиске, время обработки вершины есть
величина постоянная, пропорциональная размеру вершины, а значит,
временная сложность T(n) алгоритма удаления из B-дерева будет также
пропорциональна O(h), где h – глубина дерева.
1.4.2.3. Общая оценка B-деревьев
Итак, как говорилось ранее, у B-деревьев есть своя сфера примене-
ния: хранение настолько больших массивов информации, что их невоз-
можно целиком разместить в выделяемой оперативной памяти, но тре-
буется обеспечить быстрый доступ к ним. В таких случаях B-деревья
являются хорошим средством программно ускорить доступ к данным.
Ярким примером практического применения B-деревьев является
файловая система NTFS, где B-деревья применяются для ускорения по-
иска имен в каталогах. Если сравнить скорость поиска в этой файловой
системе и в обычной FAT на примере поиска на жестком диске большо-
го объема или в каталоге, содержащем очень много файлов, то можно
