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

Question

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

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

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

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

Answer 1

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

Answer 2

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

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

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

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

Answer 3

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

Answer 4

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

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