4551
правка
B-дерево (дерево многоканального поиска): различия между версиями
Перейти к навигации
Перейти к поиску
B-дерево (дерево многоканального поиска) (посмотреть исходный код)
Версия от 13:22, 1 ноября 2012
, 1 ноября 2012→Варианты и расширения
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 36: | Строка 36: | ||
Хаддлстон и Мельхорн [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)-деревья реализуются как листовые деревья. | Хаддлстон и Мельхорн [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 > | Согласно этому определению, B-дерево представляет собой (b/2; b)-дерево, если b является четным, или (a; 2a – 1)-дерево (для нечетных b). Небольшое различие между четной и нечетной максимальной степенью приобретает значимость в контексте важного утверждения Хаддлстона и Мельхорна об амортизации (см. ниже), в котором должно выполняться неравенство <math>b \ge 2 \; </math>. Это утверждение в конечном итоге привело к тому, что (a, b)-деревья с <math>b \ge 2a \; </math> получили специальное название – ''слабые B-деревья'' [13]. | ||
== Операции обновления == | == Операции обновления == | ||