title: Creating an Index that is best for wildcard search through 40Million names
body: <p><strong>Task</strong>: search for best matching results for a name-search with wildcard  inside a db with ~40Million names.  e.g. query='John' results might be 'John', 'Johnny', 'Smith John', 'ajohn'<br>
  <strong>Candidates</strong>: MySQL Full-text, Sphinx and Lucene.<br>
  <strong>Observation</strong>: I assume they all work with an inverted index, which might not be the best solution for such short "documents" (names), and a trie might be a lot more suitable.   </p>
  
  <p>Assuming this observation is correct, do these tools have configurations to be more suitable for my case? Are there other tools that can integrate easily in PHP? </p>
  
  <p>Thanks.</p>