I don't think that there is a way to index by levenshtein distance generally because there is a many-to-many mapping between search terms and keys to match and

I don't think that there is a way to index by levenshtein distance generally because there is a many-to-many mapping between search terms and keys to match and there is potentially an infinite number of either. What I've seen databases that need to do fuzzy matching on strings do more often is index a list of substrings of keys and match on those. So hypothetically if I had a row identified with the string 'abc', I would have a separate table with the strings: 'a', 'b', 'c', 'ab', 'bc', 'abc' all mapped to the row in question and an index built on them. If you had a cap on the edit distance you knew was acceptable for searches, you could do something similar with levenshtein distance, where you could save every string with an edit distance less than say, 3, to a separate table along with the edit distance. This would be expensive in terms of space though, if your keys were very large. I suppose you could optimize it by just pre-computing the distance on a prefix (say the first three or four characters) and using that to narrow the search space.