title: Best data structures for searching millions of filenames?
body: <blockquote>
    <p><strong>Possible Duplicate:</strong><br>
    <a href="https://stackoverflow.com/questions/6838690/build-an-index-for-substring-search">Build an index for substring search?</a>  </p>
  </blockquote>
  
  
  
  <p>I'm developing a filename search tool. I'd like to search a harddrive (or multiple harddrives) for, perhaps, millions of filenames.</p>
  
  <p>Given the file: <strong><code>application 3 - jack smithinson</code></strong></p>
  
  <p>Searches:</p>
  
  <ol>
  <li>'<code>application</code>', '<code>3</code>', '<code>jack</code>', '<code>smithinson</code>' </li>
  <li>'<code>smith</code>'</li>
  <li>'<code>inson</code>'</li>
  </ol>
  
  <p>Should all return this file.</p>
  
  <p>What are the best data structures for this kind of operation and why?</p>
  
  <ol>
  <li>Binary tree.</li>
  <li>Trie.</li>
  <li>SQLite Database, of filenames</li>
  <li>More?</li>
  </ol>