Re: GSoC - Designing a faster index format
From: Nguyen Thai Ngoc Duy <hidden>
Date: 2016-06-15 22:53:28
On Wed, Apr 4, 2012 at 3:26 PM, elton sky [off-list ref] 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