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

Question

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

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

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

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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