Основные достоинства

Рис. 1. В-дерево с согласными английского алфавита в качестве ключей

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

Основные достоинства

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

- Неизменная упорядоченность по ключу обеспечивает возможность эффективной пакетной обработки.

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

-Произвольный доступ к записи реализуется посредством малого количества подопераций (обращения к физическим блокам).

Основной недостаток В-деревьев состоит в отсутствии для них эффективных средств выборки данных (т.е. метода обхода дерева), упорядоченных по отличному от выбранного ключу.

Б-деревья также представляют собой сбалансированные деревья, поэтому время выполнения стандартных операций в них пропорционально высоте. Но, в отличие от остальных деревьев, они созданы специально для эффективной работы с дисковой памятью, а точнее — они минимизируют обращения типа ввода-вывода.

Б-деревом (B-tree) называем корневое дерево, устроенное следующим образом:

1. Каждый узел (вершина) содержит поля, в которых хранятся:

а) количество n[x] ключей, хранящихся в ней;

б) сами ключи, количество которых равно n[x] и которые хранятся в неубывающем порядке, так что key₁[x]=<key₂[x]=< … =<key_n[x][x];

в) Логическое значение leaf[x], равное TRUE, если x является листом, и FALSE, если x – внутренний узел.

2. Кроме того, каждый внутренний узел x содержит n[x]+1 указателей c₁[x], c₂[x], …, c_n[x]+1[x] на дочерние узлы. Листья не имеют дочерних узлов, так что их поля c _i не определены.

3. Ключи key_i[x] разделяют поддиапазоны ключей, хранящихся в поддеревьях: если k_i – произвольный ключ, хранящийся в поддереве с корнем c_i[x], то k₁ =< key₁[x] =< k₁=< key₂[x] =< … =< key_n[x][x] =< k_n[x]+1.

4. Все листья расположены на одной и той же глубине, которая равна высоте дерева h.

5. Имеются нижняя и верхняя границы количества ключей, которые могут содержаться в узле. Эти границы могут быть выражены с помощью одного фиксированного целого числа t=>2, называемого минимальной степенью Б-дерева:

а) Каждый узел, кроме корневого, должен содержать как минимум t-1 ключей. Каждый внутренний узел, не являющийся корневым, имеет, таким образом, как минимум t дочерних узлов. Если дерево не является пустым, корень должен содержать как минимум один ключ.

б) Каждый узел содержит не более 2t-1 ключей. Таким образом, внутренний узел имеет не более 2t дочерних узлов. Говорят, что узел заполнен (full), если он содержит ровно 2t-1 ключей.

Простейшее Б-дерево получается при t=2. При этом каждый внутренний узел может иметь 2,3 или 4 дочерних узла, и мы получаем так называемое 2-3-4 дерево( 2-3-4 tree). Однако, обычно на практике используются гораздо большие значения t.

Рисунок 2. Б-дерево, высота которого равна 3, с минимально возможным количеством ключей.

Date: 2015-06-11; view: 390; Нарушение авторских прав