Я знаю, что производительность никогда не бывает черно-белой, часто одна реализация быстрее в случае X и медленнее в случае Y и т.д., но в целом - B-деревья быстрее, чем AVL или RedBlack-Trees? Они значительно сложнее реализовать тогда деревья AVL (и, может быть, даже RedBlack-деревья?), Но быстрее ли они (их сложность окупается)?
Изменить: Я также хотел бы добавить, что если они быстрее, то эквивалентное дерево AVL/RedBlack (с точки зрения узлов/содержимого) - почему они быстрее?
Сообщение Sean (в настоящее время принятое) содержит несколько неправильных требований. Прости, Шон, я не хочу быть грубой; Надеюсь, я могу убедить вас, что мое утверждение основано на самом деле.
В своих случаях использования они совершенно разные, поэтому сравнение невозможно.
Они оба используются для поддержки набора полностью упорядоченных элементов с быстрым поиском, вставкой и удалением. Они имеют один и тот же интерфейс и одно и то же намерение.
Деревья RB обычно представляют собой структуры в памяти, используемые для обеспечения быстрого доступа (в идеале O (logN)) к данным. [...]
всегда O (log n)
B-деревья, как правило, основаны на дисках, поэтому они по сути медленнее, чем данные в памяти.
Глупости. Когда вы храните деревья поиска на диске, вы обычно используете B-деревья. Это правда. Когда вы храните данные на диске, это медленнее, чем данные в памяти. Но красно-черное дерево, хранящееся на диске, также медленнее, чем красно-черное дерево, хранящееся в памяти.
Вы сравниваете яблоки и апельсины здесь. Что действительно интересно, так это сравнение B-деревьев в памяти и красно-черных деревьев в памяти.
[В стороне: B-деревья, в отличие от красно-черных деревьев, теоретически эффективны в модели ввода-вывода. Я экспериментально тестировал (и проверял) модель ввода-вывода для сортировки; Я ожидаю, что он будет работать и для B-деревьев.]
B-деревья редко являются бинарными деревьями, число детей a node может быть обычно большим числом.
Чтобы быть ясным, диапазон размеров узлов B-дерева является параметром дерева (в С++ вы можете использовать целочисленное значение в качестве параметра шаблона).
Управление структурой B-дерева может быть довольно сложным при изменении данных.
Я помню, что их было намного проще понять (и реализовать), чем красно-черные деревья.
B-tree пытается минимизировать количество обращений к диску, чтобы поиск данных был достаточно детерминированным.
Это правда.
Нередко можно увидеть что-то вроде 4 B-дерева, необходимого для поиска небольшого количества данных в самой базе данных.
Получены данные?
В большинстве случаев я бы сказал, что деревья RB в памяти быстрее.
Получены данные?
Поскольку поиск является двоичным, очень легко найти что-то. B-tree может иметь несколько дочерних элементов на node, поэтому на каждом node вам нужно отсканировать node, чтобы найти соответствующий ребенок. Это операция O (N).
Размер каждого node является фиксированным параметром, поэтому даже если вы выполняете линейное сканирование, это O (1). Если мы имеем большой размер по каждому из node, обратите внимание, что вы обычно держите массив отсортированным, чтобы он O (log n).
На дереве RB это будет O (logN), поскольку вы делаете одно сравнение и затем разветвляетесь.
Вы сравниваете яблоки и апельсины. O (log n) - это то, что высота дерева не более O (log n), как и для дерева B.
Кроме того, если вы не играете противные трюки выделения с красно-черными деревьями, кажется разумным предположить, что B-деревья имеют лучшее поведение кеширования (он обращается к массиву, а не к указателям, разбросанным по всему месту и имеет меньшее распределение накладные расходы на увеличение местоположения памяти еще больше), что может помочь в ускорении гонки.
Я могу указать на экспериментальное доказательство того, что B-деревья (с параметрами размера 32 и 64, в частности) очень конкурентоспособны с красно-черными деревьями для небольших размеров и превосходят его для даже умеренно больших значений n. См. http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html
B-деревья быстрее. Зачем? Я предполагаю, что это из-за локальности памяти, лучшего поведения кэширования и меньшего количества преследователей (которые, если не одни и те же, частично перекрываются).
На самом деле в Википедии есть отличная статья, в которой показано, что каждое RB-Tree может быть легко выражено как B-Tree. Возьмем следующее дерево в качестве образца:
теперь просто преобразуйте его в B-Tree (чтобы сделать это более очевидным, узлы по-прежнему окрашены R/B, что вы обычно не имеете в B-Tree):
(не может добавить изображение здесь по какой-то странной причине)
То же самое верно для любого другого RB-Tree. Это взято из этой статьи:
http://en.wikipedia.org/wiki/Red-black_tree
Чтобы процитировать эту статью:
Затем красно-черное дерево структурно эквивалентное B-дереву порядок 4, с минимальным коэффициентом заполнения 33% значений для каждого кластера с максимальная емкость 3 значения.
Я не нашел данных, что один из них значительно лучше другого. Думаю, один из них уже вымер, если это так. Они различаются в отношении того, сколько данных они должны хранить в памяти и насколько сложно добавлять/удалять узлы из дерева.
Мои личные тесты показывают, что B-Trees лучше при поиске данных, так как они имеют лучшую локальность данных, и, следовательно, кэш ЦП может сравниться несколько быстрее. Чем выше порядок B-Tree (порядок - количество детей, которое может иметь заметка), тем быстрее будет поиск. С другой стороны, у них худшая производительность для добавления и удаления новых записей, чем выше их порядок. Это связано с тем, что добавление значения в node имеет линейную сложность. Поскольку каждый node является отсортированным массивом, вы должны перемещать множество элементов вокруг этого массива при добавлении элемента в середину: все элементы слева от нового элемента должны быть перемещены на одну позицию слева или все элементы на справа от нового элемента необходимо переместить одну позицию вправо. Если значение перемещает один node вверх во время вставки (что часто происходит в B-Tree), оно оставляет отверстие, которое также должно быть заполнено либо перемещением всех элементов из левой позиции вправо, либо путем перемещения всех элементы вправо на одну позицию слева. Эти операции (в C обычно выполняются memmove) на самом деле O (n). Таким образом, чем выше порядок B-Tree, тем быстрее выполняется поиск, а медленнее модификация. С другой стороны, если вы выберете слишком низкий порядок (например, 3), B-Tree на практике имеет небольшие преимущества или недостатки по сравнению с другими древовидными структурами (в этом случае вы можете использовать что-то еще). Таким образом, я всегда создавал B-деревья с высокими порядками (по крайней мере 4, 8 и все в порядке).
Файловые системы, которые часто основаны на B-деревьях, используют намного более высокие заказы (порядка 200 и даже намного больше) - это потому, что они обычно выбирают порядок, достаточно высокий, чтобы примечание (при содержании максимального количества разрешенных элементов ) равно либо размеру сектора на жестком диске, либо кластере файловой системы. Это дает оптимальную производительность (поскольку HD может записывать только полный сектор за раз, даже когда изменяется только один байт, полный сектор переписывается в любом случае) и оптимальное использование пространства (поскольку каждая запись данных на диске равна, по меньшей мере, размеру один кластер или кратно размерам кластера, независимо от того, насколько велики данные на самом деле). Вызванный тем фактом, что аппаратное обеспечение рассматривает данные как сектора и группы файловой системы для кластеров, B-Trees может обеспечить гораздо лучшую производительность и использование пространства для файловых систем, чем любая другая древовидная структура; почему они так популярны для файловых систем.
Когда ваше приложение постоянно обновляет дерево, добавляет или удаляет из него значения, RB-Tree или AVL-Tree может показывать лучшую производительность в среднем по сравнению с B-Tree с высоким порядком. Несколько хуже для поиска, и им также может потребоваться больше памяти, но для этого изменения обычно бывают быстрыми. На самом деле RB-деревья еще быстрее для модификаций, чем AVL-деревья, поэтому AVL-деревья немного быстрее для поиска, поскольку они обычно менее глубоки.
Итак, как обычно, многое зависит от того, что делает ваше приложение. Мои рекомендации:
Альтернативой всем этим деревьям являются AA-Trees. Поскольку этот документ PDF предлагает, AA-Trees (которые фактически являются подгруппой RB-деревьев) почти равны по производительности обычным RB-деревьям, но их намного проще реализовать, чем RB-деревья, AVL-деревья или B-деревья. Вот полноценная реализация посмотрите как крошечный (основная функция не является частью реализации, а половина линий реализации на самом деле являются комментариями).
Как показывает документ в формате PDF, Treap также является интересной альтернативой реализации классического дерева. Treap также является двоичным деревом, но не пытается обеспечить балансировку. Чтобы избежать сценариев худшего случая, которые вы можете получить в несбалансированных бинарных деревьях (что приводит к тому, что lookups становится O (n) вместо O (log n)), Treap добавляет некоторую случайность к дереву. Случайность не может гарантировать, что дерево хорошо сбалансировано, но это также делает маловероятным, что дерево чрезвычайно неуравновешено.
Ничто не мешает реализации B-Tree, которая работает только в памяти. Фактически, если сравнение ключей дешево, B-Tree в памяти может быть быстрее, потому что его упаковка нескольких ключей в одном node приведет к уменьшению пропусков кеша во время поиска. См. эту ссылку для сравнения производительности. Цитата: "Результаты теста скорости интересны и показывают, что дерево B + будет значительно быстрее для деревьев, содержащих более 16 000 предметов". (B + Дерево - всего лишь вариация на B-Tree).
Вопрос старый, но я думаю, что он по-прежнему имеет значение. Jonas Kölker и Mecki дали очень хорошие ответы, но я не думаю, что ответы охватывают всю историю. Я бы даже утверждать, что в целом обсуждении не хватает смысла:-).
То, что было сказано о B-Trees, верно, когда записи относительно малы (целые числа, маленькие строки/слова, поплавки и т.д.). Когда записи велики (более 100B), различия становятся меньше/несущественны.
Позвольте мне подытожить основные моменты о B-деревьях:
Они быстрее, чем любое двоичное дерево поиска (BST) из-за локальности памяти (что приводит к уменьшению количества пропусков кеша и TLB).
B-деревья обычно более эффективны в пространстве, если записи относительно маленький или если записи имеют переменный размер. Управление свободным пространством проще (выделяете большие куски памяти) и дополнительные метаданные накладные расходы на каждую запись ниже. B-деревья будут тратить некоторое пространство на узлы не всегда полны, однако они все же становятся более компактными что деревья двоичного поиска.
Производительность большого O (O (logN)) одинакова для обоих. Более того, если вы выполняете двоичный поиск внутри каждого B-Tree node, вы даже получите такое же количество сравнений, как и в BST (это хорошая математическая проверка, чтобы проверить это). Если размер B-Tree node разумный (размер строки кеша 1-4x), линейный поиск внутри каждого node еще быстрее из-за предварительная выборка оборудования. Вы также можете использовать инструкции SIMD для сравнивая основные типы данных (например, целые числа).
B-деревья лучше подходят для сжатия: для сжатия требуется больше данных на node. В некоторых случаях это может быть огромной выгодой. Подумайте об автоинкрементном ключе в таблице реляционной базы данных, которая используется для построения индекса. Ведущие узлы B-дерева содержат последовательные целые числа, которые очень сильно сжимаются.
B-Деревья явно намного быстрее, когда они хранятся на вторичном хранилище (где вам нужно делать блок ввода-вывода).
На бумаге у B-Trees есть много преимуществ и почти никаких недостатков. Итак, нужно ли просто использовать B-Trees для лучшей производительности?
Ответ обычно НЕТ - если дерево вписывается в память. В тех случаях, когда производительность имеет решающее значение, вам нужна потокобезопасная древовидная структура данных (просто говоря, несколько потоков могут работать больше, чем одна). Более проблематично сделать одновременный доступ к B-Tree, чем для создания BST. Самый простой способ сделать одновременный доступ к дереву поддерживает блокировку узлов при их перемещении/изменении. В B-Tree вы блокируете больше записей на node, что приводит к большему количеству точек сериализации и более жестких блокировок.
Все версии дерева (AVL, Red/Black, B-Tree, другие) имеют бесчисленные варианты, отличающиеся тем, как они поддерживают concurrency. Ванильные алгоритмы, которые преподаются в университетском курсе или читаются из некоторых вводных книг, практически никогда не используются на практике. Таким образом, трудно сказать, какое дерево лучше всего работает, поскольку нет никакого официального соглашения о точных алгоритмах за каждым деревом. Я бы предложил подумать о деревьях, которые упоминаются больше как структуры структуры данных, которые подчиняются определенным древовидным инвариантам, а не точным структурам данных.
Возьмем, например, B-Tree. Ванильное B-Tree практически никогда не используется на практике - вы не можете сделать его хорошо масштабируемым! Наиболее распространенным вариантом B-Tree является B + -Tree (широко используется в файловых системах, базах данных). Основные отличия между B + -Tree и B-Tree: 1) вы не храните записи во внутренних узлах дерева (при этом вам не нужны блокировки записи, высокие в дереве при изменении записи, хранящейся во внутреннем node); 2) у вас есть связи между узлами на одном уровне (при этом вам не нужно блокировать родителя node при поиске диапазона).
Надеюсь, это поможет.
Ребята из Google недавно выпустили свою реализацию контейнеров STL, которая основана на B-деревьях. Они утверждают, что их версия быстрее и потребляет меньше памяти по сравнению со стандартными контейнерами STL, реализованными красно-черными деревьями. Подробнее здесь
Для некоторых приложений B-деревья значительно быстрее, чем BST. Деревья, которые вы можете найти здесь:
http://freshmeat.net/projects/bps
довольно быстрые. Они также используют меньше памяти, чем обычные реализации BST, так как они не требуют инфраструктуры BST из 2 или 3 указателей на node, а также некоторые дополнительные поля для сохранения балансирующей информации.
В разных обстоятельствах это происходит в зависимости от того, как использовать B-деревья, когда узлы дерева должны храниться вместе в хранилище - как правило, поскольку хранилище является дисковой страницей, и поэтому повторная балансировка может быть дорогостоящей. Деревья RB используются, когда у вас нет этого ограничения. Таким образом, B-деревья, вероятно, будут быстрее, если вы хотите реализовать (скажем) индекс реляционной базы данных, в то время как деревья RB, вероятно, будут быстрее для (скажем) поиска в памяти.
Все они имеют одинаковое асимптотическое поведение, поэтому производительность зависит скорее от реализации, чем от типа используемого дерева. Некоторая комбинация древовидных структур может быть самым быстрым подходом, где каждый node B-дерева точно вписывается в строку кэша, а для каждого node используется поиск какого-то двоичного дерева. Управление памятью для самих узлов также может позволить вам достичь еще большей локальности кэша, но по очень высокой цене.
Лично я просто использую все, что есть в стандартной библиотеке для используемого языка, поскольку он очень много работает для очень небольшого прироста производительности (если есть).
В теоретической заметке... RB-деревья на самом деле очень похожи на B-деревья, поскольку имитируют поведение 2-3-4 деревьев. AA-деревья подобны структуре, которая имитирует 2-3 дерева вместо.
кроме того... высота красного черного дерева равна O (log [2] N), тогда как высота B-дерева равна O (log [q] N), где потолок [N] <= q <= = N. Поэтому, если мы рассматриваем сравнения в каждом ключевом массиве B-дерева (который фиксируется, как упоминалось выше), то сложность времени B-tree <= сложность времени для Red-black tree. (равный случай для одиночной записи, равный размеру блока)
.svg){kind=link}