README
¶
merkledb
Binary merkle tree database, backed by leveldb. Built to persist ZTYP SSZ data structures.
This library is under development, and not quite optimized.
The main idea is to hit the DB as few times as possible, while still structuring it as a binary tree without duplicates.
- Lookups for a specific node do not require iteration from the top-node, the generalized index can be used to select a range of all known nodes at a specific position.
- The DB returns virtual nodes; to lazy-load the children nodes
- Puts of nodes with children are transformed into batch-writes before writing to the db
Keys have:
- a 3-byte namespace prefix, since leveldb doesn't have tables
- a generalized index, big-endian, length prefixed. This groups adjacent/parent nodes close together, and enables smarter iteration.
- 32 bytes of the node itself
Values have:
- a 1-byte type prefix, to distinguish single-node (
0:Root) and pair-node (1:PairNode)Nodetypes. - an 8-byte little-endian slot value, to track when the node was inserted
- if a pair-node: 32 byte left node key, then 32 byte right node key
License
MIT, see LICENSE file.
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type MerkleDB ¶
type MerkleDB interface {
// Put a node and its subtree in the DB
Put(slot uint64, node Node, fn HashFn) error
// Get a node from the DB
Get(gindex Gindex, key Root) (SlottedNode, error)
// Has the node or not
Has(gindex Gindex, key Root) (bool, error)
// Delete the node at (gindex, key), does not remove any subtree
Delete(gindex Gindex, key Root) error
// Range retrieval of slotted values from the DB, between startSlot and endSlot, at the given gindex.
// There may be multiple nodes per slot.
Range(startSlot uint64, endSlot uint64, gindex Gindex) ([]SlottedNode, error)
}
type SlottedNode ¶
type SlottedNode struct {
Slot uint64
Node Node
}
type VirtualNode ¶
type VirtualNode interface {
Node
Detach() error
}
func NewVirtualNode ¶
func NewVirtualNode(db MerkleDB, gindex Gindex, key Root, left Root, right Root) VirtualNode
Source Files
Click to show internal directories.
Click to hide internal directories.