В зависимости от версии MySQL, которую вы используете, вы можете рассмотреть возможность создания разделов таблицы. Есть несколько способов, которыми вы можете использовать его, либо путем хеширования по идентификатору, либо по дате.
Существуют также способы логически отделить «рабочие» данные от архивных данных. Рассмотрим большую таблицу, которая представляет канал. Может случиться так, что данные менее 14 или 28 дней составляют 95% используемых вами данных, а остальные обычно могут быть помещены в архивную таблицу.
Если возможно разделение на несколько серверов, представляющих куски данных, есть несколько отличных презентаций о том, как создавать федеративные системы хранения данных с использованием MySQL. Обзор LiveJournal Брэда Фитпатрика - отличное место для старта.
В зависимости от типа данных, которые вы храните, вам может даже не понадобиться MySQL вообще. Если большинство ваших поисков являются первичными ключами, вы можете изучить системы хранения ключей / значений, такие как Redis или Cassandra, чтобы выяснить, соответствуют ли они вашим потребностям.