AVL дерево против B-дерева

Question

Чем дерево AVL отличается от B-дерева?

Answer 1

Деревья AVL предназначены для использования в оперативной памяти, где произвольный доступ относительно дешев. B-деревья лучше подходят для дискового хранилища, поскольку они группируют большее количество ключей в каждом узле, чтобы минимизировать количество операций поиска, необходимых для операции чтения или записи. (Вот почему B-деревья часто используются в файловых системах и базах данных, таких как SQLite .)

Answer 2

И дерево AVL, и B-дерево схожи в том, что они являются структурами данных, которые благодаря своим требованиям минимизируют высоту их соответствующих деревьев. Эта «краткость» позволяет выполнять поиск за время O (log n), поскольку максимально возможное число операций чтения соответствует высоте дерева.

    5
   / \
  3   7
 /   / \
1   6   9

Это дерево AVL и ядро ​​двоичного поиска. Однако он самобалансирующийся, что означает, что при добавлении элементов в дерево оно будет реструктурироваться, чтобы поддерживать как можно более равномерную высоту. В принципе, это не допустит длинных ветвей.

B-дерево также делает это, но через другую схему перебалансировки. Это немного сложно написать, но если вы ищете в Google «Анимация B-дерева», есть несколько действительно хороших апплетов, которые достаточно хорошо объясняют B-дерево.

Они отличаются тем, что дерево AVL реализовано с учетом решений на основе памяти, а дерево B реализовано с учетом решений на основе дисков. Деревья AVL не предназначены для хранения огромных коллекций данных, так как они используют динамическое распределение памяти и указатели на следующий блок памяти. Очевидно, мы могли бы реплицировать функциональность дерева AVL с указанием расположения дисков и указателей дисков, но это было бы намного медленнее, потому что у нас все еще было бы значительное количество операций чтения для чтения дерева очень большого размера.

Когда сбор данных настолько велик, что он не помещается в памяти, решение представляет собой B-дерево (интересный фактоид: нет единого мнения о том, что на самом деле означает «B»). B-дерево содержит много дочерних узлов и множество указателей на дочерний узел. Таким образом, во время чтения с диска (которое может занять около 10 мс для чтения одного блока диска), возвращается максимальный объем данных соответствующего узла, а также указатели на дисковые блоки «конечного узла». Это позволяет амортизировать время извлечения данных до времени записи (n), что делает B-дерево особенно полезным для реализаций извлечения базы данных и большого набора данных.

Answer 3

AVL-дерево - это самобалансирующееся двоичное дерево поиска, сбалансированное для поддержания высоты O (log n).

B-дерево - это сбалансированное дерево, но это не бинарное дерево. Узлы имеют больше дочерних элементов, что увеличивает время поиска на узел, но уменьшает количество узлов, которые необходимо посетить для поиска. Это делает их хорошими для дисковых деревьев. Для получения дополнительной информации см. Статью Википедии .

.

Answer 4

AVL является самобалансирующимся, гарантируя, что все операции имеют O (log n) в среднем и худшем случаях.

Answer 5

Они действительно очень разные, хотя они служат в основном одной и той же цели: поддержке ассоциативной таблицы. Исторически сложилось так, что дерево AVL превзошло B-дерево для операций в памяти, но это особенно справедливо, когда доступ к памяти был дешевым (er) по сравнению с циклами ЦП.

Хотя обычно используются в хранилище баз данных для ключей переменной длины, B-деревья работают лучше всего для фиксированной длины и коротких записей (ключ + данные). Для таких применений это может значительно превзойти деревья AVL для использования в оперативной памяти, как с точки зрения занимаемой памяти (так как они хранят данные более компактно), так и скорости (у них было бы намного лучшее расположение кеша).

L2 - библиотека структур данных, реализующая очень быстрые ассоциативные таблицы и последовательности над B-деревьями. Он также имеет AVL-деревья, и сравнение производительности двух легко.

Answer 6

AVL-дерево - это самобалансирующееся бинарное дерево, которое включает среднее значение O (lgN) и наихудший случай для операций поиска и удаления. Он используется для поиска по дереву в памяти (наборы данных среднего размера).

B-дерево в основном используется как дерево поиска с резервной копией для очень больших наборов данных, поскольку оно требует меньше операций чтения на диск (поскольку каждый узел содержит N ключей, где N> 1). B-дерево называется (N, N + 1) B-деревом, где N - это количество ключей на узел, а N + 1 - количество дочерних элементов на узел. Чем больше ключей на узел, тем меньше времени вам потребуется для чтения с диска, и, естественно, оно будет более мелким деревом (меньше уровней).

Answer 7

B-дерево использует все идеи, описанные выше. В частности, B-дерево:

1)keeps keys in sorted order for sequential traversing
2)uses a hierarchical index to minimize the number of disk reads
3)uses partially full blocks to speed insertions and deletions
4)keeps the index balanced with an elegant recursive algorithm

Кроме того, B-дерево минимизирует отходы, поскольку внутренние узлы заполнены как минимум наполовину. B-дерево может обрабатывать произвольное количество вставок и удалений.

Answer 8

Другие авторы уже предоставили достаточно подробную техническую информацию об AVL и B-Tree, но я хотел бы добавить относительно новичок относительно этих двух :) -

• Дерево AVL - это двоичное дерево, в то время как B-дерево - это многоходовое дерево (N-арное дерево), т. Е. Любой узел в дереве AVL может иметь на максимум двух дочерних узлах и один фрагмент информации / данных , тогда как любой узел в B-дереве может иметь n узлов и n-1 фрагмент информации / данных. Для B-дерева n также известно как его порядок.

Answer 9

В непрофессионале -

Дерево AVL и дерево двоичного поиска одинаковы, но дерево AVL имеет ограничение, согласно которому разница между высотой левого поддерева и правого поддерева должна быть либо 0, 1, либо -1.

Если какое-либо двоичное дерево поиска удовлетворяет этим условиям, оно будет называться деревом AVL.

Двоичное дерево поиска + ВЫСОКОЕ СОСТОЯНИЕ - это дерево AVL.

См .: Введение в алгоритмы по Cormen https://books.google.co.in/books...