How to index the UTXO set efficiently? I haven't been able to find information on how to efficiently index UTXOs. Can you explain or point me to some resources?

Update: Btw, I understand completely that the notion of address balance is awkward at best, and that it can never really be known with 100% confidence, especially as P2SH transactions gain popularity.
I believe what you are looking for is and address based index for txout. Have a look here https://bitcointalk.org/index.php?topic=1395749.msg14194272#msg14194272

Your basic idea of keeping a map of address -> txout is ok. You might want to rethink about storing in memory. Current bitcoind chainstate is around 1.2G (compressed state).