Лекция 9 Б-деревья План лекции 1.Структуры данных на диске 2.Определение Б-дерева. 3.Высота Б-дерева. 4.Поиск в Б-дереве 5.Создание пустого дерева. 6.Разбиение. - презентация

1 Лекция 9 Б-деревья План лекции 1.Структуры данных на диске 2.Определение Б-дерева. 3.Высота Б-дерева. 4.Поиск в Б-дереве 5.Создание пустого дерева. 6.Разбиение вершины дерева на две. 7.Добавление элемента в Б-дерево. 8.Удаление элемента из Б-дерева.

2 Структуры данных на диске

3 Б – дерево и данные на диске

4 Определение Б – дерева (1) Б – дерево – корневое дерево, такое что Каждая вершина содержит поля, в которых хранятся: –Количество n[x] ключей, хранящихся в ней; –Сами ключи key 1 [x]

5 Определение Б – дерева (2) Ключи key i [x] служат границами, разделяющими значения ключей в поддеревьях k 1

6 Определение Б – дерева (3) Число ключей, хранящихся в одной вершине, ограничено сверху и снизу, границы задаются единым для всего дерева числомt t>=2 (минимальной степенью Б-дерева). Именно: a)каждая вершина, кроме корня, содержит по меньшей мере t-1ключей внутренние вершины имеют не менее t детей. Если дерево не пусто, то в корне должен храниться хотя бы 1 ключ b)В вершине хранится не более 2t-1 ключей. Следовательно внутренняя вершина имеет не более 2t детей. Вершина, хранящая 2t-1 ключей называется полной.

7 Высота Б - дерева h