[MERGE] Review feedback on hash trie inventories, and describe radix tree inventories, plus some details on hash trie implementation.

[Vincent Ladeuil]

>>>>> "robert" == Robert Collins <robertc at robertcollins.net> writes:

<snip/>

    robert> Canonical form isn't delta based at all;

May be I mispoked then, what I meant is that the full
representation is stored as fragments on disk somehow. Accessing
all the fragments may have a cost. This cost can be reduced by
putting all the fragments at the same place, eventually
*duplicating* the same information. As long as the representation
is canonical this should not be a problem.

    robert> I think the penny hasn't quite dropped all the way
    robert> into the slot :). Also note that we're not using a
    robert> hash partition, there are no delta representations at
    robert> all. Its history independent (which is one of the
    robert> goals) - anything that ever writes deltas isn't
    robert> history independent.

Hmm. Just to be clear, in the example you gave:

    robert> Ok, so - we start at the root node, and deserialise
    robert> it. This gives us a list of child node CHK's, as
    robert> pointers in a tree. e.g.

    robert> '0' : HASH1
    robert> '1' : HASH2
    robert> '2' : HASH3

    robert> We then read the other root node, which might give us:
    robert> '0' : HASH1
    robert> '1' : HASH4
    robert> '2' : HASH5

Is the tree associated with HASH0 stored once and shared between
the two trees or stored for each tree ?

    Vincent