user4796: 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.

user26481: 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). 

4796: <p>I haven't been able to find information on how to efficiently index UTXOs. Can you explain or point me to some resources?</p>

<p>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.</p>
 26481: <p>I believe what you are looking for is and address based index for txout. Have a look here <a href="https://bitcointalk.org/index.php?topic=1395749.msg14194272#msg14194272" rel="nofollow">https://bitcointalk.org/index.php?topic=1395749.msg14194272#msg14194272</a></p>

<p>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). </p>
