Yes, that is the nature of an index.
You will see, however that a query like “select artist from songs” will never profit from an index on artist. 😉
Anyway, what just popped into my mind: instead of rewriting all the queries that would be hard on the slug maybe the same effect can be acheived by cleaning up the DB.
This would make sense to be run as a cron-job, presumably after a rescan cronjob.