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