Improving MySQL efficiency
I would be considering the use of table partitioning. You don't mention mysql version or storage engine types. Here is the doc link:

http://dev.mysql.com/doc/refman/5.6/en/partitioning.html

for 5.6