How does the music identifying application Shazam work?

I mean, how the application knows what song I’m recording now by a few seconds only. Do they save a song Database with all the records?

Very intersting thing. Great Application! love it!