Презентация

Титул
1
2
3
4
5
6
7
8
9
10

B-деревья

С точки зрения внешнего логического представления B-дерево - это сбалансированное сильно ветвистое дерево во внешней памяти. Сбалансированность означает, что длина пути от корня дерева к любому его листу одна и та же. Ветвистость дерева - это свойство каждого узла дерева ссылаться но большое число узлов-потомков. С точки зрения физической организации B-дерево представляется как мультисписочная структура страниц внешней памяти, т.е. каждому узлу дерева соответствует блок внешней памяти (страница).
B-дерево порядка n представляет собой совокупность иерархически связанных страниц внешней памяти (каждая вершина дерева - страница), обладающая следующими свойствами:

Каждая страница содержит не более 2*n элементов (записей с ключом).
Каждая страница, кроме корневой, содержит не менее n элементов.
Если внутренняя (не листовая) вершина B-дерева содержит m ключей, то у неё имеется m+1 страниц-потомков.
Все листовые страницы находятся на одном уровне.

Внутренние и листовые страницы обычно имеют разную структуру. В типовом случае структура внутренней страницы выглядит следующим образом:

N(1) key(1) N(2) key(2) .... N(n) key(n)

При этом выдерживаются следующие свойства:

ключ(1) <= ключ(2) <= ... <= ключ(n);
в странице дерева Nm находятся ключи k со значениями ключ(m) <= k <= ключ(m+1).

Листовая страница обычно имеет следующую структуру:

key(1) key(2) .... key(n)

Листовая страница обладает следующими свойствами:

ключ(1) < ключ(2) < ... < ключ(t);
листовые страницы связаны одно- или двунаправленным списком.