Package merkletrie provides support for n-ary trees that are at the sametime Merkle trees and Radix trees (tries).
Git trees are Radix n-ary trees in virtue of the names of theirtree entries. At the same time, git trees are Merkle trees thanks totheir hashes.
This package defines Merkle tries as nodes that should have:
- a hash: the Merkle part of the Merkle trie
- a key: the Radix part of the Merkle trie
The Merkle hash condition is not enforced by this package though. Thismeans that the hash of a node doesn't have to take into account the hashes oftheir children, which is good for testing purposes.
Nodes in the Merkle trie are abstracted by the Noder interface. Theintended use is that git trees implements this interface, eitherdirectly or using a simple wrapper.
This package provides an iterator for merkletries that can skip wholedirectory-like noders and an efficient merkletrie comparison algorithm.
When comparing git trees, the simple approach of alphabetically sortingtheir elements and comparing the resulting lists is too slow as itdepends linearly on the number of files in the trees: When a directoryhas lots of files but none of them has been modified, this approach isvery expensive. We can do better by prunning whole directories thathave not change, just by looking at their hashes. This package providesthe tools to do exactly that.