Branko =?ISO-8859-2?Q?=C8ibej?= <brane@xbc.nu> writes:
> > Perhaps the table should be
> >
> > DIR-NODE-ID ENTRY-NAME REVISION -> ENTRY-NODE-ID
>
> Hmmm. Would you really need REVISION?
>
> > where REVISION is the filesystem revision in which this directory
> > entry was last changed. Use a table order that makes it easy to
> > search for "the last rev no later than N". To delete a directory
> > entry, you'd add a table entry of the form:
> >
> > DIR-NODE-ID ENTRY-NAME REVISION -> deleted
> >
> > which would mask table entries for the younger directory entries.
>
> But if you delete an entry, or add it, or replace it with a successor,
> the directory's revision itself gets bumped, and so all the way to the
> root. So you don't need REVISION after all. Within an active
> transaction, the mapping may change, but it's set in stone once you commit.
>
> You can't have two keys that differ only in the REVISION, because you
> can't have a changed (or mutable) subtree in the filesystem that's
> doesn't start at the root.
>
> You don't have to do "last rev no later than N" searches, because we do
> all lookups from the root (since yesterday, remember? Your own idea. :-)
> ), and we can find the correct root in the revisions table.
No, you're missing my point. The idea is to store all revisions of
all directories in a single table. Using the revision as part of the
key allows successive revisions of the same directory to share
structure.
For example, if we have a directory with the following revisions:
10.1: foo->12.4 bar->13.6 baz->14.7
10.2: foo->12.5 bar->13.6 baz->14.7
10.3: foo->12.5 bar->13.6 baz->14.8
then that would be represented by the following entries in the table:
10 foo 1 -> 12.4
10 bar 1 -> 13.6
10 baz 1 -> 14.7
10 foo 2 -> 12.5
10 baz 3 -> 14.8
To find an entry E in a node N, node revision R, you search for N E x,
where x is the largest x <= R. So searching for "bar" in node 10.3
probes for "10 bar x", largest x <= R, which is "10 bar 1", which is
13.6.
So node revisions two and three each share two table entries with the
previous node revision.
Is there something broken about this?
Received on Sat Oct 21 14:36:22 2006