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]-дерево представляет собой структуру данных для двухуровневой памяти.

Литература

• Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.

• Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.

• Кнут Д. Искусство программирования для ЭВМ. — М.: Мир, 1978. — Т. 3. Сортировка и поиск.