[notmuch] nested tag trees (was: Mail in git)

[martin f krafft]

also sprach Ben Gamari <bgamari at gmail.com> [2010.02.18.1744 +1300]:
> I believe you would. The problem isn't the messages (well, that's
> a problem too), it's the fact that the tree (e.g. tab) objects
> which reference the messages are immutable (I believe). This
> presents us with the difficult circumstance of being unable to
> modify a tag after it has been created. Therefore, as far as I can
> tell, we need to rewrite the tag's tree object whenever we add or
> remove a message. This was the reason I suggested nesting tag
> trees, although this only partially solves the issue.

You are absolutely right, and I think nesting tag trees is an
interesting idea to pursue. It *would* make it impossible to ever
check out the metatree into the filesystem, or rather result in
subdirectories that the user shouldn't need to worry about.

Instead of nested subtrees, think of 16 subtrees forming a level-1
hash table, or 256 for level-2, which really *ought* to be enough.

Anyway, rewriting a tree object is pretty much exactly the same as
removing a line (e.g. a message ID) from a file (e.g. a tag), as
that file would have to be fully rewritten.

> > This can probably be further optimised, but still: it's not
> > quite as nice as enumerating all parents of a message in O(1)
> > time (which would still result in O(m×n)).
> > 
> Yeah, I'm not sure how well this would scale on truly massive mail
> stores.

The more I think about this, the more I want to implement this
between evenless and Git, i.e. as a porcelain layer, since then
I could also use it for vcs-home[0]. In fact, maybe one day we can
store ~ and mail all in one Git repo, with different porcelains for
different use-cases, and notmuch indexing it all anyway. ;)

0. http://vcs-home.madduck.net

Let's continue the technical discussion on the Git list, okay?

http://marc.info/?l=git&m=126646636824600&w=2
id:20100218041240.GA4127 at lapse.rw.madduck.net

-- 
martin | http://madduck.net/ | http://two.sentenc.es/
 
"i hate vulgar realism in literature. the man who could call a spade
 a spade should be compelled to use one. it is the only thing he is
 fit for."
                                                        -- oscar wilde
 
spamtraps: madduck.bogus at madduck.net
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature (see http://martin-krafft.net/gpg/)
URL: <http://notmuchmail.org/pipermail/notmuch/attachments/20100218/5e2c1006/attachment.pgp>