Well sure, a songs database is important. But song databases like https://acoustid.org/ exist, which let you look up songs that share the same audio "fingerprint" (https://github.com/acoustid/chromaprint). You need the full track to make that fingerprint.

Shazam can take only a tiny snippet, and can guess quite accurately just from that snippet. By comparison to AcoustID, which is also a song database (with an entirely different purpose) we can say that the "main ingredient" is Shazam's system for identifying songs from short snippets.