README
¶
Trieste
Trieste is an Italian coastal and historical frontier city partially enclosed by Slovenia. Why not visit?
Trieste is also a sparse prefix tree library for Go based on ideas from crit-bit and qp tries.
Status
This is currently a prototype.
Building
You can get the dependencies necessary for building this library by installing dep and running:
dep ensure -v
Purpose
This work is motivated by the need for prefix-addressable and Merkle tree storage in Hyperledger Burrow, but if it ever becomes useful might have general applicability. It aims to provide a reasonably compressed and fast sorted, range-iterable, prefix tree with a full-byte branching factor of 256 (technically 257 including a distinguished terminal). It compresses paths in the tree (from root to leaf) by only introducing nodes on the 'critical byte' on which keys differ and it keeps down storage space by implementing a sparse map of child nodes for a branch using a bitset.
Future
Burrow has some uses for a basic in-memory version of this tree to provide sorted caching layers, but further extensions may be of interest:
- Providing a lazy Merkle tree hash where hashes are stable over prefixes
- Providing a persistent version where nodes are written immutably to a storage backend
- Writing to disc or a memory-mapped file to provide a prefix tree database
- Providing various kinds of proof to facilitate (among other things) blockchain light clients
Related work
See the excellent and more mature Tendermint IAVL library with similar aims.
See also the go-ethereum trie package based also on a condensed trie (sometimes called PATRICIA) with support for proofs and Merkle hashes, with a 16 + 1 branching factor, but no sparse array.
Why bother?
Surprisingly few standalone trie libraries exist for Go. IAVL is good but not so efficient for in-memory storage and because of the way balacning happens AVL is order-dependent and does not maintain stable hashes for prefixes.
A common data structure in-memory and on-disc may be possible with some advantages for serialisation. Also it might be nice to have the tree structure as the native database structure rather than implementing an prefix/AVL tree of a B+ tree (or whatever the database layer is).
Documentation
¶
Index ¶
Constants ¶
const BranchingFactor uint = 257
Branch on byte plus special terminal character
const TerminalChar = 0
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Branch ¶
type Branch struct {
// contains filtered or unexported fields
}
A Branch or internal node consists of an index which is the index of the key byte on which this branch 'decides'. A Branch implements a sparse array of children with one possible slot for each possible character branch. The Leaf node, Leaf[K,V], for a particular key can be found under the subtree rooted at the child in position C when charAt(K[Branch.index]) == C.
type HeightNode ¶
type Node ¶
We model Node as a sum type. Either Node should be nil, contain just a non-nil Branch, or contain just a non-nil Leaf
func (*Node) BreadthFirstSearch ¶
func (tn *Node) BreadthFirstSearch(callback func(*HeightNode) error) error
func (*Node) Descend ¶
Descend implements the basic traversal of the trie. It returns the deepest directed edge, parent --char--> child, accessible by following key on each critical index along the path of Branches. child may be nil indicating the slot for char on branch is unoccupied. Note: we use the Node container for branch as a convenience for mutation - it is guaranteed to be a Branch Node
Source Files