Had another thought about this today. One thing that might reduce rebuild times would be storing the state of each feed independently. This would have a few benefits:

• Index the important things first
  • Index your messages first
  • Index only the people that you follow
• Lazy-load everything else
  • Friends of friends get indexed when you need it
  • Or, more likely, very slowly in the background
• Rebuild indexes for one feed only
  • Did Alice delete a message? Rebuild her index
  • Is Bob's index corrupt again? Rebuild it now

There are probably indexes that won't be able to save each feed's state separately, but my guess is most of them could do this just fine. I think the only universal constraint that we can't ignore is the number of file descriptors we have available.