Occasionally, a Bitcoin client will come across a fork of blocks that is longer than the chain it is currently on. Depending on how often orphaned blocks occur, this could be quite often. When this happens, any internal data structures relating to the "current" state of the blockchain (for example, a hashtable of unspent outputs) need to be updated to reflect the state of the new, longer fork.
How is this accomplished? Is history played "backwards" to the most recent common ancestor and then "forwards" to the new top block? Is it all just reconstructed from scratch?