Excerpts from Stewart Smith's message of Wed Feb 17 18:56:53 -0500 2010:
> On Wed, 17 Feb 2010 14:21:01 +1300, martin f krafft <madduck@madduck.net> wrote:
> > What I am wondering is if (explicit) tags couldn't be represented as
> > tree-objects with this.
> 
> I think it could get expensive for tags with lots of messages.
> 
> As far as I understand it, the tree object is stored in full and space
> is only reclaimed during repack (due to delta compression).
> 
> So if you, say, had the entire history of a high volume list such as
> linux-kernel, adding messages could get rather expensive if you
> auto-tagged (or autotagged messages with patches or whatever).
> 

Well, it's tough to say, but I don't think it's as bad as you think. I
proposed that we could use a tree structure like the following,

                  ╭─msg1
      ╭tagA.list1╶┼─msg2
      │           ╰─msg3
      │
      │           ╭─msg4
      ├tagA.list2╶┼─msg5
      │           ╰─msg6
tagA ╶┤
      │           ╭─msg7
      ├tagA.list3╶┼─msg8
      │           ╰─msg9
      │
      │           ╭─msg10
      ╰tagA.list4╶┼─msg11
                  ╰─msg12

This way, adding a message to, say list3, would only require rewriting
list3 and tagA, which seems pretty reasonable to me. Moreover, we could
make the tree structure as deep as necessary, although we
would need to rewrite a node at every level of the tree, so its tough
saying how many levels is too many. It could simply be adaptive (e.g.
bisect any nodes with more than N children).

This certainly isn't as simple as the naive approach, but I think it's
the only reasonable approach performance-wise and I don't believe it
shouldn't be too tricky.

> > messages would then be deleted whenever using git-gc.
> > 
> > No idea how this would sync if we don't keep ancestry. Otoh, it
> > would probably not be very expensive to do just that.
> 
> If we keep ancestry though, we are reusing existing working code for
> backup (git-pull :)

This is one of the reasons I feel it's important we keep it. And as is
stated below, the storage overhead is minimal.
> 
> Keep in mind that with my tests, the Maildir in git is about a quarter
> to a fifth of the size of it in Maildir... so a bit of extra usage per
> message isn't as dramatic as it may sound.
>