B-дерево быстрее, чем AVL или RedBlack-Tree?[закрыто]
https://stackoverflow.com/questions/647537
-
22-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я знаю, что производительность никогда не бывает черно-белой, часто одна реализация быстрее в случае X и медленнее в случае Y и т. д.но в целом - B-деревья быстрее AVL или RedBlack-Trees?Их значительно сложнее реализовать, чем деревья AVL (и, возможно, даже RedBlack-деревья?), но являются ли они Быстрее (окупается ли их сложность) ?
Редактировать: Я также хотел бы добавить, что если они быстрее, чем эквивалентное дерево AVL/RedBlack (с точки зрения узлов/контента) - почему они быстрее?
Решение
Сообщение Шона (принятое на данный момент) содержит несколько неверных утверждений.Извини, Шон, я не хочу показаться грубым;Надеюсь, мне удастся убедить вас, что мое утверждение основано на фактах.
Они совершенно разные в своих сценариях использования, поэтому провести сравнение невозможно.
Оба они используются для поддержки набора полностью упорядоченных элементов с быстрым поиском, вставкой и удалением.У них одинаковый интерфейс и одинаковые намерения.
Деревья RB обычно представляют собой структуры в памяти, используемые для обеспечения быстрого доступа (в идеале O(logN)) к данным.[...]
всегда О (логарифм n)
B-деревья обычно представляют собой дисковые структуры и поэтому по своей сути медленнее, чем данные в памяти.
Ерунда.Когда вы храните деревья поиска на диске, вы обычно используете B-деревья.Это правда.Когда вы храните данные на диске, доступ к ним происходит медленнее, чем к данным в памяти.Но красно-черное дерево, хранящееся на диске, также медленнее, чем красно-черное дерево, хранящееся в памяти.
Вы здесь сравниваете яблоки и апельсины.Что действительно интересно, так это сравнение B-деревьев в памяти и красно-черных деревьев в памяти.
[Как в сторону:B-деревья, в отличие от красно-черных деревьев, теоретически эффективны в модели ввода-вывода.Я экспериментально протестировал (и подтвердил) модель ввода-вывода для сортировки;Я ожидаю, что это сработает и для B-деревьев.]
B-деревья редко являются двоичными деревьями, количество дочерних узлов, которые может иметь узел, обычно большое.
Чтобы внести ясность, диапазон размеров узлов B-дерева является параметром дерева (в C++ вы можете использовать целочисленное значение в качестве параметра шаблона).
Управление структурой B-дерева может быть довольно сложным при изменении данных.
Я помню, что их гораздо проще понять (и реализовать), чем красно-черные деревья.
B-дерево пытается минимизировать количество обращений к диску, чтобы получение данных было достаточно детерминированным.
Это правда.
Нередко можно увидеть что-то вроде доступа к 4 B-дереву, необходимого для поиска небольшого количества данных в самой базе данных.
Есть данные?
В большинстве случаев я бы сказал, что деревья RB в памяти работают быстрее.
Есть данные?
Поскольку поиск является двоичным, найти что-то очень легко.B-дерево может иметь несколько дочерних элементов на узел, поэтому на каждом узле вам придется сканировать узел в поисках соответствующего дочернего элемента.Это операция O(N).
Размер каждого узла является фиксированным параметром, поэтому даже если вы выполняете линейное сканирование, он равен O(1).Если мы преувеличиваем размер каждого узла, обратите внимание, что вы обычно сохраняете сортировку массива так, чтобы он был равен 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-дерево можно легко выразить как B-дерево. Возьмите в качестве примера следующее дерево:
теперь просто преобразуйте его в B-дерево (чтобы сделать это более очевидным, узлы по-прежнему окрашены в R / B, чего у вас обычно нет в B-дереве):
Цитировать из этой статьи:
Тогда красно-черное дерево структурно эквивалентно B-дереву порядок 4, с минимальным коэффициентом заполнения 33% значений на кластер с максимальная вместимость 3 значения.
Я не нашел данных о том, что один из них значительно лучше другого. Я думаю, что один из них уже вымер, если бы это было так. Они различаются в зависимости от того, сколько данных они должны хранить в памяти и насколько сложно добавить / удалить узлы из дерева.
Обновление:
Мои личные тесты показывают, что B-Trees лучше при поиске данных, так как они имеют лучшую локальность данных и, следовательно, кэш-память ЦП может выполнять сравнение несколько быстрее. Чем выше порядок B-дерева (порядком является количество детей, которое может иметь нота), тем быстрее будет выполняться поиск. С другой стороны, они имеют худшую производительность для добавления и удаления новых записей, чем выше их порядок. Это вызвано тем, что добавление значения в узле имеет линейную сложность. Поскольку каждый узел является отсортированным массивом, вы должны перемещать множество элементов в пределах этого массива при добавлении элемента в середину: все элементы слева от нового элемента должны быть перемещены на одну позицию влево или все элементы справа от новый элемент должен быть перемещен на одну позицию вправо. Если значение перемещается на один узел вверх во время вставки (что часто происходит в B-дереве), оно оставляет отверстие, которое также должно быть заполнено либо путем перемещения всех элементов с левой позиции на одну позицию вправо, либо путем перемещения всех элементов в справа на одну позицию влево. Эти операции (в C обычно выполняемые memmove) на самом деле O (n). Таким образом, чем выше порядок B-дерева, тем быстрее поиск, но медленнее модификация. С другой стороны, если вы выбираете слишком низкий порядок (например, 3), B-дерево демонстрирует небольшие преимущества или недостатки по сравнению с другими древовидными структурами на практике (в таком случае вы также можете использовать что-то еще). Таким образом, я бы всегда создавал B-деревья с высокими заказами (по крайней мере, 4, 8 и выше - это хорошо).
Файловые системы, которые часто основаны на B-деревьях, используют гораздо более высокие порядки (порядка 200 и даже намного больше) - это потому, что они обычно выбирают порядок достаточно высокий, чтобы записку (когда содержится максимальное количество разрешенных элементов) ) равен либо размеру сектора на жестком диске, либо кластеру файловой системы. Это дает оптимальную производительность (так как HD может записывать только полный сектор за раз, даже когда изменяется только один байт, полный сектор перезаписывается в любом случае) и оптимальное использование пространства (так как каждая запись данных на диске равна по крайней мере размеру один кластер или кратен размеру кластера, независимо от того, насколько большими на самом деле являются данные). Вызванный тем фактом, что аппаратное обеспечение рассматривает данные как сектора, а файловая система группирует сектора в кластеры, B-деревья могут обеспечить гораздо лучшую производительность и использование пространства для файловых систем, чем любая другая древовидная структура; вот почему они так популярны для файловых систем.
Когда ваше приложение постоянно обновляет дерево, добавляя или удаляя значениеИсходя из этого, RB-Tree или AVL-Tree могут в среднем показывать лучшую производительность по сравнению с B-Tree с высоким порядком. Несколько хуже для поисков, и им также может потребоваться больше памяти, но для этого изменения обычно бывают быстрыми. В действительности, RB-деревья даже быстрее для модификаций, чем AVL-деревья, поэтому AVL-деревья немного быстрее для поиска, поскольку они обычно менее глубоки.
Как обычно, многое зависит от того, что делает ваше приложение. Мои рекомендации:
<Ол>Альтернативой всем этим деревьям являются деревья AA . Как показывает этот документ PDF , деревья АА (которые находятся в Фактически, подгруппа RB-Trees) по производительности почти равна обычным RB-Trees, но их гораздо проще реализовать, чем RB-Trees, AVL-Trees или B-Trees. Вот полная реализация , посмотрите, насколько она крошечная (основная функция не является частью реализации, а половина строк реализации на самом деле являются комментариями).
Как показывает документ PDF, Treap также представляет собой интересную альтернативу реализации классического дерева. Treap также является бинарным деревом, но оно не пытается навязать балансировку. Чтобы избежать наихудших сценариев, которые вы можете получить в несбалансированных бинарных деревьях (в результате чего поиски становятся O (n) вместо O (log n)), Treap добавляет некоторую случайность в дерево. Случайность не может гарантировать, что дерево хорошо сбалансировано, но также крайне маловероятно, что дерево будет крайне несбалансированным.
Ничто не мешает реализации B-Tree, которая работает только в памяти. На самом деле, если сравнение ключей обходится дешево, B-Tree в памяти может быть быстрее , поскольку его упаковка нескольких ключей в один узел приведет к меньшему пропуску кэша во время поиска. См. эту ссылку для сравнения производительности. Цитата: & Quot; Результаты теста скорости интересны и показывают, что дерево B + значительно быстрее для деревьев, содержащих более 16 000 элементов. & Quot; (B + Tree - это просто разновидность B-Tree).
Вопрос старый, но думаю он все еще актуален.Йонас Кёлькер и Меки дали очень хорошие ответы, но я не думаю, что ответы охватывают всю историю.Я бы даже сказал, что вся дискуссия упускает суть :-).
То, что было сказано о B-деревьях, верно, когда записи относительно малы (целые числа, небольшие строки/слова, числа с плавающей запятой и т. д.).Когда записи большие (более 100 Б), различия становятся меньшими/незначительными.
Позвольте мне суммировать основные моменты, касающиеся B-деревьев:
Они быстрее, чем любое двоичное дерево поиска (BST), из-за локальности памяти (что приводит к меньшему количеству промахов в кеше и TLB).
B-деревья обычно более эффективны в пространстве, если записи относительно невелики или если записи имеют переменный размер.Управление свободным пространством проще (вы распределяете большие куски памяти), а дополнительные накладные расходы на метаданные за запись ниже.B-деревья будут тратить некоторое пространство, так как узлы не всегда заполнены, однако они все еще становятся более компактными, чем бинарные поисковые деревья.
Большая производительность O ( O(logN) ) одинакова для обоих.Более того, если вы выполняете двоичный поиск внутри каждого узла B-дерева, вы даже получите такое же количество сравнений, как и в BST (это хорошее математическое упражнение, чтобы проверить это).Если размер узла B-Tree разумный (размер линии кэша 1-4X), линейный поиск внутри каждого узла все еще быстрее из-за аппаратного предварительного получения.Вы также можете использовать инструкции SIMD для сравнения основных типов данных (например,целые числа).
B-деревья лучше подходят для сжатия:на каждый узел приходится сжимать больше данных.В определенных случаях это может оказаться огромным преимуществом.Просто представьте себе автоматически увеличивающийся ключ в таблице реляционной базы данных, который используется для построения индекса.Ведущие узлы B-дерева содержат последовательные целые числа, которые очень хорошо сжимаются.
Очевидно, что B-деревья работают намного быстрее, если они хранятся во вторичном хранилище (где вам нужно выполнять блочный ввод-вывод).
На бумаге B-деревья имеют много преимуществ и почти не имеют недостатков.Так стоит ли просто использовать B-деревья для достижения наилучшей производительности?
Ответ обычно НЕТ — если дерево умещается в памяти.В тех случаях, когда производительность имеет решающее значение, вам нужна потокобезопасная древовидная структура данных (проще говоря, несколько потоков могут выполнять больше работы, чем один).Сделать B-дерево, поддерживающее одновременный доступ, более проблематично, чем сделать BST.Самый простой способ обеспечить одновременный доступ к дереву — это блокировать узлы при их перемещении/изменении.В B-дереве вы блокируете больше записей на узел, что приводит к большему количеству точек сериализации и большему количеству конкурирующих блокировок.
Все версии дерева (AVL, Red/Black, B-Tree и другие) имеют бесчисленное множество вариантов, которые отличаются тем, как они поддерживают параллелизм.Ванильные алгоритмы, которые преподают в университетских курсах или читают из каких-то вводных книг, на практике практически не используются.Таким образом, трудно сказать, какое дерево работает лучше, поскольку нет официального соглашения о точных алгоритмах, лежащих в основе каждого дерева.Я бы предложил думать об упомянутых деревьях скорее как о классах структур данных, которые подчиняются определенным древовидным инвариантам, а не как о точных структурах данных.
Возьмем, к примеру, B-дерево.Ванильное B-дерево почти никогда не используется на практике — его невозможно хорошо масштабировать!Наиболее распространенным вариантом B-дерева является B+-дерево (широко используемое в файловых системах и базах данных).Основные различия между B+-деревом и B-деревом:1) вы не храните записи во внутренних узлах дерева (поэтому вам не нужны блокировки записи высоко в дереве при изменении записи, хранящейся во внутреннем узле);2) у вас есть связи между узлами на одном уровне (поэтому вам не нужно блокировать родительский элемент узла при поиске по диапазону).
Надеюсь, это поможет.
Ребята из Google недавно выпустили свою реализацию контейнеров STL, которая основана на B-деревьях. Они утверждают, что их версия быстрее и потребляет меньше памяти по сравнению со стандартными контейнерами STL, реализованными через красно-черные деревья. Подробнее здесь
Для некоторых приложений B-деревья значительно быстрее, чем BST. Деревья вы можете найти здесь:
http://freshmeat.net/projects/bps
довольно быстро Они также используют меньше памяти, чем обычные реализации BST, так как им не требуется, чтобы инфраструктура BST содержала 2 или 3 указателя на узел, а также некоторые дополнительные поля для хранения информации о балансировке.
Они используются в различных обстоятельствах - B-деревья используются, когда узлы дерева должны храниться вместе в хранилище - обычно потому, что хранилище - это страница диска, и поэтому перебалансировка может быть очень дорогой. Деревья RB используются, когда у вас нет этого ограничения. Таким образом, B-деревья, вероятно, будут быстрее, если вы захотите реализовать (скажем) индекс реляционной базы данных, в то время как деревья RB, вероятно, будут быстрее для (скажем) поиска в памяти.
Все они имеют одинаковое асимптотическое поведение, поэтому производительность зависит больше от реализации, чем от того, какой тип дерева вы используете. Некоторая комбинация древовидных структур на самом деле могла бы быть самым быстрым подходом, когда каждый узел B-дерева точно вписывается в строку кэша, а некоторый вид двоичного дерева используется для поиска внутри каждого узла. Самостоятельное управление памятью для узлов может также позволить вам добиться еще большей локализации кэша, но по очень высокой цене.
Лично я просто использую то, что есть в стандартной библиотеке для языка, который я использую, так как это очень большая работа для очень небольшого прироста производительности (если есть).
С теоретической точки зрения ... RB-деревья на самом деле очень похожи на B-деревья, так как они имитируют поведение 2-3-4 деревьев. AA-деревья имеют похожую структуру, которая имитирует 2-3 дерева.
кроме того ... высота красного черного дерева равна O (log [2] N), тогда как высота B-дерева равна O (log [q] N), где потолок [N] < = q < = N. Таким образом, если мы рассмотрим сравнения в каждом ключевом массиве B-дерева (который фиксирован, как упомянуто выше), то временная сложность B-дерева & Lt; = временная сложность красно-черного дерева. (одинаковый регистр для одной записи, равной по размеру блока)
.svg){kind=link}