Ich habe mich in letzter Zeit mit einigen Shopsystemen (Oxid, Shopware, etc.) und habe mir diesbezüglich mal die Datenbankstruktur angesehen. Was mich total erstaunt hatte war das die Felder nach denen Sortiert oder gesucht werden gar keinen Index haben. Hat dieses einen tieferen Sinn?
Ich kenne keine Shopsysteme im konkreten, weiß aber, dass gute Systeme auf datenbankexterne Indexdienste wie z.B. Apache Lucene zurückgreifen. Suche ist viel mehr, als nur plumpe Vergleiche von Strings (fuzzy Search, Ontologien, …). Insofern wird für solche Daten kein weiterer Index in der Datenbank benötigt.
Indexe für die Keys, mehr willst nicht in der Datenbank. Zum Suchen wie @musiKk schon sagte, gibt es externe Engines, z.B. noch Solr oder Elastica.
Das ist eine ziemlich gewagte These 
Klar, für Volltextsuchen bringen normale Indizes nicht viel, aber z.B. bei denormalisierten Datenbanken kann die Performance deutlich profitieren. Date-Felder ebenso, oder boolean flags wie „deleted“ oder indizes auf SQL-Funktionen, oder, oder, oder…
Ich empfehle sehr gerne das Buch, welches auch auf dieser Seite durchzublättern ist: http://use-the-index-luke.com/de (nein, ich bekomme da nichts dafür). Da wird SQL- Performance für Entwickler erklärt, auch wie indizes technisch funktionieren, wie sie benutzt werden, etc.
Gut, war vielleicht zu knapp gesagt. Indizes auf date oder andere Felder die halt fast in jedem Query drin sind, sind schon Gold wert. Aber man muss halt abwägen.