Здравствуйте, BlackEric, Вы писали:

BE>Собственно вопрос: как организовать индекс по какому будет идти поиск, что бы он имел минимальный размер?

Можно посмотреть на поиск по триграммам (n-граммам), и соответствующие индексы