ja sure gibts das... Konsole: locate *.mp3 (je nach distri auch: mlocate, slocate) und hast alle mp3s vom PC.
Der erstellt jeden Tag eine komplette Liste, so findet man instant wichtige Dateien ohne einen Suchlauf zu starten.
Dies hat aber mit dem Amarok Problem nichts zu tun. Was da speziell Performance erhöht weiß ich auch nicht. Hast du denn die Medienbibliothek von deinen ganzen MP3s gemacht? Also bei mir gehts immer relativ schnell^^.
edit: mal kurz gegoogelt:
[Zur Link-Ansicht bitte registrieren.]