не понял
надо все тупо слить в одну таблицу:
200*20k = 4кк - это вообще ни о чем, да если еще над my.cnf поколдовать...
только если вилдкард спереди будешь использовать при поиске, то лучше полнотекстовый индекс делать
вариант подобный предложенному ar4ibas (только вместо auto_increment - md5 хеши для скорости) у меня выдает
120к инкрементных операций в секунду на базе в 100кк
уж не знаю на сколько важна скорость ТСу, но 4кк записей - это мало для велосипедов