Оглавление
- 1 B-дерево
- 1.1 История и определение B-деревьев
- 1.2 Структура и свойства B-деревьев
- 1.3 Различия в терминологии
- 1.4 Вставка и удаление в B-деревьях
- 1.5 Сравнение с другими деревьями
- 1.6 Варианты B-деревьев
- 1.7 Структура B-дерева
- 1.8 Использование B-дерева в базах данных
- 1.9 Индекс B-дерева
- 1.10 Вставки и удаления
- 1.11 Преимущества B-дерева
- 1.12 Оптимальная и наихудшая высота
- 1.13 Алгоритмы
- 1.14 Создание и разделение узлов
- 1.15 Удаление элементов
- 1.16 Последовательный доступ и массовое строительство
- 1.17 Использование в файловых системах
- 1.18 Сравнение B-дерева и связанного списка
- 1.19 Т-образное дерево
- 1.20 Параллельный доступ
- 1.21 Метод мета-доступа
- 1.22 Параллельные алгоритмы
- 1.23 Кленовое дерево
- 1.24 Другие структуры данных
- 1.25 Рекомендации и источники
- 1.26 Полный текст статьи:
- 2 B-дерево – Arc.Ask3.Ru
B-дерево
-
История и определение B-деревьев
- B-деревья были изобретены Рудольфом Байером и Эдвардом М. Маккрайтом в 1970 году.
- B-деревья поддерживают сортировку данных и логарифмическое время поиска, последовательного доступа, вставки и удаления.
- B-деревья обобщают дерево бинарного поиска, позволяя использовать узлы с более чем двумя дочерними элементами.
- B-деревья подходят для систем хранения, считывающих и записывающих большие блоки данных.
-
Структура и свойства B-деревьев
- Каждый узел имеет не более m дочерних узлов, где m – порядок дерева.
- У корневого узла есть не менее двух дочерних элементов, если он не является листовым.
- Все листья располагаются на одном уровне.
- Неконечный узел с k дочерними элементами содержит k−1 ключей.
- Ключи каждого внутреннего узла действуют как разделительные значения.
-
Различия в терминологии
- Терминология по B-деревьям неоднородна, что приводит к неоднозначности.
- Байер и Маккрайт определяют порядок как минимальное количество ключей в некорневом узле.
- Кнут определяет порядок как максимальное количество дочерних элементов.
- Термин “лист” также неоднозначен, так как конечный уровень может быть на один уровень ниже самых низких ключей.
-
Вставка и удаление в B-деревьях
- Внутренние узлы могут быть объединены или разделены для поддержания диапазона дочерних узлов.
- Количество клавиш выбирается так, чтобы они варьировались в зависимости от d и 2d.
- B-дерево поддерживается сбалансированным путем разделения переполненных узлов и слияния узлов с соседними.
-
Сравнение с другими деревьями
- B-деревья не нуждаются в частой балансировке, но могут занимать пространство из-за неполной заполненности узлов.
- B-деревья эффективны для систем с медленным доступом к данным, таких как дисковые накопители.
- Максимальное количество дочерних узлов зависит от размера дискового блока.
-
Варианты B-деревьев
- Дерево B+ хранит ключи в конечных узлах, ускоряя последовательный доступ.
- Дерево B* балансирует больше соседних узлов, чтобы внутренние узлы были более плотно упакованы.
- B*-деревья откладывают разделение узлов, передавая ключи соседним узлам.
-
Структура B-дерева
- B-дерево делит массив пополам, сохраняя младшие ключи в текущем узле, а средние ключи в родительском узле.
- Если оба родственных узла заполнены, они разделяются на три, и ключ перемещается вверх по дереву.
- Удаление узлов сложнее, чем вставка.
-
Использование B-дерева в базах данных
- B-деревья могут быть преобразованы в деревья статистики для быстрого поиска и других операций.
- Время поиска в отсортированном файле зависит от количества операций сравнения.
- В больших базах данных время поиска увеличивается из-за задержки вращения диска.
-
Индекс B-дерева
- Индекс B-дерева создает многоуровневую древовидную структуру для разбиения базы данных на блоки.
- Вспомогательный индекс ускоряет поиск, указывая на нужный блок в основной базе данных.
- Вспомогательные индексы могут быть созданы для уменьшения количества операций чтения с диска.
-
Вставки и удаления
- Вставки и удаления выполняются быстро, если в блоке есть свободное место.
- Вставки могут быть медленными в отсортированном последовательном файле, поэтому используются частично заполненные блоки.
-
Преимущества B-дерева
- B-дерево сохраняет ключи в отсортированном порядке и использует иерархический индекс.
- B-дерево минимизирует потери и поддерживает баланс индекса.
- B-дерево может обрабатывать произвольное количество вставок и удалений.
-
Оптимальная и наихудшая высота
- Высота B-дерева зависит от количества записей и максимального количества дочерних элементов.
- Наилучшая высота корпуса равна: h = ⌈m/2⌉.
- Наихудшая высота равна: h = m/2 + 1.
-
Алгоритмы
- Поиск аналогичен поиску в бинарном дереве поиска.
- Вставка начинается с конечного узла и выполняется рекурсивно.
-
Создание и разделение узлов
- Если узел не имеет родительского элемента, создайте новый корень.
- Если разбиение продолжается до корня, создайте новый корень с одним разделителем и двумя дочерними элементами.
- Максимальное количество элементов на узел равно U−1.
- При разделении узла один элемент перемещается к родительскому, но один добавляется.
-
Удаление элементов
- Существует две стратегии удаления: найти и удалить элемент или выполнить один проход вниз по дереву.
- При удалении элемента из конечного узла просто удалите его.
- При удалении из внутреннего узла найдите новый разделитель и замените удаляемый элемент.
- Восстановление баланса после удаления начинается с листа и продолжается к корню.
-
Последовательный доступ и массовое строительство
- Последовательный доступ становится менее эффективным по мере роста базы данных.
- Массовая загрузка использует неравномерное разделение переполненных узлов для создания более эффективного дерева.
-
Использование в файловых системах
- B-деревья используются в файловых системах для быстрого произвольного доступа.
- MS-DOS использовала FAT для преобразования адресов файловых блоков в адреса дисковых блоков.
- TOPS-20 и другие системы использовали дерево уровней от 0 до 2.
- Современные файловые системы, такие как HFS+, APFS, NTFS, jfs2 и ext4, используют B-деревья.
-
Сравнение B-дерева и связанного списка
- B-дерево растет медленнее с увеличением объема данных
- Обе структуры имеют одинаковую производительность, но B-дерево лучше масштабируется
-
Т-образное дерево
- Аналогично B-дереву, но более компактно
- Используется в системах баз данных с основной памятью
-
Параллельный доступ
- Леман и Яо предложили связывать блоки дерева с указателем “next”
- Блокировки записи требуются только при изменении древовидного блока
- Пустые страницы не могут быть удалены из btree
-
Метод мета-доступа
- Обеспечивает одновременный доступ к дереву B+ и модификации без блокировок
- Использует дополнительные индексы в памяти для указания на блоки
- Не требует реорганизации для удаления
-
Параллельные алгоритмы
- B-деревья похожи на красно-черные деревья
- Параллельные алгоритмы для красно-черных деревьев применимы к B-деревьям
-
Кленовое дерево
- Разработано для ядра Linux для уменьшения конфликта блокировок
-
Другие структуры данных
- B+ дерево
- R-дерево
- Красно-черное дерево
- 2-3 дерева
- 2-3-4 дерева
-
Рекомендации и источники
- Глава 18: B-деревья
- Раздел 6.2.4: Многоходовые деревья
- Раздел 6.2.3: Сбалансированные деревья
- Оригинальные документы
- Внешние ссылки
- Лекция Дэвида Скотта Тейлора
- Визуализация B-дерева
- Анимированная визуализация B-дерева
- B-tree и UB-tree на Scholarpedia
- B-деревья: Сбалансированные древовидные структуры данных
- Словарь алгоритмов и структур данных NIST: B-дерево
- Учебное пособие по B-дереву
- Реализация InfinityDB BTree
- Кэшировать забвенные B(+)-деревья
- Запись в словаре алгоритмов и структур данных для B*-дерева
- Открытые структуры данных – Раздел 14.2 – B-Деревья
- Подсчитанные B-деревья
- B-Tree .Net – современная виртуализированная реализация оперативной памяти и дисков