No the the gateway don't need to scan everyone.
Your peer id describes your "location" in the network. The hash of the file is a location too.
When peers looking for a file they will ask the peer whose peer id is the closest to the file hash and the asked peer will do the same until the closest peer is found which is supposed to know which peer/peers to ask for the file.
When storing tracking data into the DHT the same lookup process happens and the closest peer is supposed to keep track of the hashes and the corresponding seeders closest to him.
Lot of variants of this possible, but the basic idea is the same.