My database contains tens of millions of products, so I need an efficient search technique to speed up my response. Initially, I tried making a number of tables based on alphabets or some initial characters of the query. However, that fails many times, e.g. if the user searches for "ipod touch" instead of "apple ipod touch." Can I implement this using a trie or some other data structure? How does Google keep track of so much data?
What you need is a full text search. You could try using the FULLTEXT index in MySQL and perform a MATCH AGAINST query.
But I think you will have much better luck with Apache Solr. It is fast, scalable and provides much better (relevant) results.