Красное Черное дерево против дерева B

У меня есть проект, в котором я должен добиваться быстрого поиска, вставки и удаления операций с данными в диапазоне от мегабайт до терабайт. В последнее время я изучал структуры данных и анализировал их. Будучи конкретным, я хочу представить 3 случая и задавать вопросы по этому поводу:

  • Данные намного больше, чем может обрабатывать память (выборки диапазонов в 10-15 терабайт) за один раз. В этом случае я бы сохранил структуру данных на диске.

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

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

Сделанные мной выводы:

Для случая 1 я должен использовать B-Tree для более быстрого доступа, поскольку он сохраняет отставание, вызванное вращением диска

В случае 2 я должен использовать Red Black Tree для более быстрого доступа, поскольку данные хранятся в памяти и нет. элементов, которые необходимо отсканировать в худшем случае, будет меньше, чем один, который я должен выполнить, если я использую B Trees

В случае 3, я сомневаюсь, что этот файл на диске использует встроенный OS I/O для работы с файлами, так что должно ли B Tree быть лучшим вариантом или деревом Red Black?

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

Я использую язык С++ с красным черным деревом и деревом B, которые я разработал с нуля. Я использую библиотеку Boost для сопоставления файлов.

Обновление 1:: Прочитано через этот пост в stackoverflow. Получите некоторые реальные хорошие идеи, которые заставляют меня чувствовать, что тип сравнений, которые я сделал в случаях, может быть ошибочным. Ссылка была опубликована в наиболее проголосоваемом для ответа http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html

Ответы

Ответ 1

Красное/черное дерево более или менее эквивалентно дереву 2-3-4, который является всего лишь типом B-дерева. Производительность наихудшего случая идентична, если вы выполняете двоичный поиск значений B-tree node.

Очевидным недостатком B-дерева является потраченное впустую пространство, но в зависимости от используемого дистрибутора языка/памяти вы можете обнаружить, что дерево 2-3-4 использует меньше места, чем красно-черное дерево в среднем. Например, в 32-битной Java примерно 8-байтовые служебные данные для каждого объекта. (Это также сильно зависит от распределителя, IIRC phkmalloc округляет небольшие выделения до размера мощности.)

Чтобы ответить на ваши дела,

  • Задержка диска примерно равномерно распределена между временем поиска и ожиданием вращения диска.
  • B-tree должен иметь преимущество над красно-черным деревом, если вы делаете это правильно (в частности, B-дерево должно быть быстрее, если узлы вписываются в структуру кэша.)
  • Это не обязательно должно быть смежным в файле страницы; он просто должен быть смежным в виртуальном адресном пространстве процесса. Для нормальных ОС это также в значительной степени идентично случаю 1, если только ваши данные не достаточно малы, чтобы он в основном вписывался в память, а служебные данные memcpy значительны.

Для простоты я бы пошел с B-деревом и запускал некоторые тесты на разных размерах node.

Ответ 2

Чтобы понять разницу между ними, прочитайте ниже 2 пункта:

1) "Красно-черное дерево" - это "самобалансирующееся" "Дерево двоичного поиска" , с каждым node, отмеченным цветом (красным или черным) и имеет дополнительные операции, определенные для него, чтобы поддерживать "баланс"

2) Все "Красно-Черное дерево" - это "Дерево двоичного поиска" , но все "Дерево двоичного поиска" не являются "Красно-черным деревом"