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

Question

В b-дереве вы можете хранить как ключи, так и данные во внутренних и конечных узлах , но в b + дереве вы должны сохранить данные только в листовых узлах .

Есть ли преимущество выполнения вышеизложенного в дереве b +?

Почему бы не использовать b-деревья вместо b + деревьев везде, поскольку они интуитивно кажутся намного быстрее?

Я имею в виду, зачем вам нужно копировать ключ (данные) в дереве b +?

Answer 1

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

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

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

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

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

---

Answer 2

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

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

Answer 3

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

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

Answer 4

1. В дереве B искать ключи и данные, хранящиеся во внутренних или конечных узлах. Но в B + -дереве хранятся только листовые узлы.
2. Полное сканирование в дереве B + очень просто, потому что все данные находятся в конечных узлах. Полное сканирование B-дерева требует полного обхода.
3. В B-дереве данные могут быть найдены в конечных или внутренних узлах. Удаление внутренних узлов очень сложно. В дереве B + данные находятся только в конечных узлах. Удаление листовых узлов легко.
4. Вставка в дерево B сложнее, чем в дерево B +.
5. В деревьях B + хранится избыточный ключ поиска, но в дереве B нет избыточного значения.
6. В дереве B + данные листовых узлов упорядочены как последовательный связанный список, но в дереве B листовой узел не может быть сохранен с использованием связанного списка. Реализации многих систем баз данных предпочитают структурную простоту дерева B +.

Answer 5

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

B + -tree

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

Answer 6

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

Answer 7

Адегок А, Амит

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

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

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

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

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

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

Answer 8

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

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

• Простое и согласованное блочное хранилище: у внутреннего узла есть N указателей, больше ничего, у конечного узла есть данные, больше ничего. это облегчает анализ, отладку и даже реконструкцию.

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

Answer 9

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

Answer 10

**

Главный недостаток B-Tree - сложность обхода клавиш. последовательно. B + Tree сохраняет свойство быстрого произвольного доступа 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