On 12.02.2012 21:52, Branko Čibej wrote: > The idea is that we'd always maintain the complete index, i.e., in order > to determine if path@15 exists, one only needs to search the index for > (path, rev <= 15, !deleted) -- which is trivial in a properly ordered > index. (Yes, this assumes that we record deletions in the index as well > as insertions.) > > All of this can be done with an append-only index representation. What > you can't do with append-only is represent forward history links, but -- > we're not representing them very well right now, are we. :) > > The other issue with an append-only index is that you essentially have > to reconstruct the whole index before you can do a lookup. A much better > structure for representing such (compressed, ordered) indexes has been > known for a while now, it's called a B-tree. ...
N.B.: In revlog, the @rev is implicit, since the index is itself versioned. You do have to reconstruct a whole revision of the index, but not the whole index. Possibly some smart heuristics would allow the server to reconstruct only part of the fulltext of index@rev, however, as far as I'm aware, Mercurial's revlog implementation does not use such heuristics. -- Brane
