Bitcoin doesn't care about balances. Miners also don't.
Your wallet may keep track of your balance but it doesn't need to know about anyone else's. No one else cares about your balance. It is irrelevant.
Bitcoin only keeps track of unspent transaction outputs (UTXOs) - If you like metaphors and understand their limits, you can think of UTXOs as "coins" whose "current ownership" is indirectly kept track of in an almost anonymous way. When you give someone a coin in payment, they don't care how many other coins you have in your pocket, they only care whether the coin you gave them is genuine (really yours).
Bitcoin is designed so that creating new pages in the replicated journal of transactions is expensive and slow (i.e. constructing blocks that can be added to the blockchain). However, transactions can be verified quickly.
In the database world you speed up retrieval by adding appropriate indexes. You can have separate tables for live vs dead data, you can hold important data in memory, etc etc. That is how software finds UTXO's fast.