B-Дерево

[math]\displaystyle{ B }[/math]-Дерево ([math]\displaystyle{ B }[/math]-Tree) - [math]\displaystyle{ B }[/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]