Hi Nguyen, On Mon, Mar 26, 2012 at 12:06 PM, Nguyen Thai Ngoc Duy <pclouds@xxxxxxxxx> wrote: > (I think this should be on git@vger as there are many experienced devs there) > > On Sun, Mar 25, 2012 at 11:13 AM, elton sky <eltonsky9404@xxxxxxxxx> wrote: >> About the new format: >> >> The index is a single file. Entries in the index still stored >> sequentially as old format. The difference is they are grouped into >> blocks. A block contains many entries and they are ordered by names. >> Blocks are also ordered by the name of the first entry. Each block >> contains a sha1 for entries in it. > > If I remove an entry in the first block, because blocks are of fixed > size, you would need to shift all entries up by one, thus update all > blocks? > We need some GC here. I am not moving all blocks. Rather I would consider merge or recycle the block. In a simple case if a block becomes empty, I ll change the offset of new block in the header point to this block, and make this block points to the original offset of new block. In this way, I keep the list of empty blocks I can reuse. If a block is not empty but not full, we better merge it with adjacent block for efficiency. But I don't know an light way to handle that when refreshing index. But we can always run a background thread to rebuild the index, at some stage, while system is quiet. > Also note the sequence format means duplication because we always > store full path. You are right, this keeps the size of the index as current system. Use a tree will save disk space for sure. Need think more about this. > -- > Duy Attach my previous email here: The goal of this project is : 1. verify checksum for only necessary part of index 2. keep the time complexity of most git-app below logn About the new format: The index is a single file. Entries in the index still stored sequentially as old format. The difference is they are grouped into blocks. A block contains many entries and they are ordered by names. Blocks are also ordered by the name of the first entry. Each block contains a sha1 for entries in it. For using a binary search to locate the block for an entry, the offsets of blocks are stored in the header of the index. We reserve 100 spaces for block offsets in the header. More offsets are stored in a meta block (see below) afterwards. An offset of the first meta block is stored. The checksum is computed on block. After we locate the block, the checksum is recomputed for the block. And only the this block will be read and write back later. As the block is read into ram, it is easy to do a binary search for entries in a block when they are in ram. When the index doesn't have many entries, it works very similar with current format. When more entries git-added, blocks will come into play. Format: Head: * 4-byte signature * 4-byte version num * 4-byte num of entries blocks * 4-byte offset for new block * list of offsets for blocks (e.g. 96, 14096, 8192, ..) : For binary search. Each offset is 8 bytes, we reserve 100 x 4 = 400 bytes for first 100 blocks. More offsets (if applicable) will be stored in a meta blocks. * 4-byte offset to the first meta block * 20-byte sha1 for above and meta blocks List of Blocks: * sha1 for all entries * list of entries Meta block: * offset to next meta block * list of offsets Extensions: TBD. Have not hacked cache tree yet. Need more knowledge of cache tree... Block Split & Delete: TBD. -Elton -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html