Documentation
¶
Overview ¶
Package merkletrie provides support for n-ary trees that are at the same time Merkle trees and Radix trees (tries), and provides an efficient tree comparison algorithm for them.
Git trees are Radix n-ary trees in virtue of the names of their tree entries. At the same time, git trees are Merkle trees thanks to their hashes.
When comparing git trees, the simple approach of alphabetically sorting their elements and comparing the resulting lists is too slow as it depends linearly on the number of files in the trees: When a directory has lots of files but none of them has been modified, this approach is very expensive. We can do better by prunning whole directories that have not change, just by looking at their hashes. This package provides the tools to do exactly that.
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. This means that the hash of a node doesn't have to take into account the hashes of their children, which is good for testing purposes.
Nodes in the Merkle trie are abstracted by the Noder interface. The intended use is that git trees implements this interface, either directly or using a simple wrapper.
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
internal
|
|
|
fsnoder
Package fsnoder allows to create merkletrie noders that resemble file systems, from human readable string descriptions.
|
Package fsnoder allows to create merkletrie noders that resemble file systems, from human readable string descriptions. |
|
Package noder provide an interface for defining nodes in a merkletrie, their hashes and their paths (a noders and its ancestors).
|
Package noder provide an interface for defining nodes in a merkletrie, their hashes and their paths (a noders and its ancestors). |