AVL tree vs. B-tree

Question

Как дерево AVL отличается от дерева B?

Answer 1

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

Answer 2

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

Answer 3

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

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

Answer 4

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

5 
/\ 
    3 7 
//\ 
1 6 9 

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

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

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

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

Answer 5

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

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-дерево может обрабатывать произвольное количество вставок и удалений.

Answer 6

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

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

Answer 7

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

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

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

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

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

Answer 8

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

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

Answer 9

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

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

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