4551
правка
B-дерево (дерево многоканального поиска): различия между версиями
Материал из WEGA
B-дерево (дерево многоканального поиска) (посмотреть исходный код)
Версия от 13:04, 1 ноября 2012
, 1 ноября 2012нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 8: | Строка 8: | ||
== Нотация == | == Нотация == | ||
B-дерево представляет собой дерево многоканального поиска, определенное следующим образом (определение Байера и Маккрейта [ ] было переформулировано Кнутом [16, глава 6.2.4] и Корменом и коллегами [10, глава 18.1]): | ''B-дерево'' представляет собой дерево многоканального поиска, определенное следующим образом (определение Байера и Маккрейта [6] было переформулировано Кнутом [16, глава 6.2.4] и Корменом и коллегами [10, глава 18.1]): | ||
Определение 1. Пусть m > | '''Определение 1.''' Пусть <math>m \ge 3</math> – целое положительное число. Дерево T представляет собой ''B-дерево степени m'', если оно пусто или удовлетворяет следующим условиям: | ||
1. Все листья T находятся на одном и том же уровне T. | |||
2. Каждая вершина T имеет не более m потомков. | 1. Все листья T находятся на одном и том же уровне T. | ||
3. Каждая вершина T, кроме корня и листьев, имеет по крайней мере m/2 потомков. | |||
4. Корень T либо является листом, либо имеет не менее двух потомков. | 2. Каждая вершина T имеет не более m потомков. | ||
5. Внутренняя вершина, имеющая k потомков c1 [ v], ... , c^[v], хранит k – 1 ключей; лист хранит от m/2 – 1 до m – 1 ключей. Ключи keyi [v], 1 < i < k – 1 вершины v 2 T < | |||
3. Каждая вершина T, кроме корня и листьев, имеет по крайней мере m/2 потомков. | |||
4. Корень T либо является листом, либо имеет не менее двух потомков. | |||
5. Внутренняя вершина, имеющая k потомков c1 [ v], ... , c^[v], хранит k – 1 ключей; лист хранит от m/2 – 1 до m – 1 ключей. Ключи keyi [v], 1 < i < k – 1 вершины v 2 T < | |||
хранятся в порядке сортировки, т.е. keyjv] < | хранятся в порядке сортировки, т.е. keyjv] < | ||
6. Если v – внутренняя вершина T с k потомками c1 [v],..: ; Cfc[v], то k – 1 ключей keyjv],].. ,keyi_1[v] вершины v делят диапазон ключей, хранящихся в поддеревьях с корнем в вершине потомков v. Если xi – любой ключ, хранящийся в поддереве, корнем которого является ci [v], выполняется следующее соотношение: | 6. Если v – внутренняя вершина T с k потомками c1 [v],..: ; Cfc[v], то k – 1 ключей keyjv],].. ,keyi_1[v] вершины v делят диапазон ключей, хранящихся в поддеревьях с корнем в вершине потомков v. Если xi – любой ключ, хранящийся в поддереве, корнем которого является ci [v], выполняется следующее соотношение: | ||
