Б-ДЕРЕВЬЯ. ОПЕРАЦИИ, СЛОЖНОСТЬ.

Б-деревья - сбалансированные сильно ветвящиеся деревья, удобные для хранения информации на дисках. Характерным для Б-деревьев является их малая высота h. Представление информации во внешней памяти в виде Б-дерева стало стандартным способом в системах баз данных.

В Б-дереве узел может иметь много сыновей, на практике до тысячи. Количество сыновей (максимальное) определяет степень Б-дерева.

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

Применение сильно ветвящихся деревьев - поиск в больших объемах данных, которые не помещаются в оперативную память.

Б-деревья делят на страницы. Мы получаем структуры, которые помещаются в одно окно, тогда поиск идет не вниз, а вширь – вероятность найти объект выше.

Б-дерево порядка n обладает следующими свойствами:

· Каждая страница содержит не более 2n элементов.

· Каждая страница, кроме корневой, содержит не менее nэлементов.

· Каждая страница представляет собой либо лист (не имеет потомков), либо имеет m+1 потомков, где m-число ключей на данной странице.

· Все страницы-листья находятся на одном уровне

m = 3,

(m+1) ключей

Операции:

Поиск ключа: Читаем первую страницу, ищем ключ, если не находим, то переходим по ссылке между 2 наиболее близкими к искомому ключами.

Например: ищем 15 – переходим по ссылке межу 10 и 20 и т.д.

Вставка: сначала с помощью поиска находим место. Если на станице m<2n, то вставляем. Иначе создаем новую страницу-соседа, распределяем 2n ключей между ними, но 1 ключ (по значению средний) уходит наверх на родительскую страницу.

Удаление: Если m>n, то удаляем. Иначе берем элементы с соседней страницы (если не хватает, сливаем 2 страницы вместе).

Для дерева из N элементов для выполнения операций потребуется не более k=log_nNрекурсивных вызовов (обращений к страницам), коэффициент использования памяти = 50%, т. к. страницы всегда заполнены минимум на половину

Не нашли, что искали? Воспользуйтесь поиском: