go-ipld-prolly-trees

golang implementation of probabilistic merkle search trees for IPLD

constructor

The prolly trees cannot be constructed in place; it needs a helper constructor, also know as framework.

type Framework struct {
    done      bool
    cidPrefix *cid.Prefix
    nodeCoder *NodeCoder
    configCid cid.Cid
    builders  []*LevelBuilder
}

The structure is mainly composed of three layers：Framework -> LevelBuilder -> NodeStore. The framework is responsible for the upper layer, the middle node layer is done by the builder, and all data is stored in the nodestore abstraction..

prolly tree

Once the prolly tree has been constructed, only the root (entry) node of the prolly trees is needed for query operations.

type ProllyTree struct {
    ProllyRoot
    root       ProllyNode
    Ns         NodeStore
    treeConfig TreeConfig

    mutating  bool
    mutations *Mutations
}

If update operations (add/delete) are needed, they need to be done through the constructor.

// TreeConfig includes config for prolly tree, it includes some global setting, the splitter method you choose and specific configs about
// the splitter
type TreeConfig struct {
    StrategyType   byte
    MinNodeSize    int
    MaxNodeSize    int
    MaxPairsInNode int
    NodeCodec      []byte
    Strategy       strategy
}

const (
    SuffixThreshold  = 0
    WeibullThreshold = 1
    RollingHash      = 2
)

• ProllyNode：It's the same from the leaf to the root
• ProllyRoot：include
  • CID of the Root ProllyNode
  • CID of a configuration node

const (
    Unknown op = 0
    Modify  op = 1
    Add     op = 2
    Remove  op = 3
)

ADL