Составители:
77
будет констатировать превосходство NTFS. Поиск файла в каталоге всегда
предшествует запуску программы или открытию документа.
B-деревья обладают прекрасным качеством: во всех трех операциях
над данными (поиск/удаление/добавление) они обеспечивают сложность
порядка O(h), где h – глубина дерева. Это значит, что чем больше узлов
в дереве и чем сильнее дерево ветвится, тем меньшую часть узлов надо
будет просмотреть, чтобы найти нужный элемент. Попробуем оценить
зависимость временной сложности операций T(h) от высоты дерева h.
Число элементов в вершине есть величина вероятностная с постоян-
ным математическим ожиданием MK. Математическое ожидание числа
вершин равно n/MK ~ n, где n – число элементов, хранимых в B-дереве.
Это дает сложность T(h) ~ O(log n), а это очень хороший результат.
Поскольку вершины могут заполняться не полностью (иметь менее
NumberOfItems элементов), то можно говорить о коэффициенте ис-
пользования памяти. Существуют доказательства, что память будет ис-
пользоваться в среднем на ln2·100% ≈ 69,3%.
В отличие от сбалансированных деревьев, которые рассматриваются
далее, B-деревья растут не вниз, а вверх. Поэтому (и из-за разной струк-
туры узлов) алгоритмы включения или удаления принципиально раз-
личны, хотя цель их в обоих случаях одна – поддерживать сбалансиро-
ванность дерева.
Идея внешнего поиска с использованием техники B-деревьев была
предложена в 1970 году Р. Бэйером и Э. Мак-Крэйтом и независимо от
них примерно в то же время М. Кауфманом. Естественно, что за это
время было предложено ряд усовершенствований B-деревьев, связан-
ных с увеличением коэффициента использования памяти и уменьшени-
ем общего количества расщеплений.
Одно из таких усовершенствований было предложено Р. Бэйером и
Э. Мак-Крэйтом и заключалось в следующем. Если вершина дерева пе-
реполнена, то прежде чем расщеплять эту вершину, следует посмот-
реть, нельзя ли «перелить» часть элементов соседям слева и справа.
При использовании такой методики уменьшается общее количество рас-
щеплений и увеличивается коэффициент использования памяти.
