Busqueda con FULLTEXT SEARCH. ¿Se puede optimizar para 10 millones de registros

[xcars]

Saludos amigos, buen rato de no pasar por aqui, pero tengo una duda interesante.
Resulta que tengo una BD (no explicare porque ni apra que) con aprox. 10 millones de registros de personas, donde esta la informacion basica x persona, nombre, direccion, etc.
Ahora bien, necesito hacer un sistema de busqueda de personas, el cual ya esta hecho, con indices FULLTEXT en los campos Nombre y Direccion (porque estos 2, pues porque puede ser que busquen "Carlos Perez" cuantos carlos perez habran en la BD, entonces es probable que conozcan parte de la direccion y unicamente usen "Carlos Perez Colonia Maquilishuat" por ejemplo, en fin, en esos 2 campos esta el indice de texto completo.

Ahora bien, al haber casi 10 Millones de registros, la busqueda no me es demasiado veloz como quisiera, y se tarda aun mas si pagino los datos, es decir, si quiero ir mostrando de 10 en 10, ya que debe calcular primero el numero de registros que tiene uqe devolver, y luego obtener estos datos, etc etc.

Que sugerencias me podrian dar para que la busqueda sea optimizada o mas veloz, por algun lado gracias a san google encontre que una forma de hacerlo es partiendo la BD en varias no mayores a 2 Millones de registros, pero nose que tan mito urbano pueda ser, si alguien ha tenido una experiencia similar, me ayudaria mucho escuchar opiniones.
Gracias