4551
правка
B-дерево (дерево многоканального поиска): различия между версиями
Перейти к навигации
Перейти к поиску
B-дерево (дерево многоканального поиска) (посмотреть исходный код)
Версия от 13:16, 1 ноября 2012
, 1 ноября 2012→Нотация
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 24: | Строка 24: | ||
6. Если v – внутренняя вершина T с k потомками <math>c_1[v], ..., c_k[v] \; </math>, то k – 1 ключей <math>key_1[v], ... ,key_{k-1}[v] \; </math> вершины v делят диапазон ключей, хранящихся в поддеревьях с корнем в вершине потомков v. Если <math>x_i \; </math> – любой ключ, хранящийся в поддереве, корнем которого является <math>c_i[v] \; </math>, выполняется следующее соотношение: | 6. Если v – внутренняя вершина T с k потомками <math>c_1[v], ..., c_k[v] \; </math>, то k – 1 ключей <math>key_1[v], ... ,key_{k-1}[v] \; </math> вершины v делят диапазон ключей, хранящихся в поддеревьях с корнем в вершине потомков v. Если <math>x_i \; </math> – любой ключ, хранящийся в поддереве, корнем которого является <math>c_i[v] \; </math>, выполняется следующее соотношение: | ||
<math>x_1 \le key_1[v] \le x_2 \le key_2[v] \le ... \le x_{k-1} \le key_{k-1}[v] \le x_k \; </math> | |||
Чтобы произвести поиск по B-дереву для заданного ключа x, алгоритм начинает с корня дерева, которым является текущая вершина. Если x соответствует одному из ключей текущей вершины, поиск успешно завершается. В противном случае, если текущая вершина представляет собой лист, поиск завершается неуспешно. Если ключи текущей вершины не содержат x, а текущая вершина не является листом, алгоритм определяет уникальное поддерево с корнем в потомке текущей вершины, которое может содержать x, и рекурсивно исполняется для этого поддерева. Поскольку процесс поиска управляется ключами вершины, они также называются элементами маршрутизации. | Чтобы произвести поиск по B-дереву для заданного ключа x, алгоритм начинает с корня дерева, которым является текущая вершина. Если x соответствует одному из ключей текущей вершины, поиск успешно завершается. В противном случае, если текущая вершина представляет собой лист, поиск завершается неуспешно. Если ключи текущей вершины не содержат x, а текущая вершина не является листом, алгоритм определяет уникальное поддерево с корнем в потомке текущей вершины, которое может содержать x, и рекурсивно исполняется для этого поддерева. Поскольку процесс поиска управляется ключами вершины, они также называются ''элементами маршрутизации''. | ||
== Варианты и расширения == | == Варианты и расширения == | ||