关于大数据量查询问题

关于数据库优化这方面的问题讨论也挺多的
不过我想知道对于大数据量的表查询大家都是用什么方法呢
我有一个一百万数据量的表
现在只是按名字的关键字检索也就是 where name like %?%
这样检索起来特别慢
后来用了分页方法一次拿10条出来到最后不够十条再算出尾页解决了慢的问题但如果输入的关键字是数据不存在的那等于也是遍历整个表
想到加索引在那么字段加速度似乎快了点但还是要花费一段时间也听说like %?%加索引无效（不知是否为真？）
还有就是现在还要加上一个排序 order by hot 可以加个索引
但速度还是慢 10秒以上

各位说说有什么方法解决呢？
问题补充：
现在主要问题出在当检索不到数据的时候特别慢不是其他