Сохранение и поиск дерева каталогов в памяти эффективно

Question

Я хочу хранить все каталоги на огромном диске как можно эффективнее в памяти, а также иметь возможность извлекать каталог, учитывая его полный путь. В каждом каталоге есть поля для имени (не полный путь) и указатель на его родительский элемент и список подкаталогов. Как вы думаете, какой путь?

Как я понимаю, что есть несколько способов:

а) хранить полные пути к каждой директории в словаре и сделать простой поиск. Плюсы: быстрая, Минусы: каждая строка полного пути занимает необработанный и избыточный объем памяти

b) Храните только фактическое имя каталога в словаре со списком всех каталогов с этим именем, затем проверьте соответствия, если оно правильно : Плюсы: довольно быстро, Минусы: нужно либо сохранить список для каждого каталога, либо использовать бокс для хранения списка или каталога в словаре.

c) Пропустите словарь, пересечь дерево из корня и найти совпадение путем разделения пути. Возможно, PLINQ, чтобы ускорить процесс. Плюсы: нет недостатка памяти со словарем, минусы: потенциально медленнее, чем поиск.

d) другим способом я не подумал ...

Answer 1

Если вы можете хранить подкаталоги в качестве словаря, а не как список (и для случаев, когда вы хотите, чтобы все подкаталоги были легко выполнены с использованием свойства Values), вы можете пройти через путь, каждый шаг которого равен O (1) и, следовательно, сложность нахождения каталога из полного пути O (n), где n - количество шагов в пути, не связанное с количеством каталогов в системе.

Answer 2

Используйте atabase. Точка. Проблема заключается в эффективном поиске, если дерево не тривиально мало. Ему нужен индекс.

Пропустить словарь, сделать перечислитель, который пересекает все дерево и находит совпадение

Не «эффективные», но worsst возможного время решения мудрого, что не является полным программированием отходов мудрой и делая вещи медленнее, чем без проблем.

Проблема заключается в том, что для эффективного частичного поиска требуется индекс, который требует много программирования для поддержки, по сравнению с использованием чего-то вроде SqlLite в каталоге temp.