Unless it's changed since I was there, Spotlight is more or less a sqlite3 database so it has about the same complexity as navigating a filesystem tree but prob

Unless it's changed since I was there, Spotlight is more or less a sqlite3 database so it has about the same complexity as navigating a filesystem tree but probably with better cache affinity. But also this concern about loading the header of millions of files is such an edge case that I don't think it matters. A human tapping on a piece of glass to play a few files would notice no difference in performance.