Excerpts from martin f krafft's message of Wed Feb 17 20:58:47 -0500 2010:
> also sprach Ben Gamari <bgamari@gmail.com> [2010.02.18.1339 +1300]:
> > Yes, it would be linear in number of tags. I suppose if messages
> > weren't stored in the top-level tree nodes, then it would still be
> > linear, although with a slope equal to the reciprocal of the fan-out.
> > This has the potential to be very reasonable performance-wise.
> 
> Messages are never stored in tree nodes; all these do are store
> references to objects (blobs) holding messages. I bet you know this,
> but I just wanted to make it explicit.

Yep, I'm aware.
> 
> So retagging is really just writing a new tree with a modified list
> of references.
> 
Certainly, however if you have a large tag (>100,000 messages), this
list of reference could easily be tens of megabytes. For this reason, it
seems like the added overhead of nesting trees would be well worth it.

- Ben