Jim Blandy wrote:
>> It should be possible, i guess. Right now, our delta format doesn't
>> allow such random-access applying of deltas simply because the windows
>> aren't indexed. You'd have to store a window lookup table with the
>> delta in order to convert seek offsets appropriate windows.
>
>
> Yep. Just on the techno-wanking side, I was thinking of a
> hierarchical index: after every tenth window, store a little table of
> pointers to the windows. After every tenth little table, store a
> little table of pointers to little tables of pointers to windows.
> After every tenth... you see what I mean. Then you can start at the
> end of the file and find any window in logarithmic time. That
> procedure always emits balanced trees. Use 100 instead of ten, and
> your tree has 1/100th the number of nodes as your file has windows,
> and is very shallow.
Aha, you're describing a B+tree of delta windows. Talk about a database
of compressed databases. :-)
>> Another question: when do you need random access to old versions?
>> And if you do, wouldn't it make more sense to store them in the
>> clear, anyway, without having to apply a series of deltas every
>> time? That's what any caching scheme will boil down to, anyway.
>
>
> Greg S. asked some mild questions, and I'm inferring from there.
> The thought arose from the intersection of these issues:
> - Subversion wants to use deltas to store multiple versions of files
> in a compact way.
> - Subversion wants to provide a uniform interface for accessing both
> old and new versions of nodes.
> - HTTP or DAV has some way to ask about substrings of files.
Oooh, that's right: HTTP/1.1 let's you pick a file to pieces.
> I have no compelling application in mind; I'm just trying to meet all
> the promises we're making.
Well, personally I think it would be a great feature to have, and I've a
hunch that it could be a huge performance gain in some situations. I've
no feeling about /when/ we'll need it. I suggest you add this to IDEAS,
and we can pull it out of there when the time's right..
--
Brane �ibej
home: <brane_at_xbc.nu> http://www.xbc.nu/brane/
work: <branko.cibej_at_hermes.si> http://www.hermes-softlab.com/
ACM: <brane_at_acm.org> http://www.acm.org/
Received on Sat Oct 21 14:36:14 2006