Re: GSoC - Designing a faster index format

[Nguyen Thai Ngoc Duy <pclouds@gmail.com>]

On Wed, Apr 4, 2012 at 3:26 PM, elton sky <eltonsky9404@gmail.com> wrote:
> I am not sure how the trailer works.
> I assume there can be multiple trailers, each update will generate a
> new one. Every trailer will point to the root tree (i.e. all trailers
> point to the same block?). So if there are some changes to root, like
> rename, trailers all point to the latest root block?

Each trailer points to the whole new tree. Because trees are
immutable, changing in a tree meangs creating a new one and will also
make a new parent tree (to point to the updated tree because old
parent will always point to old tree). This eventually leads to root
tree change, recorded by the trailer.

> Is the index looks like :
> | HEADER | TREE BLOCKS | TRAILER |  TREE BLOCKS | TRAILER | TREE
> BLOCKS | TRAILER | ...
>
> Blocks and trailers are interleaved. The index starts from a few
> blocks (git add file1 file2 file3 ..) and expands as it goes. If file1
> is updated, the tree block containing file1 is updated and appended.
> (At this point, 2 versions of tree blocks containing file is in index
> ?) How do you organize these 2 block in a tree ?

I leave them where they are. They will be indirectly referenced by two
different roots. At that point we have to new full trees, sharing many
subtrees except the one that contains file1 and its ancestors. This
makes it possible to access an old index version by traversing from an
older trailer. Heavy "add -p" users may like this.

> Appended blocks are also a tree or just a list. If it's a list, it
> needs O(n) read time. If it's like a sub tree, I assume it's small,
> because I guess there won't be many changes each time. If it's too
> small then lgn -> n, and in total read time -> n.

It's trees all the way down. I'm not sure why read time is related
here. You read it by traversing from root tree to leaves, no matter
old or new root. Appended trees may push trees farther away and
increase seek time. Other than that, I don't see significant read
performance degradation (really crowded trees may degrade a little bit
because we need to read trees in addition to leaves, but I don't think
it's a big problem).
-- 
Duy