Dependiendo de la versión de MySQL que esté utilizando, podría considerar crear particiones de tabla. Hay varias formas de usarlo, ya sea al hacer el parche hash id o al paricionar la fecha.
También hay formas de separar lógicamente los datos de "trabajo" de los datos de archivo. Considere una mesa grande que represente un alimento. Es posible que los datos con menos de 14 o 28 días de antigüedad sean el 95% de los datos utilizados y el resto se puede colocar rutinariamente en una tabla de archivos.
Si es posible dividir en varios servidores que representan fragmentos de datos, hay algunas excelentes presentaciones sobre cómo crear sistemas de almacenamiento de datos federados utilizando MySQL. Brad Fitpatrick's overview of LiveJournal es un gran lugar para comenzar.
Dependiendo del tipo de datos que esté almacenando, puede que ni siquiera necesite MySQL en absoluto. Si la mayoría de sus búsquedas se obtienen con la clave principal, es posible que desee investigar sistemas de almacenamiento de clave/valor como Redis o Cassandra para ver si satisfacen sus necesidades.
¿Qué versión de mySql estás usando? ¿Qué motor de almacenamiento se usa para la tabla? – ceteras