What underlying data structure is used to store wallet address on the blockchain? I'm curious how websites like bitref.com can determine the balance of a bitcoin wallet very quickly. 

I understand that the blockchain stores every single transaction across the thousands of blocks, so it's possible to reconstruct the balance of any wallet with this ledger. But wouldn't it take a long time to scan all these transactions? 

Instead, does the blockchain actually store every single address in some sort of map? Would this also contain the balance of each address? If so, I can't find a website where I could view all the addresses on the blockchain. Does anyone know where I can find that?
Bitcoin's blockchain does not track total amounts of bitcoin owned by individual addresses, only the changes in amounts (i.e. transactions between addresses).

To know the total amount of bitcoin a single address owns, wallet software must search the blockchain for transactions that reference that address. Then, using those transactions, the wallet software must sum the ins and outs of bitcoin coming from and going to that address.