Различия между деревьями B и деревьями B +

Ответ 1

Ниже показано изображение различий между деревьями B + и деревьями B.

Преимущества деревьев B +:

• Поскольку деревья B + не имеют данных, связанных с внутренними узлами, большее количество ключей может помещаться на страницу памяти. Поэтому для доступа к данным, расположенным на листе node, потребуется меньшее количество промахов в кеше.
• Листовые узлы деревьев B + связаны между собой, поэтому для полного сканирования всех объектов в дереве требуется только один линейный проход по всем листовым узлам. С другой стороны, дерево B потребует обхода каждого уровня в дереве. Этот обход всего дерева, вероятно, будет включать больше промахов в кеше, чем линейный обход листьев B +.

Преимущество деревьев B:

• Поскольку деревья B содержат данные с каждым ключом, часто доступные узлы могут располагаться ближе к корню, и поэтому их можно получить быстрее.

Ответ 2

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

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

Ответ 3

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

B-деревья, с другой стороны, могут быть быстрее, когда вы ищете (ищет конкретную часть данных по ключу), особенно когда дерево находится в ОЗУ или другом неблокированном хранилище. Поскольку вы можете поднимать обычно используемые узлы в дереве, для получения данных требуется меньшее количество сравнений.

Ответ 4

• В ключах поиска дерева B и данных, хранящихся во внутренних или листовых узлах. Но в B + -tree хранятся только узлы листа.
• Поиск любых данных в дереве B + очень просто, потому что все данные находятся в листовых узлах. В дереве B данные не могут быть найдены в листовых узлах.
• В дереве B данные могут быть найдены в листовых узлах или внутренних узлах. Удаление внутренних узлов очень сложно. В дереве B + данные встречаются только в листовых узлах. Удаление листовых узлов легко.
• Вставка в дерево B более сложна, чем дерево B +.
• B + деревья хранят избыточный ключ поиска, но дерево B не имеет избыточного значения.
• В дереве B + данные листовых узлов упорядочены как последовательный связанный список, но в дереве B лист node не может быть сохранен с помощью связанного списка. Многие реализации систем баз данных предпочитают структурную простоту дерева B +.

Ответ 5

Определите "намного быстрее". Асимптотически они примерно одинаковы. Различия заключаются в том, как они используют вторичное хранилище. Статьи Википедии о B-деревья и B + trees look довольно надежный.

Ответ 6

Пример из концепций системы баз данных 5th

В + -tree

соответствующее B-дерево

Ответ 7

Adegoke A, Amit

Я думаю, что один важный момент, который вам не хватает, - это разница между данными и указателями, как описано в этом разделе.

Указатель: указатель на другие узлы.

Данные: - В контексте индексов базы данных данные являются еще одним указателем на реальные данные (строки), которые находятся где-то в другом месте.

Следовательно, в случае дерева B каждый node имеет три информационных ключа, указатели на данные, связанные с ключами, и указатель на дочерние узлы.

В дереве B + дерева node сохраняйте ключи и указатели на дочерние node, а листья node сохраняют ключи и указатели на связанные данные. Это позволяет увеличить количество ключей для заданного размера node. Размер node определяется в основном размером блока.

Преимущество наличия большего количества ключей для node объясняется значительно выше, поэтому я сохраню свое усилие ввода.

Ответ 8

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

• высокий уровень разветвления/низкая глубина: это означает, что вам нужно получить меньше блоков, чтобы добраться до данных. с данными, смешавшимися с указателями, каждое чтение получает меньше указателей, поэтому вам нужно больше искать, чтобы добраться до данных.

• простое и последовательное хранение блоков: внутренний node имеет N указателей, ничего больше, у листа node есть данные, ничего больше. что позволяет легко анализировать, отлаживать и даже восстанавливать.

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

Ответ 9

В B + Tree, поскольку во внутренних узлах хранятся только указатели, их размер становится значительно меньше, чем внутренние узлы дерева B (которые хранят как ключ данных +). Следовательно, индексы дерева B + могут быть извлечены из внешней памяти на одном диске, прочитанном, обработанном, чтобы найти местоположение цели. Если это было дерево B, чтение диска требуется для каждого процесса принятия решений. Надеюсь, я ясно дал понять!:)

Ответ 10

Основное различие между деревом B и деревом B + состоит в том, что B-дерево исключает избыточное хранение значений ключа поиска. Поскольку ключи поиска не повторяются в B-дереве, мы не сможем хранить индекс, используя меньше, чем в соответствующем индексе дерева B+. Однако, поскольку ключ поиска, который появляется в нелистовых узлах, больше нигде не отображается в B-дереве, мы вынуждены включать дополнительное поле указателя для каждого ключа поиска в не-лист node. Это пространственные преимущества для B-дерева, поскольку повторение не происходит и может использоваться для больших индексов.

Ответ 11

**

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

** ref: Структуры данных с использованием C//Автор: Aaro M Tenenbaum

http://books.google.co.in/books?id=X0Cd1Pr2W0gC&pg=PA456&lpg=PA456&dq=drawback+of+B-Tree+is+the+difficulty+of+Traversing+the+keys+sequentially&source=bl&ots=pGcPQSEJMS&sig=F9MY7zEXYAMVKl_Sg4W-0LTRor8&hl=en&sa=X&ei=nD5AUbeeH4zwrQe12oCYAQ&ved=0CDsQ6AEwAg#v=onepage&q=drawback%20of%20B-Tree%20is%20the%20difficulty%20of%20Traversing%20the%20keys%20sequentially&f=false

Ответ 12

Дерево B + - это сбалансированное дерево, в котором каждый путь от корня дерева до листа имеет одинаковую длину, и каждый нелеистый node дерева имеет между [n/2] и [n] дети, где n фиксировано для определенного дерева. Он содержит индексные страницы и страницы данных. Двоичные деревья имеют только два родителя на родителя node, деревья B + могут иметь переменное число детей для каждого родителя node

Ответ 13

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

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

B + Деревья разделяют ключи от данных.

Но если ваш размер данных меньше, вы можете сохранить их с помощью ключа, который является тем, что делает дерево B.

Ответ 14

Одним из возможных вариантов использования B + tress является то, что он подходит для ситуаций где дерево растет настолько большим, что оно не должно Память. Таким образом, вы обычно ожидаете, что будете делать несколько операций ввода-вывода. Часто случается, что дерево B + используется, даже если оно действительно вписывается в памяти, а затем ваш менеджер кэша может постоянно его хранить. Но это особый случай, а не общий, а политика кэширования - это отдельно от обслуживания дерева B + как такового.

Кроме того, в дереве B + страницы листа связаны в связанный список (или двусвязный список), который оптимизирует обходы (для поиска диапазона, сортировки и т.д.). Таким образом, количество указателей функция используемого конкретного алгоритма.