title: Efficient data structure for associating data with filesystem paths?
body: <p>I need to keep some data in memory about a possibly large number of files and directories (typically up to a few hundreds of thousands). The obvious approach is to use a <code>Dictionary&lt;string, Something&gt;</code> with the path as the key, but there are two problems with this:</p>
  
  <ul>
  <li>many of the files will have a large part of their path in common, so it's probably a waste of memory to store the full path of each file</li>
  <li>I need to be able to quickly access the data about all the descendants of a directory; with a dictionary, the only way to do this is to test each key and check if it starts with the specified path, which is quite inefficient</li>
  </ul>
  
  <p>This problem seems like a good candidate for using a prefix tree (or <a href="http://en.wikipedia.org/wiki/Trie" rel="nofollow">trie</a>), with segments of the path as "characters". I tried to implement it, and the performance is not too bad for lookup by prefix (about 4 times faster than a dictionary), but it has two issues:</p>
  
  <ul>
  <li>the memory consumption is not reduced, probably because of the overhead of the list of children for each node</li>
  <li>the construction time is much worse than with a dictionary (about 4 times slower to fill the collection)</li>
  </ul>
  
  <p>I'm sure it must be a very common problem, so perhaps there are well known solutions that I'm not aware of?</p>