лекция_11

1.

Лекция
B-деревья, B+-деревья
2026

2. Введение

Сбалансированные деревья
Для чего нужны:
Работа с большим объемом данных при низкой скорости доступа к диску
Высота дерева = количеству операций чтения с диска
B-деревья
Позволяют хранить множество детей => снижается высота дерева
Эффективное чтение/запись блоками
Типовые области применения
Файловые системы, индексные структуры, СУБД
2

3. Сравнение деревьев

?
Простые
Самобалансировка
В худшем случае
вырождаются в
список
Каждый узел
содержит только
двух детей
Высота = O(n)
Высота = O(log n)
Уменьшение высоты
в десятки раз
3

4. B-tree

Б-дерево – сбалансированное сильно ветвистое дерево поиска
Сбалансированное – длины любых двух путей от корня до
листьев различаются не более чем на 1
Ветвистость – свойство каждого узла ссылаться на большое
число узлов-потомков
4

5. B-tree

t – минимальный порядок – основной параметр Б-дерева
Любой внутренний узел (кроме корня) имеет от t до 2t детей
включительно
Корневой узел может иметь меньше детей
Количество ключей в узле (кроме корня) – от t-1 до 2t-1
Значение t?
5

6. B-tree

Каждый узел представляет из себя отсортированные ключи,
между которыми размещаются ссылки на дочерние узлы
При наличии в узле ключей K1..Kn, узел будет иметь X потомков
Первая ссылка содержит значения от -∞ до K1(не включая),
i-ая –