xrpl::SHAMapNodeData Struct Reference

A SHAMap is both a radix tree with a fan-out of 16 and a Merkle tree. More...

#include <SHAMap.h>

Collaboration diagram for xrpl::SHAMapNodeData:

Public Attributes
SHAMapNodeID	nodeID
bool	isLeaf
Blob	data

Detailed Description

A SHAMap is both a radix tree with a fan-out of 16 and a Merkle tree.

A radix tree is a tree with two properties:

1. The key for a node is represented by the node's position in the tree (the "prefix property").
2. A node with only one child is merged with that child (the "merge property")

These properties result in a significantly smaller memory footprint for a radix tree.

A fan-out of 16 means that each node in the tree has at most 16 children. See https://en.wikipedia.org/wiki/Radix_tree

A Merkle tree is a tree where each non-leaf node is labelled with the hash of the combined labels of its children nodes.

A key property of a Merkle tree is that testing for node inclusion is O(log(N)) where N is the number of nodes in the tree.

See https://en.wikipedia.org/wiki/Merkle_tree Holds a SHAMap node's identity, leaf status, and serialized data. Used by getNodeFat to return node data for peer synchronization.

Definition at line 102 of file SHAMap.h.

Member Data Documentation

nodeID

SHAMapNodeID xrpl::SHAMapNodeData::nodeID

Definition at line 104 of file SHAMap.h.

isLeaf

bool xrpl::SHAMapNodeData::isLeaf

Definition at line 108 of file SHAMap.h.

data

Blob xrpl::SHAMapNodeData::data

Definition at line 109 of file SHAMap.h.