В зависимости от версии MySQL, которую вы используете, вы можете рассмотреть возможность создания табличных разделов. Есть несколько способов, которыми вы можете использовать его, либо путем хеширования идентификаторов, либо с помощью воспрепятствования даты.
Есть также способы логически отделить «рабочие» данные от архивных данных. Рассмотрим большую таблицу, представляющую фид. Возможно, что данные, не превышающие 14 или 28 дней, составляют 95% ваших использованных данных, а остальные можно поместить в архивную таблицу.
Если возможно разделить на несколько серверов, представляющих куски данных, есть несколько замечательных презентаций о том, как создавать системы хранения данных с использованием MySQL. Brad Fitpatrick's overview of LiveJournal - отличное место для начала.
В зависимости от типа данных, которые вы храните, возможно, вам даже не нужен MySQL. Если большинство ваших поисковых запросов получают первичный ключ, вы можете изучить системы хранения ключей/значений, такие как Redis или Cassandra, чтобы узнать, соответствуют ли они вашим потребностям.
Какую версию mySql вы используете? Какой механизм хранения используется для стола? – ceteras