Оценка быстродействия

Оценим время поиска в В-дереве. Рассмотрим, к скольким узлам в наихудшем случае будет происходить обращение при поиске в В-дереве порядка m. Пусть В-дерево содержит N ключей и имеет высоту h. Число ключей на уровнях 1,2,3…h не менее 1, 2(m/2), 2(m/2)², 2(m/2)³…2(m/2)^h-1, следовательно

(11)

или

(12)

Так как при поиске происходит обращение не более чем к h узлам, то эффективность весьма высока, например, при m=200 и N=10⁶, имеем h=4.

При вставке может потребоваться расщепить h узлов. Однако среднее число расщеплений невелико. Поскольку любой новый узел, кроме корня, создается как результат расщепления, то суммарное число расщеплений, выполненное при построении дерева из Р узлов, равно Р-1. В дереве не менее чем ключей, следовательно, . Это означает, что среднее число расщеплений, приходящееся на вставку одного ключа, меньше чем .

Реально фиксируемой для В-дерева величиной является размер узла (страницы), а порядок m вычисляется исходя из размера записи.

Контрольные вопросы

1) Дайте словесное описание алгоритма вставки записей в таблицу, организованную как бинарное дерево.

2) Как удалить запись из таблицы, организованной как бинарное дерево?

3) Дайте оценку трудоёмкости поиска в случайном дереве.

4) Дайте словесное описание алгоритма построения оптимального дерева.

5) Приведите определение сбалансированного дерева.

6) Выведите выражение для максимальной высоты сбалансированного дерева.

7) Как выполняется восстановление балансировки?

8) Опишите алгоритм поиска записи по индексу в древовидной таблице.

9) Приведите определение B-дерева.

10) Опишите алгоритмы вставки, поиска и удаления для В-дерева.

11) Оцените время, необходимое для выполнения операций поиска и вставки в В-дерево.