B-Дерево

Материал из WEGA
Версия от 13:57, 13 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''<math>B</math>-Дерево''' (''<math>B</math>-Tree'') - <math></math>-дерево порядка <math>m</math> есть <math>m</...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

[math]\displaystyle{ B }[/math]-Дерево ([math]\displaystyle{ B }[/math]-Tree) - [math]\displaystyle{ }[/math]-дерево порядка [math]\displaystyle{ m }[/math] есть [math]\displaystyle{ m }[/math]-арное выровненное дерево, у которого каждая вершина (страница) содержит не более [math]\displaystyle{ m }[/math] и не менее [math]\displaystyle{ m/2 }[/math] слов, корень имеет не менее 2 потомков, каждая страница либо представляет собой висячую вершину, либо имеет [math]\displaystyle{ k+1 }[/math] потомков, где [math]\displaystyle{ k }[/math] --- число слов на этой странице. [math]\displaystyle{ B }[/math]-дерево представляет собой структуру данных для двухуровневой памяти.

Литература

[Кнут],

[Евстигнеев/85],

[Евстигнеев-Касьянов/94]