У меня есть проект, в котором я должен добиваться быстрого поиска, вставки и удаления операций с данными в диапазоне от мегабайт до терабайт. В последнее время я изучал структуры данных и анализировал их. Будучи конкретным, я хочу представить 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
