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

Question

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

Как я вижу, есть несколько способов:

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

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

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

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

Answer 1

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

Answer 2

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

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

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

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