How can large websites keep countless user/pass combinations? I am asking about how exactly situations are saved within the database - or will they make use of a database? How can they scan with the countless records very quickly?

Hashed index. If you are using a number, unique userid you are able to assume couple of collisions (if setup properly) and hash indexes are the best choice.

Company, they are doing use databases. Typically multiple load balanced servers. Check this out question for applying for grants load balancing for SQL server as you will find multiple approaches:

SQL Server load balancing

A very common method to load balance is known as "federating" by Microsoft, however it virtually propagates the query request and allows it's maintained by multiple servers (afaik).