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

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

Ответ 1

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

Ответ 2

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

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

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

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

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

Ответ 3

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

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

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

Ответ 7

В условиях неспециалиста -

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

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

Дерево двоичного поиска + HEIGHT CONDITION - это дерево AVL.

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

Ответ 8

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

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