WIP: Propose the new merkled index storage engine

[imotai]

Motivation

Currently, db3 uses merk as merkled index storage engine.
the advantage of merk

• an ordered kv store, db3 use merk to query a single key or query data with a range of keys
• support proof of query, merk can prove the seeking operation and range query
• memory management according to the tree level, when the level of children nodes is greater than the limit, merk will remove the nodes from memory

the shortcomings

• AVL tree that merk uses is not good for persistence storage
• inactive community

the unsupported feature that db3 needs

• namespace, in db3 every account is a namespace and every namespace has its root hash

the namespaced Merkle tree is proposed by Celestia in the LazyLedger academic paper.so I want to propose a new merkled index storage engine called merkdb based on merk and merkdb has the following improvements

• replace AVL tree with b+tree to improve the performance on persistence storage, the berkletree has made some good experiments
• support namespace level root hash

and you can consider merkdb as rocksdb in crypto

The Instruction set of the storage engine

The poof of query

• proof of membership
• proof of range
• proof of efficiency

Reference

• https://github.com/cberner/redb/blob/master/docs/design.md
• https://github.com/erthink/libmdbx
• https://github.com/vorot93/libmdbx-rs
• Verkle tree a bandwidth-efficient alternative to Merkle Tree