On Wed, 2008-06-11 at 20:27 -0500, Ben Collins-Sussman wrote:
> I haven't thought about it hard yet; we just need to 'split up' a
> directory's entries into multiple places somehow. Perhaps via hash
> buckets, as Blair has described. The ultimate feature we want is that
> it should be *fast* to locate a single entry, and *fast* to append a
> new entry to a directory, regardless of how many children it has.
I think the ideal structure here is some kind of multi-headed btree.
Ignore the current structure of BDB and FSFS for a moment, and imagine
that all information about all revisions of a directory are located in
one file. The file would end with a binary table mapping revisions to
block offsets, so you'd do some appropriate seeking math to look that up
and then you'd load a block of sorted directory entries. A block could
indirect to other blocks between entries, so it might be able to say:
abacus <rep key>
<indirection to other block>
marsupial <rep key>
<indirection to other block>
zebra <rep key>
Since you're going to load 4K blocks at a time, you'd expect it to
contain a whole bunch of entries and indirections. Only for very large
directories would you need to indirect more than once, I think.
A change to a single entry would only result in having to write out a
few new blocks, typically; you would truncate off the revision index,
write out the new blocks, and then write out a new revision index. If
the tree becomes too imbalanced, you have to write out some extra blocks
so that the new revision has a reasonably balanced tree, but according
to the btree theory I'm familiar with, that's still only O(lg(n)) extra
blocks to write out, or in practice, only a couple.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe_at_subversion.tigris.org
For additional commands, e-mail: dev-help_at_subversion.tigris.org
Received on 2008-06-12 03:52:10 CEST