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

Презентация:



Advertisements
Похожие презентации
Б-деревья Лекция 19. Б-деревья Б-деревья – сбалансированные деревья, обеспечивающие эффективное хранение информации на дисках и других устройствах с прямым.
Advertisements

Лекция 8 Красно-черные деревья План лекции 1.Определение красно-черного дерева и его высота. 2.Вращения 3.Вставка элемента, восстановление структуры дерева.
Задание бинарных деревьев с помощью массивов Обходы деревьев.
Корни и корневые системы.
К созданию архитектуры поисковой системы в наборах документов. Горелов С.С. МГУ им. М.В. Ломоносова механико-математический факультет.
Деревья и их представление в STL Презентацию подготовила Чиркова Ольга, 2 подгруппа, группа 271ПИ.
Дерево это связный ациклический граф. Связность означает наличие путей между любой парой вершин, ацикличность отсутствие циклов и то, что между парами.
Деревья ПОИСКА Дерево поиска – это либо пустое дерево, либо непустое двоичное дерево, в котором все элементы различны и в котором для каждой вершины справедливо.
Графы Лекция 2. Графы Неориентированным графом (графом) называется тройка (V, E, ), где V и E конечные множества и {X V : | X | = 2}. Ориентированным.
Хранение таблиц По строкам По столбцам Строки нескольких таблиц группируются по общему атрибуту.
Соединение вида и разреза на чертеже. Соединение части вида и части разреза : Границей является СПЛОШНАЯ ВОЛНИСТАЯ линия. На части вида линии невидимого.
Алгоритм Эдмондса Лекция 11. Идея алгоритма Эдмондса Пусть есть некоторое паросочетание M, построим M-чередующийся лес F. Начинаем с множества S вершин.
МЕТОД ОБЛАСТЕЙ В РЕШЕНИИ И ИССЛЕДОВАНИИ В ЗАДАЧАХ С ПАРАМЕТРАМИ МЕТОД ОБЛАСТЕЙ В РЕШЕНИИ И ИССЛЕДОВАНИИ В ЗАДАЧАХ С ПАРАМЕТРАМИ.
Лекция 2 КИНЕМАТИЧЕСКИЙ АНАЛИЗ СООРУЖЕНИЙ. Внешняя нагрузка может вызвать значительные перемещения элементов сооружения, в результате чего оно может перестать.
БАЗЫ ДАННЫХ. Тест.. БАЗЫ ДАННЫХ. 1. База данных - это: А. совокупность данных, организованных по определенным правилам; Б. совокупность программ для хранения.
ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекции Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ, ХНУРЭ Компьютерная.
Операционные системы и среды. Схема устройства жесткого диска Дорожка N Сектор (блок) Пластина 1 Пластина 2 Цилиндр 0 сторона Диск – одна или несколько.
1 БАЗЫ ДАННЫХ СТРУКТУРЫ ДАННЫХ. 2 МОДЕЛИ СТРУКТУР ДАННЫХ Линейная структура (списки и кольца) Линейная структура (списки и кольца) Иерархическая структура.
ИССЛЕДОВАНИЕ ДЕРЕВА РЕШЕНИЙ В РЕАЛИЗАЦИИ МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА Ермошин А.С., Плиско В.А. (МГУПИ)
Подготовила: Бовина Елена М-063. это информационная модель, позволяющая в упорядоченном виде хранить данные о группе объектов, обладающих одинаковым набором.
Транксрипт:

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

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

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

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

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

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

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