Karaoke index is file which stores names of songs for which there is a karaoke file available. If you play a song, EvilLyrics looks up if karaoke is available and if it is, it shows little "mouth" icon in its statusbar (and also on karaoke bar).
You have to update your karaoke indxed once in a while so you get availability info on karaoke files that has been added recently. Karaoke index isn't updated automatically, you have to update it from preferences. If your karaoke index is more than 2 weeks old, you get alerted via little red popup and you can then update it also directly from statusbar menu.