Давно такое делал.....
Acronis, Partition я думаю такое сделать могут без проблем
Отрезать от второго раздела и присоединить к пермому, в интернете полно статей я думаю
такой поиск еще называется n-граммный
В mysql я пробывал, уж очень долго (учитывая особенности поиска стоило и ожидать)
В PostgreSQL есть пример - хабр
мне кажеться быстрее будет Sphinx