Merkle.h File Reference

Generic sorted content-addressed B-tree over a templated key type. More...

#include "IStorageBackend.h"
#include <array>
#include <cstddef>
#include <cstdint>
#include <optional>
#include <string>
#include <vector>

Go to the source code of this file.

Classes
class	nt::Merkle< Key >
struct	nt::Merkle< Key >::Entry
	One (key, payload) pair returned by Page(). More...

Namespaces
namespace	nt
	Contains the Relational NT runtime managers and API facade.

Typedefs
using	nt::Hash32 = std::array<uint8_t, 32>
	32-byte hash, the universal payload type for all merkle levels.

Functions
Hash32	nt::hex_to_bin (const std::string &hex)
	Decode a 64-character lowercase-hex SHA256 string into raw bytes.
std::string	nt::bin_to_hex (const Hash32 &bin)
	Encode raw 32 bytes back into a 64-character lowercase-hex string.

Detailed Description

Generic sorted content-addressed B-tree over a templated key type.

Maps Key → Hash32 payload with Key totally ordered. Each tree node is stored as an immutable blob in IStorageBackend via Put/Get. All operations load only the nodes on the path from root to the target leaf — O(log_B(n)) nodes in memory at once, never the whole tree.

Instantiated three times in RNT:

Level	Key	Payload (Hash32)
Branch tree	std::string	multigroup snapshot hash
Multigroup	std::string	relation merkle root
Relation	nt::Hash32	tuple hash (key=payload)

Branching factor B = 64. At 64 children per node and a billion leaves the tree is at most 5 levels deep (~20 KB peak working set).

Immutability: nodes are never overwritten once written (content-addressed). Insert / Remove produce new nodes only along the modified path; old nodes remain valid for any snapshot that still holds their root hash.

Leaf node stores a sorted-by-key list of (Key, Hash32 payload) pairs, length ≤ B. For the relation level the key and payload happen to carry the same value (the tuple hash); callers pass it twice. Storing both keeps the tree shape uniform across the three levels.

Internal node entry layout (leaf_count | min_key | child_hash):

• leaf_count enables O(log_B(n) + limit) offset navigation for Page() without loading sibling subtrees.
• min_key is the smallest key in the subtree — the routing key.
• child_hash is the content-addressed hash of the child node blob.

Invariants (asserted in debug builds):

• No leaf or internal node is ever empty.
• Leaf entries are sorted ascending by key.
• Internal entries are sorted ascending by min_key.

Wire format: tagged 1-byte node kind ('L' or 'I'), then big-endian u32 count, then count repetitions of either a leaf entry or a child entry. Key encoding is per-specialisation: Hash32 is 32 raw bytes; std::string is u32_be length | bytes. Wire format is content-addressed — any change here invalidates every existing stored snapshot.