lookup in distributed ledgers
The balance is calculated from the UTXO set where unspent outputs belong to the address in question. Most block explorers will enable the transaction index, parse the historical and live data, and dump it into a database that runs on top of bitcoin to track additional statistics. As you can imagine this requires a lot more disk storage, but it makes things like searching faster.