Другое различие между B-деревом и двоичным деревом состоит в том, что у B-дерева должны быть все его дочерние узлы на одном уровне, тогда как у двоичного дерева нет такого ограничения. Бинарное дерево может иметь максимум 2 поддерева или узла, тогда как в B-дереве не может быть M ни поддеревьев, ни узлов, где M - порядок B-дерева.
Сравнительная таблица
| Основа для сравнения | В-дерево | Бинарное дерево |
|---|---|---|
| Существенное ограничение | У узла может быть не более M количество дочерних узлов (где M - порядок дерева). | Узел может иметь максимум 2 числа поддеревьев. |
| Используемый | Используется, когда данные хранятся на диске. | Используется, когда записи и данные хранятся в оперативной памяти. |
| Высота дерева | log M N (где m - порядок дерева M-way) | log 2 N |
| заявка | Индексирование структуры данных во многих СУБД. | Оптимизация кода, кодирование Хаффмана и др. |
Определение B-дерева
B-дерево - это сбалансированное M-way дерево, также известное как сбалансированное дерево сортировки. Это похоже на двоичное дерево поиска, где узлы организованы на основе обхода по порядку. Пространственная сложность B-дерева O (n). Сложность времени вставки и удаления составляет O (log n).
Существуют определенные условия, которые должны выполняться для B-дерева:
- Высота дерева должна быть минимально возможной.
- Над листьями дерева не должно быть пустых поддеревьев.
- Листья дерева должны прийти на одном уровне.
- Все узлы должны иметь наименьшее количество дочерних элементов, кроме оставленных узлов.
Свойства B-дерева порядка M
- Каждый узел может иметь максимальное число детей M и минимальное число детей M / 2 или любое число от 2 до максимального.
- Каждый узел имеет на один ключ меньше, чем дочерние, с максимальным количеством ключей M-1.
- Расположение ключей в некотором определенном порядке в узлах. Все ключи в поддереве, присутствующем слева от ключа, являются предшественниками ключа, а те, которые присутствуют справа от ключа, называются преемниками.
- Во время вставки полного узла дерево разделяется на две части, и ключ с медианным значением вставляется в родительский узел.
- Операция слияния происходит при удалении узлов.
Определение двоичного дерева
Двоичное дерево - это древовидная структура, которая может иметь не более двух указателей для своих дочерних узлов. Это означает, что наивысшая степень, которую может иметь узел, равна 2, а также может быть узел с нулевой или одной степенью.
Существуют определенные варианты двоичного дерева, такие как строго двоичное дерево, полное двоичное дерево, расширенное двоичное дерево и т. Д.
- Строго бинарное дерево - это дерево, в котором каждый нетерминальный узел должен иметь левое поддерево и правое поддерево.
- Дерево называется Полным двоичным деревом, когда оно удовлетворяет условию наличия 2 узлов i на каждом уровне, где i - уровень.
- Бинарный поток - это бинарное дерево, которое состоит из 0 или 2 узлов.
Техники обхода
Обход дерева - это одна из наиболее частых операций, выполняемых над структурой данных дерева, при которой каждый узел посещается ровно один раз систематическим образом.
- Inorder - в этом обходе дерева рекурсивное посещение левого поддерева, затем посещение корневого узла и посещение последнего правого поддерева.
- Preorer - при этом обходе дерева сначала посещается корневой узел, затем левое поддерево и, наконец, правое поддерево.
- Postorder - этот метод посещает левое поддерево, затем правое поддерево и, наконец, корневой узел.
Ключевые различия между B-деревом и бинарным деревом
- В B-дереве максимальное количество дочерних узлов, которое может иметь нетерминальный узел, равно M, где M - порядок B-дерева. С другой стороны, двоичное дерево может иметь не более двух поддеревьев или дочерних узлов.
- B-дерево используется, когда данные хранятся на диске, тогда как двоичное дерево используется, когда данные хранятся в быстрой памяти, такой как RAM.
- Другой областью применения B-дерева является структура данных индексации кода в СУБД, напротив, двоичное дерево используется для оптимизации кода, кодирования Хаффмана и т. Д.
- Максимальная высота B-дерева равна log M N (M - это порядок дерева). В отличие от этого, максимальная высота двоичного дерева равна log 2 N (N - количество узлов, а base - 2, потому что это для двоичного файла).
Заключение
B-дерево используется поверх двоичного и двоичного дерева поиска. Основная причина этого - иерархия памяти, в которой ЦП подключен к кешу с каналами с высокой пропускной способностью, а ЦП подключен к диску через канал с низкой пропускной способностью. Бинарное дерево используется, когда записи хранятся в оперативной памяти (маленький и быстрый), а B-дерево используется, когда записи хранятся на диске (большой и медленный). Таким образом, использование B-дерева вместо Binary tree значительно сокращает время доступа из-за высокого коэффициента ветвления и уменьшенной высоты дерева.
