B-дерево быстрее, чем AVL или RedBlack-Tree? [закрытый]
Я знаю, что производительность никогда не бывает черно-белой, часто одна реализация быстрее в случае X и медленнее в случае Y и т. д. но в целом-B-деревья быстрее, чем AVL или RedBlack-деревья? Они значительно сложнее реализовать, чем деревья AVL (и, возможно, даже RedBlack-деревья?), но разве они быстрее (окупается ли их сложность)?
Edit: Я также хотел бы добавить, что если они быстрее, то эквивалентное дерево AVL/RedBlack (in условия узлов / контента) -почему они быстрее?
9 ответов:
сообщение Шона (в настоящее время принятое) содержит несколько неверных утверждений. Извините, Шон, я не хочу быть грубым; я надеюсь, что смогу убедить вас, что мое заявление основано на самом деле.
Они совершенно разные в своих случаях использования, поэтому невозможно провести сравнение.
Они оба используются для поддержания набора полностью упорядоченных элементов с быстрым поиском, вставкой и удалением. Они имеют тот же интерфейс и то же самое намерение.
деревья RB обычно являются структурами в памяти, используемыми для обеспечения быстрого доступа (в идеале O(logN)) к данным. [...]
всегда O (log n)
B-деревья обычно являются дисковыми структурами и поэтому по своей сути медленнее, чем данные в памяти.
бред. При хранении деревьев поиска на диске обычно используются B-деревья. Это действительно так. Когда вы храните данные на диске, это медленнее доступ, чем данные в памяти. Но красно-черное дерево хранится на диске и медленнее, чем красно-черное дерево хранится в памяти.
вы сравниваете яблоки и апельсины здесь. Что действительно интересно, так это сравнение в памяти B-деревьев и в памяти красно-черных деревьев.
[в стороне: B-деревья, в отличие от красно-черных деревьев, теоретически эффективны в модели ввода-вывода. Я экспериментально проверил (и подтвердил) модель ввода / вывода для сортировки; я ожидал бы этого чтобы работать и на B-деревья.]
B-деревья редко являются двоичными деревьями, количество детей, которые может иметь узел, обычно велико.
чтобы быть ясным, диапазон размеров узлов B-дерева является параметром дерева (в C++ вы можете использовать целочисленное значение в качестве параметра шаблона).
управление структурой B-дерева может быть довольно сложным при изменении данных.
Я помню, что их было много проще понять (и реализовать), чем красно-черные деревья.
B-tree попытайтесь свести к минимуму количество обращений к диску, чтобы извлечение данных было разумно детерминированным.
Это правда.
Это не редкость, чтобы увидеть что-то вроде 4 B-дерева имеет доступ к необходимой для поиска информации в базе.
получил данные?
в большинстве случаев я бы сказал, что деревья RB в памяти быстрее.
получил данные?
потому что поиск двоичный это очень легко найти что-то. B-tree может иметь несколько дочерних узлов на каждом узле, поэтому на каждом узле вы должны сканировать узел, чтобы найти соответствующего ребенка. Это операция O(N).
размер каждого узла является фиксированным параметром, поэтому даже если вы выполняете линейное сканирование, Это O(1). Если мы большие-oh по размеру каждого узла, обратите внимание, что вы обычно держите массив отсортированным так, чтобы он был O(log северный.)
на 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-дерево можно легко выразить как B-дерево. Возьмите в качестве примера следующее дерево:
теперь просто преобразуйте его в B-дерево (чтобы сделать это более очевидным, узлы все еще окрашены R / B, чего у вас обычно нет в B-дереве):
(Не могу добавить изображение здесь по какой-то странной причине)
то же самое верно для любого другого RB-дерева. Это взято из этой статьи:
http://en.wikipedia.org/wiki/Red-black_tree
цитата из этой статьи:
тогда красно-черное дерево структурно эквивалентно B-дереву заказ 4, с минимальным коэффициентом заполнения 33% значений для каждого кластера с максимальная емкость 3 значения.
Я не нашел никаких данных, что один из них значительно лучше, чем другой. Я думаю, что один из них уже вымер если бы это было так. Они отличаются тем, сколько данных они должны хранить в памяти и насколько сложно добавлять/удалять узлы из дерева.
обновление:
мои личные тесты показывают, что B-деревья лучше при поиске данных, так как они имеют лучшую локальность данных и, следовательно, кэш процессора может делать сравнение несколько быстрее. Чем выше порядок B-дерева (порядок-это количество дочерних элементов, которые может иметь заметка), тем быстрее будет выполняться поиск. С другой стороны, они имеют худшую производительность для добавления и удаления новых записей, чем выше их порядок. Это вызвано тем, что добавление значения в узле имеет линейную сложность. Поскольку каждый узел является отсортированным массивом, вы должны перемещать множество элементов внутри этого массива при добавлении элемента в середину: все элементы слева от нового элемента должны быть перемещены на одну позицию влево или все элементы справа от нового элемента должны быть перемещены на одну позицию вправо. Если значение перемещается один узел вверх во время вставки (что часто происходит в B-дереве), он оставляет отверстие, которое также должно быть заполнено либо перемещением всех элементов из левой позиции вправо, либо перемещением всех элементов в правую позицию влево. Эти операции(в C обычно выполняются memmove) на самом деле O (n). Таким образом, чем выше порядок B-дерева, тем быстрее поиск, но медленнее модификация. С другой стороны, если вы выбрали слишком низкий заказ (например, 3), B-дерево показывает небольшие преимущества или недостатки по сравнению с другими древовидными структурами на практике (в таком случае вы можете также использовать что-то еще). Таким образом, я бы всегда создавал B-деревья с высокими порядками (по крайней мере, 4, 8 и выше).
файловые системы, которые часто основаны на B-деревьях, используют гораздо более высокие порядки (порядка 200 и даже намного больше) - это связано с тем, что они обычно выбирают достаточно высокий порядок, чтобы Примечание (при содержании максимального количества разрешенных элементов) равнялось либо размеру сектора на жестком диске или кластера файловой системы. Это дает оптимальную производительность (поскольку HD может записывать только полный сектор за раз, даже когда изменяется только один байт, полный сектор все равно перезаписывается) и оптимальное использование пространства (поскольку каждая запись данных на диске равна по крайней мере размеру одного кластера или кратна размерам кластера, независимо от того, насколько велики данные на самом деле). Вызвано тем, что аппаратное обеспечение видит данные как секторы, а файловая система группирует секторы в кластеры, B-деревья могут дать много лучшая производительность и использование пространства для файловых систем, чем любая другая древовидная структура; вот почему они так популярны для файловых систем.
когда ваше приложение постоянно обновляет дерево, добавляя или удаляя из него значения, RB-дерево или AVL-дерево могут показывать лучшую производительность в среднем по сравнению с B-деревом с высоким порядком. Несколько хуже для поиска, и им также может потребоваться больше памяти, но для этого модификации обычно быстры. На самом деле RB-деревья еще быстрее для модификации, чем AVL-деревья, поэтому AVL-деревья немного быстрее для поиска, поскольку они обычно менее глубоки.
Так что, как обычно, это зависит от того, что делает ваше приложение. Мои рекомендации:
- много поисков, небольшие изменения: B-дерево (с высоким порядком)
- много поисков, много модификаций: AVL-Tree
- маленькие поиски, много модификаций: RB-Tree
альтернативой всем этим деревьям являются AA-деревья. Как это PDF бумага предлагает, AA-деревья (которые на самом деле являются подгруппой RB-деревьев) почти равны по производительности обычным RB-деревьям, но их гораздо легче реализовать, чем RB-деревья, AVL-деревья или B-деревья. Вот это полной реализации посмотри какой он крошечный (основная функция не является частью реализации и половина строк реализации на самом деле комментарии).
Как показано в документе PDF, a Treap также является интересной альтернативой классической реализации дерева. Treap также является двоичным деревом, но тот, который не пытается обеспечить балансировку. Чтобы избежать наихудших сценариев, которые вы можете получить в несбалансированных двоичных деревьях(в результате чего поиск становится O(n) вместо O (log n)), Treap добавляет некоторую случайность к дереву. Случайность не может гарантировать, что дерево хорошо сбалансировано, но она также делает крайне маловероятным, что дерево чрезвычайно несбалансировано.
.svg){kind=link}
ничто не мешает реализации B-дерева, которая работает только в памяти. На самом деле, если ключевые сравнения дешевы, в памяти B-Tree может быть быстрее потому что его упаковка нескольких ключей в одном узле вызовет меньше кэш пропускает во время поиска. Смотрите этой ссылка для сравнения производительности. Цитата: "результаты теста скорости интересны и показывают, что дерево B+ значительно быстрее для деревьев, содержащих более 16 000 элементов.(B + дерево-это просто a разновидность B-дерева).
вопрос старый, но я думаю, что он по-прежнему актуален. Йонас Келькер и Меки дали очень хорошие ответы, но я не думаю, что ответы охватывают всю историю. Я бы даже сказал, что вся дискуссия упускает суть :-).
то, что было сказано о B-деревьях, верно, когда записи относительно малы (целые числа, маленькие строки/слова, поплавки и т. д.). Когда записи большие (более 100B) различия становятся меньше/незначительными.
позвольте мне подытожить основные моменты о B-деревьях:
они быстрее, чем любое двоичное дерево поиска (BST) из-за локальности памяти (что приводит к меньшему количеству пропусков кэша и TLB).
B-деревья обычно более эффективны в пространстве, если записи относительно маленькие или если записи имеют переменный размер. Управление свободным пространством является проще (вы выделяете большие куски памяти) и дополнительные метаданные накладные расходы на вход ниже. B-деревья будут тратить некоторое пространство в качестве узлов не всегда полны, однако, они все еще оказываются более компактными это бинарные деревья поиска.
большая производительность O(O (logN) ) одинакова для обоих. Кроме того, если вы выполняете двоичный поиск внутри каждого узла B-дерева, вы даже получите такое же количество сравнений, как и в BST (это хорошее математическое упражнение для проверки этого). Если размер узла B-дерева является разумным (1-4X размер строки кэша), линейный поиск внутри каждого узла все еще быстрее из-за аппаратная предварительная выборка. Вы также можете использовать SIMD инструкции для сравнение основных типов данных (например, целых чисел).
B-деревья лучше подходят для сжатия: есть больше данных на узел для сжатия. В некоторых случаях это может быть огромным преимуществом. Просто подумайте об автоинкрементном ключе в таблице реляционной базы данных, которая используется для построения индекса. Ведущие узлы B-дерева содержат последовательные целые числа, которые сжимаются очень, очень хорошо.
B-деревья явно намного, намного быстрее при хранении на вторичное хранилище (где вам нужно сделать блок ввода-вывода).
на бумаге B-деревья имеют много преимуществ и почти не имеют недостатков. Так что надо просто использовать B-деревья для лучшей производительности?
ответ обычно нет -- если дерево помещается в памяти. В тех случаях, когда производительность имеет решающее значение, вам нужна потокобезопасная древовидная структура данных (проще говоря, несколько потоков могут выполнять больше работы, чем один). Более проблематично сделать поддержку B-дерева параллельной обращается в БСТ. Самый простой способ сделать дерево поддерживающим параллельные обращения-это заблокировать узлы при их обходе / изменении. В B-дереве вы блокируете больше записей на узел, что приводит к большему количеству точек сериализации и более спорных блокировок.
все версии дерева (AVL, Red/Black, B-Tree, другие) имеют бесчисленные варианты, которые отличаются тем, как они поддерживают параллелизм. Ванильные алгоритмы, которые преподаются в университетском курсе или читаются из некоторых вводных книги почти никогда не используются на практике. Таким образом, трудно сказать, какое дерево работает лучше всего, поскольку нет официального соглашения о точных алгоритмах, стоящих за каждым деревом. Я бы предложил думать о деревьях, упомянутых больше как классы структуры данных, которые подчиняются определенным древовидным инвариантам, а не точным структурам данных.
Возьмем, например, B-дерево. Ванильное B-дерево почти никогда не используется на практике - вы не можете заставить его хорошо масштабироваться! Наиболее распространенный вариант B-дерева используется B+ - дерево (широко используется в файловых системах, базах данных). Основные различия между B+-деревом и B-деревом: 1) Вы не храните записи во внутренних узлах дерева (таким образом, вам не нужно записывать блокировки высоко в дереве при изменении записи, хранящейся во внутреннем узле); 2) у вас есть связи между узлами на том же уровне (таким образом, вам не нужно блокировать родительский узел при выполнении поиска диапазона).
Я надеюсь, что это помогает.
ребята из Google недавно выпустили свою реализацию контейнеров STL, которая основана на B-деревьях. Они утверждают, что их версия быстрее и потребляет меньше памяти по сравнению со стандартными контейнерами STL, реализованными через красно-черные деревья. Более подробная информация здесь
для некоторых приложений, B-деревья, значительно быстрее, чем в Бсц. Деревья вы можете найти здесь:
http://freshmeat.net/projects/bps
довольно быстро. Они также используют меньше памяти, чем обычные реализации BST, поскольку им не требуется инфраструктура BST из 2 или 3 указателей на узел, а также некоторые дополнительные поля для хранения информации о балансировке.
Они sed в разных обстоятельствах-B-деревья используются, когда узлы дерева должны храниться вместе в хранилище - обычно потому, что хранилище является дисковой страницей и поэтому повторная балансировка может быть очень дорогой. Деревья RB используются, когда у вас нет этого ограничения. Таким образом, B-деревья, вероятно, будут быстрее, если вы хотите реализовать (скажем) индекс реляционной базы данных, в то время как деревья RB, вероятно, будут fasterv для (скажем) поиска в памяти.
все они имеют одинаковое асимптотическое поведение, поэтому производительность больше зависит от реализации, чем от того, какой тип дерева вы используете. Некоторая комбинация древовидных структур может быть на самом деле самым быстрым подходом, где каждый узел B-дерева точно вписывается в строку кэша, а для поиска в каждом узле используется какое-то двоичное дерево. Управление памятью для узлов самостоятельно также может позволить вам достичь еще большей локальности кэша, но на очень высоком уровне цена.
лично я просто использую все, что находится в стандартной библиотеке для языка, который я использую, так как это много работы для очень небольшого увеличения производительности (если таковые имеются).
на теоретической ноте... RB-деревья на самом деле очень похожи на B-деревья, так как они имитируют поведение 2-3-4 деревьев. AA-деревья-это аналогичная структура, которая имитирует 2-3 дерева вместо этого.