B-дерево (дерево многоканального поиска): различия между версиями

Перейти к навигации Перейти к поиску
Строка 30: Строка 30:
== Варианты и расширения ==
== Варианты и расширения ==


Кнут [16] определяет B*-дерево как B-дерево, для которого свойство 3 определения 1 меняется следующим образом: каждая вершина, помимо корневой, содержит не менее 2m/3 ключей.
Кнут [16] определяет ''B*-дерево'' как B-дерево, для которого свойство 3 определения 1 меняется следующим образом: каждая вершина, помимо корневой, содержит не менее 2m/3 ключей.
B+-дерево представляет собой листовое B-дерево, то есть B-дерево, в котором ключи хранятся только в листьях. Кроме того, листья привязываются по порядку слева направо, что позволяет осуществлять быстрый последовательный обход ключей, хранящихся в дереве. Элементы маршрутизации в листовом дереве обычно являются копиями определенных ключей, хранящихся в листьях (ключ keyi [v] может быть установлен равным максимальному ключу, хранящемуся в поддереве с корнем в ci [v]) однако вполне подойдет любой набор элементов маршрутизации, для которого выполняются свойства 5 и 6 определения 1.


Хаддлстон и Мельхорн [ ] расширили определение 1 для описания более общего класса деревьев многоканального поиска, включающего класс B-деревьев в качестве частного случая. Введенный ими класс так называемых (a, b)-деревьев параметризован двумя целыми числами a и b, удовлетворяющими условиям: a > 2, 2a — 1 < b. Свойство 2 определения 1 изменяется таким образом, что каждая вершина может иметь до b потомков, а свойство 3 теперь гласит, что все вершины (a; b)-дерева, за исключением корня и листьев, имеют по меньшей мере a потомков. Остальные свойства определения 1 в случае (a, b)-деревьев остаются неизменными. Обычно (a, b)-деревья реализуются как листовые деревья.
''B<math>^+</math>-дерево'' представляет собой ''листовое B-дерево'', то есть B-дерево, в котором ключи хранятся только в листьях. Кроме того, листья привязываются по порядку слева направо, что позволяет осуществлять быстрый последовательный обход ключей, хранящихся в дереве. Элементы маршрутизации в листовом дереве обычно являются копиями определенных ключей, хранящихся в листьях (ключ <math>key_i[v] \; </math> может быть установлен равным максимальному ключу, хранящемуся в поддереве с корнем в <math>c_i[v] \; </math>), однако вполне подойдет любой набор элементов маршрутизации, для которого выполняются свойства 5 и 6 определения 1.
 
Хаддлстон и Мельхорн [13] расширили определение 1 для описания более общего класса деревьев многоканального поиска, включающего класс B-деревьев в качестве частного случая. Введенный ими класс так называемых ''(a, b)-деревьев'' параметризован двумя целыми числами a и b, удовлетворяющими условиям: <math>a \ge 2 \; </math> и <math>2a \; </math><math>1 \le b \; </math>. Свойство 2 определения 1 изменяется таким образом, что каждая вершина может иметь до b потомков, а свойство 3 теперь гласит, что все вершины (a; b)-дерева, за исключением корня и листьев, имеют по меньшей мере a потомков. Остальные свойства определения 1 в случае (a, b)-деревьев остаются неизменными. Обычно (a, b)-деревья реализуются как листовые деревья.


Согласно этому определению, B-дерево представляет собой (b/2; b)-дерево, если b является четным, или (a; 2a – 1)-дерево (для нечетных b). Небольшое различие между четной и нечетной максимальной степенью приобретает значимость в контексте важного утверждения Хаддлстона и Мельхорна об амортизации (см. ниже), в котором должно выполняться неравенство b > 2. Это утверждение в конечном итоге привело к тому, что (a, b)-деревья с b > 2a получили специальное название – слабые B-деревья [13].
Согласно этому определению, B-дерево представляет собой (b/2; b)-дерево, если b является четным, или (a; 2a – 1)-дерево (для нечетных b). Небольшое различие между четной и нечетной максимальной степенью приобретает значимость в контексте важного утверждения Хаддлстона и Мельхорна об амортизации (см. ниже), в котором должно выполняться неравенство b > 2. Это утверждение в конечном итоге привело к тому, что (a, b)-деревья с b > 2a получили специальное название – слабые B-деревья [13].
4551

правка

Навигация