DNS servers don't have to know "all" domains. They only need to know who is "authoritative", which it learns from a set of "root" servers. Each DNS server has a list of "root" servers, and this list changes infrequently. On one of my DNS servers, there are 18 root servers configured, and this configuration came when I installed the DNS server two years ago, and if the list of root servers has changed since then, enough of them are accessible that I haven't noticed it.
My DNS server, when asked to resolve a domain it doesn't know, makes a query to a root server to find out what other DNS server is authoritative for the domain. The response it gets may contain additional "NS" records and be marked non-authoritative, in which case my DNS server knows that it has to "follow the chain" and make a new query to a new server. Eventually, it finds a DNS server that provides authoritative information, and queries can be made that are not just NS records. A (address) and MX (mail exchange) are of course the two most common.
https://superuser.com/questions/477314/how-do-dns-servers-work