Каковы различия между деревьями B и B +?

293

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

Есть ли какое-то преимущество в том, что вы делаете в дереве b +?

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

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

simplfuzz
источник
37
Я думаю, что они говорят "B-Tree" против B + -Tree. Они означают дефис, а не знак минус.
Stu

Ответы:

421

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

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

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

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

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

B и B + дерево

Роза Перроне
источник
2
Есть ли ограничения на количество записей в листовом узле?
TLE
38
@TLE Хороший вопрос! Да. Жесткий диск одновременно обращается к минимуму страницы памяти, поэтому мы хотим разместить все указатели на одной странице памяти. Мы хотим требовать только одно чтение с диска для каждого доступа к листу, поэтому мы не хотим назначать указателю лист больше чем размер страницы. Если мы заполним лист указателями размером страницы, а затем хотим добавить еще один указатель на этот лист, мы создадим двух дочерних элементов этого узла и передадим половину указателей листа каждому новому дочернему элементу. Конечно, могут быть некоторые перестановки, чтобы гарантировать, что высота дерева сведена к минимуму. Это помогает?
Роуз Перроне
последний указатель каждого конечного узла B-дерева должен указывать на следующий конечный узел, верно?
Камино
8
Извините, что натолкнулся на такую ​​старую ветку, но комментарий @ Babyburger о том, насколько правдивым был комментарий Камино, на самом деле не соответствует действительности; На самом деле B-дерево не имеет соединенных конечных узлов. A B +, конечно.
Джейсон
Спасибо за отличный ответ, каков вариант использования, когда потребуется полная проверка объектов в дереве B / B + в контексте базы данных? Так как он в основном используется для индексации, при поиске едва ли когда-нибудь нужно будет сканировать все дерево правильно, а вместо этого обходить путь индекса, это правильно?
Сиддхартха
113

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

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

Вик Э
источник
1
Я предпочитаю ответ Джеффа, потому что он подчеркивает разницу в эффективности при выполнении полного сканирования.
Роуз Перроне
Я действительно сбит с толку, потому что при обходе b-дерева с использованием обхода по порядку все значения будут отсортированы в отсортированном порядке за O (n). Если каждый узел дерева имеет оптимальный размер для физического размера страницы, кажется, что вещи не становятся более оптимальными. И наоборот, стоимость перехода к первому (наименьшему) значению в дереве b + равна O (log n), а затем пройти через каждый лист O (n), поэтому общая стоимость равна O (log n + n). Это больше работы и больше операций чтения с диска, что имеет смысл, потому что в дереве есть все эти дополнительные данные. Я не понимаю
Эрик
Какое будет еще слово для «разветвления» в предложении выше?
Хорхе Букаран
3
@JorgeBucaran fanout = количество ребер, выходящих из узла
bantmen
33

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

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

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

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

В + -tree В + дерево

соответствующее B-дерево ВТКЕЕ

Camino
источник
5
Я не думаю, что B-Tree имеет ссылки на дочерние узлы. Например, сформируйте Clearview bucketк Mianus Bucket. В любом случае, не имеет смысла делать это, потому что между ними у вас есть то, Downtown bucketчто нужно искать в случае, если вы хотите выполнить индексное сканирование в B-дереве (требует обратного отслеживания). Где ты это взял?
Эван Кэрролл,
1
@EvanCarroll Концепции системы баз данных 5-го, возможно, вам нужно подтвердить с автором :)
camino
11

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

Чарли Мартин
источник
2
Я согласен с Чарли. Поскольку один узел B-дерева представляет одну страницу или блок вторичной памяти, переход от одного узла к другому требует много времени на смену страницы.
11

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

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

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

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

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

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

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

Сакет
источник
10

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

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

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

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

Хавьер
источник
2
в основном для деревьев в памяти; но есть и другие популярные варианты, такие как красно-черные деревья, списки пропусков и тому подобное.
Хавьер
B-деревья также разработаны для эффективного блочного хранения, ограничивая асимптотическое число обращений к узлам. В противном случае, если использовать подобный памяти запоминающий носитель с произвольным доступом, можно использовать самобалансирующееся двоичное дерево, такое как красно-черное дерево, для достижения лучших результатов.
Дионизиз
не стоит ли в первом пункте сказать «меньше ищет», а не «больше ищет». Меньшая глубина -> меньше ищет
Джесси
1
@Jesse: высокая разветвленность => низкая глубина => меньше запросов, но смешивание данных и указателей означает меньшее количество указателей => низкая разветвленность => большая глубина => больше запросов
Хавьер
1
@AdegokeA: дерево B + имеет два вида узлов: внутренние узлы только с ключами и указателями, без данных; и конечные узлы, с данными и без указателей. это учитывает максимальное количество ключей на каждом внутреннем узле. если вы храните данные на внутреннем узле, тогда вы можете разместить меньше указателей, и ваше дерево станет выше.
Хавьер
5

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

VS7
источник
4

**

Основным недостатком 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 & гл = еп & са = Х & е = nD5AUbeeH4zwrQe12oCYAQ & вед = 0CDsQ6AEwAg # v = OnePage & д = минус% 20of% 20B-дерево% 20is% 20the% 20difficulty% 20of% 20Traversing% 20the% 20keys% 20sequentially & F = ложь

Капил Кумар
источник
1
Это должен был быть правильный ответ. Короче говоря: местность ссылки.
Теодор Зографос
2

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

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

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

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

Amit
источник
1
«Если вы используете дерево B здесь, то большую часть времени тратится на сканирование страниц с данными» - не обязательно. Узлы B-дерева могут хранить только «указатели» на данные на диске, но не сами данные.
TT_
2

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

Мэри
источник
1
Интересно, что мысли о повторении уникальны среди ответов, представленных здесь, и имеют больше смысла, чем обход по порядку дерева b + более эффективный, чем обход по порядку дерева b. Насколько я могу судить, это либо не совсем верно, либо не вся история, поскольку в порядке обхода b-дерева O (n) и нахождение наименьшего узла в b + дереве O (log n), а затем прохождение каждого листа является O (n) в дополнение к этому. Однако, если вы индексировали что-то с небольшим диапазоном значений, например, логическое поле, дерево b + имеет гораздо больший смысл, чем b-дерево, из-за его обработки дубликатов.
Эрик
1

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

Вивек Рахолия
источник
1
Просто для ясности, B-деревья не являются бинарными деревьями. На самом деле, деревья B и B + ближе друг к другу по конструкции и использованию, чем бинарные деревья. Статьи вики могут помочь в прояснении определений - B + Tree , B Tree и Binary Tree
uutsav
1

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

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

программист стека
источник
Это ответ на вопрос, почему мы не должны везде использовать B-деревья вместо B + деревьев :)
программист стека
3
Но вы описали только одну сторону, насколько нам известно, с вашим ответом b-деревья могли функционировать точно так же. ОП попросил объяснить различия, а вы говорили только об одном, а не о другом. Вы не можете иметь диаграмму Венна с одним кругом!
Малфист