[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: skels in string table

From: Greg Hudson <ghudson_at_MIT.EDU>
Date: Wed, 11 Jun 2008 21:51:44 -0400

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

This is an archived mail posted to the Subversion Dev mailing list.

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.