4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 30: | Строка 30: | ||
== Варианты и расширения == | == Варианты и расширения == | ||
Кнут [16] определяет B*-дерево как B-дерево, для которого свойство 3 определения 1 меняется следующим образом: каждая вершина, помимо корневой, содержит не менее 2m/3 ключей | Кнут [16] определяет ''B*-дерево'' как B-дерево, для которого свойство 3 определения 1 меняется следующим образом: каждая вершина, помимо корневой, содержит не менее 2m/3 ключей. | ||
Хаддлстон и Мельхорн [ ] расширили определение 1 для описания более общего класса деревьев многоканального поиска, включающего класс B-деревьев в качестве частного случая. Введенный ими класс так называемых (a, b)-деревьев параметризован двумя целыми числами a и b, удовлетворяющими условиям: a > | ''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]. |
правка