Efficiently store and search the directory tree in memory

Question

I want to store all directories on a huge disk as efficiently as possible in memory, and also be able to extract a directory with its full outline. Each directory has fields for a name (not a full path) and a pointer to its parent and a list of subdirectories. How do you think how to do this?

As I see it in several ways:

a) Store the full paths in each directory in the dictionary and do a simple search. Pros: fast; Cons: each line of the full path takes up raw and excess memory

b) Store only the actual directory name in the dictionary with a list of all directories with this name, and then check if it corrects the pluses: Pros: pretty fast, Cons: either you need to save the list for each directory, or use the box to store the list or directory in dictionary.

c) Skip the dictionary, cross the tree from the root and find a match by dividing the path. Perhaps PLINQ to speed up the process. Pros: there is no lack of memory with a dictionary; cons: potentially slower than a search.

d) in some other way I did not think ...

Answer 1

If you could store the subdirectories as a dictionary, and not as a list (and for cases when you need all the subdirectories that are easily executed using the Values property), you can go through a path, each step of which will be executed O (1) and, therefore, the difficulty of finding a directory from the full path is O (n), where n is the number of steps in the path that is not related to the number of directories in the system.

Answer 2

Use atabase. Point. The problem is an efficient search if the tree is not trivially small. He needs an index.

Skip the dictionary, make an enumerator that traverses the whole tree and finds a match

Not “efficient,” but the worst possible solution time, which is not a complete garbage solution and makes things slower than without problems.

The problem is that an effective partial search requires an index that requires a lot of programming to support, compared to using something like SqlLite in the temp directory.