[MERGE] Describe a hash trie based inventory

[Vincent Ladeuil]

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

    robert> On Tue, 2008-08-26 at 09:45 +0200, Vincent Ladeuil wrote:
    >> 
    >> Have you considered handling the inventory as a flat file-ids list
    >> instead of a path tree ?

    robert> Well, essentially this does treat it as a flat list
    robert> of file ids - the list is stored via the hash trie,
    robert> with the file id as the key.

Ok, thanks for clarifying, I was unsure.

    >> This could keep the nice properties of hash tries while
    >> addressing the 10.000 files in one directory corner case as well
    >> as the 'Goal satisfaction point 4' above.

    robert> The only issue with point 4 is the multiple lookups -
    robert> to solve that you need to have the full path stored
    robert> in some fashion, and that implies recursively
    robert> altering every entry when its parent is renamed even
    robert> if the entry itself isn't altered.

IMHO, if the full path is a property of the entry then renaming a
parent effectively *changes* every child entry. So we are still
in O(changes) whatever the tree *above* that point looks like.

Point 4 was: 
  
  Success, though each change will need its parents looked up as
  well so it will be proportional to the changes + the
  directories above the changed path.

That made me think that a change of a child implied a change on
every parent, but if we manage a flat list of file-ids, this is
irrelevant. No ?

           Vincent