Стр. 48 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
46
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
1. Каждая страница содержит
m
<= 2
n
ключей, где
n
= const, называемая
кратностью дерева.
2. Каждая страница, кроме корневой, содержит
m
>=
n
ключей, где
n
–
кратность.
3. Внутри страницы ключи упорядочены.
4. Каждая страница либо является листом (нет дочерних страниц), либо
имеет (
m
+1) дочернюю страницу, где
m
– число ключей в ней.
5. Все страницы–листья – лежат на одном уровне. Следовательно,
В
-
дерево не нуждается в балансировке.
Пример
В
-дерево порядка
n
= 2,
n
≤
m
≤2
n
Поиск ключа 14.
25
10 20
30 40
2 5 7 8
13 14 15 18
22 24
26 27 28
32 33 38
41 42 45 46
P
0
P
1
P
0
P
1
P
2
P
0
P
1
P
2
m=
1
m=
2
m=
2
m=
4
m=
4
m=
2
m=
3
m=
3
m=
4
Рис. 47. Пример B-дерева
1. Считываем корневую страницу.
z
< 25. Переходим на
P
0
.
2. Считываем в оперативную память страницу с адресом
P
0
. Адреса
должны храниться в странице так же, как и ключи.
3. В текущей странице ключа
z
также не находим, но обнаруживаем, что он
находится между ключами 10 и 20, и потому переходим по ссылке
P
1
.
4. В текущей странице находим искомый ключ - <успех>.
