Struct TreeStats 

pub struct TreeStats {

    pub num_nodes: usize,
    pub num_leaves: usize,
    pub num_internal_nodes: usize,
    pub tree_height: u8,
    pub total_key_value_pairs: usize,
    pub total_tree_size_bytes: usize,
    pub avg_node_size_bytes: f64,
    pub min_node_size_bytes: usize,
    pub max_node_size_bytes: usize,
    pub avg_entries_per_node: f64,
    pub nodes_per_level: BTreeMap<u8, usize>,
    pub avg_node_size_per_level: BTreeMap<u8, f64>,
    pub avg_entries_per_level: BTreeMap<u8, f64>,
    pub min_entries_per_level: BTreeMap<u8, usize>,
    pub max_entries_per_level: BTreeMap<u8, usize>,
    pub avg_fanout: f64,
    pub min_fanout: usize,
    pub max_fanout: usize,
    pub avg_fill_factor: f64,
    pub avg_leaf_fill_factor: f64,
    pub avg_internal_fill_factor: f64,
    pub avg_key_size_bytes: f64,
    pub avg_value_size_bytes: f64,
    pub min_key_size_bytes: usize,
    pub max_key_size_bytes: usize,
    pub min_value_size_bytes: usize,
    pub max_value_size_bytes: usize,
    pub total_keys_size_bytes: usize,
    pub total_values_size_bytes: usize,
    /* private fields */
}

Statistics about a Prolly tree structure

This struct contains comprehensive metrics about a Prolly tree, including structure, size, distribution, and efficiency information. Statistics are collected through a single tree traversal using Prolly::collect_stats.

Fields

Basic Structure

• num_nodes: Total number of nodes in the tree
• num_leaves: Number of leaf nodes (containing key-value pairs)
• num_internal_nodes: Number of internal nodes (containing child pointers)
• tree_height: Maximum level in the tree (0 for single-node trees)
• total_key_value_pairs: Total number of key-value pairs stored

Size Statistics

• total_tree_size_bytes: Total serialized size of all nodes
• avg_node_size_bytes: Average node size in bytes
• min_node_size_bytes: Smallest node size in bytes
• max_node_size_bytes: Largest node size in bytes
• avg_entries_per_node: Average number of entries per node

Level-Based Statistics

• nodes_per_level: Count of nodes at each level
• avg_node_size_per_level: Average node size at each level
• avg_entries_per_level: Average entries per node at each level
• min_entries_per_level: Minimum entries at each level
• max_entries_per_level: Maximum entries at each level

Fanout and Fill Factor

• avg_fanout: Average number of children per internal node
• min_fanout: Minimum fanout value
• max_fanout: Maximum fanout value
• avg_fill_factor: Average fill factor (entries / max_chunk_size)
• avg_leaf_fill_factor: Average fill factor for leaf nodes
• avg_internal_fill_factor: Average fill factor for internal nodes

Key and Value Sizes

• avg_key_size_bytes: Average key size in bytes
• avg_value_size_bytes: Average value size in bytes
• min_key_size_bytes: Smallest key size
• max_key_size_bytes: Largest key size
• min_value_size_bytes: Smallest value size
• max_value_size_bytes: Largest value size
• total_keys_size_bytes: Total size of all keys
• total_values_size_bytes: Total size of all values

Example

use prolly::{Config, MemStore, Prolly};

let store = MemStore::new();
let prolly = Prolly::new(store, Config::default());
let mut tree = prolly.create();

// Build a tree
for i in 0..100 {
    let key = format!("key_{}", i).into_bytes();
    let val = format!("value_{}", i).into_bytes();
    tree = prolly.put(&tree, key, val).unwrap();
}

// Collect statistics
let stats = prolly.collect_stats(&tree).unwrap();

println!("Tree has {} nodes at height {}", stats.num_nodes, stats.tree_height);
println!("Average fill factor: {:.2}%", stats.avg_fill_factor * 100.0);

Fields

num_nodes: usize

num_leaves: usize

num_internal_nodes: usize

tree_height: u8

total_key_value_pairs: usize

total_tree_size_bytes: usize

avg_node_size_bytes: f64

min_node_size_bytes: usize

max_node_size_bytes: usize

avg_entries_per_node: f64

nodes_per_level: BTreeMap<u8, usize>

avg_node_size_per_level: BTreeMap<u8, f64>

avg_entries_per_level: BTreeMap<u8, f64>

min_entries_per_level: BTreeMap<u8, usize>

max_entries_per_level: BTreeMap<u8, usize>

avg_fanout: f64

min_fanout: usize

max_fanout: usize

avg_fill_factor: f64

avg_leaf_fill_factor: f64

avg_internal_fill_factor: f64

avg_key_size_bytes: f64

avg_value_size_bytes: f64

min_key_size_bytes: usize

max_key_size_bytes: usize

min_value_size_bytes: usize

max_value_size_bytes: usize

total_keys_size_bytes: usize

total_values_size_bytes: usize

Implementations

impl TreeStats

pub fn new() -> Self

Create a new TreeStats with zero values

All counters are initialized to zero, and min values are set to usize::MAX (they will be reset to 0 for empty trees during finalization).

Example

use prolly::TreeStats;

let stats = TreeStats::new();
assert_eq!(stats.num_nodes, 0);
assert_eq!(stats.tree_height, 0);

impl TreeStats

pub fn accumulate(&mut self, node: &Node)

Accumulate statistics from a single node

Updates all relevant counters, min/max values, and level-based statistics based on the provided node. This method is called during tree traversal for each visited node.

After accumulating all nodes, call finalize to compute derived metrics like averages.

Arguments

• node - The node to accumulate statistics from

Example

use prolly::{TreeStats, Node};

let mut stats = TreeStats::new();
let node = Node::builder()
    .keys(vec![b"key".to_vec()])
    .vals(vec![b"value".to_vec()])
    .leaf(true)
    .level(0)
    .build();

stats.accumulate(&node);
assert_eq!(stats.num_nodes, 1);
assert_eq!(stats.num_leaves, 1);

pub fn finalize(&mut self)

Finalize statistics by calculating all derived metrics

This method should be called after all nodes have been accumulated. It calculates averages (node size, entries, fanout, fill factors, key/value sizes) and handles edge cases like division by zero.

For empty trees, min values are reset to 0.

Example

use prolly::{TreeStats, Node};

let mut stats = TreeStats::new();
let node = Node::builder()
    .keys(vec![b"key".to_vec()])
    .vals(vec![b"value".to_vec()])
    .leaf(true)
    .level(0)
    .max_chunk_size(10)
    .build();

stats.accumulate(&node);
stats.finalize();

assert!(stats.avg_node_size_bytes > 0.0);
assert_eq!(stats.avg_fill_factor, 0.1); // 1 entry / 10 max

pub fn diff(&self, other: &TreeStats) -> StatsDiff

Compute the difference between two statistics objects

Returns a StatsDiff object containing the difference for each numeric metric. Positive values indicate an increase, negative values indicate a decrease.

Arguments

• other - The statistics object to compare against (subtracted from self)

Returns

A StatsDiff object with differences for all metrics

pub fn percentage_change(&self, other: &TreeStats) -> StatsPercentageChange

Compute percentage changes between two statistics objects

Returns a StatsPercentageChange object containing the percentage change for each metric. Percentage change is calculated as: ((self - other) / other) * 100 Returns 0.0 for metrics where the base value (other) is zero.

Arguments

• other - The baseline statistics object to compare against

Returns

A StatsPercentageChange object with percentage changes for all metrics

pub fn add_node(&mut self, node: &Node, node_size_bytes: usize)

Update statistics after adding a node

This method incrementally updates statistics when a new node is added to the tree. It updates all relevant counters, min/max values, and totals. After calling this method, you should call finalize() to recalculate derived metrics (averages).

Arguments

• node - The node being added
• node_size_bytes - The serialized size of the node in bytes

pub fn remove_node(&mut self, node: &Node, node_size_bytes: usize)

Update statistics after removing a node

This method incrementally updates statistics when a node is removed from the tree. It decrements all relevant counters and updates totals. Note that min/max values cannot be accurately updated without a full traversal, so they are left unchanged. After calling this method, you should call finalize() to recalculate derived metrics.

Arguments

• node - The node being removed
• node_size_bytes - The serialized size of the node in bytes

pub fn update_node( &mut self, old_node: &Node, new_node: &Node, old_size: usize, new_size: usize, )

Update statistics after modifying a node

This method incrementally updates statistics when a node is modified in place. It adjusts size totals and entry counts if they changed. Min/max values are updated if the new values exceed the current bounds. After calling this method, you should call finalize() to recalculate derived metrics.

Arguments

• old_node - The node before modification
• new_node - The node after modification
• old_size - The serialized size of the old node in bytes
• new_size - The serialized size of the new node in bytes

pub fn validate<S: Store>( &self, prolly: &Prolly<S>, tree: &Tree, ) -> Result<bool, Error>

Validate that incremental statistics match full collection

This method collects fresh statistics from the tree and compares them with the current statistics object. Returns true if they are equal, false otherwise. This is useful for verifying that incremental updates have been applied correctly.

Arguments

• prolly - The Prolly instance to use for collecting statistics
• tree - The tree to validate against

Returns

• Ok(true) - Statistics match
• Ok(false) - Statistics do not match
• Err(Error) - On storage or deserialization errors

Trait Implementations

impl Clone for TreeStats

fn clone(&self) -> TreeStats

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for TreeStats

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for TreeStats

fn default() -> Self

Returns the “default value” for a type.

impl<'de> Deserialize<'de> for TreeStats

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Display for TreeStats

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl PartialEq for TreeStats

fn eq(&self, other: &Self) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl Serialize for TreeStats

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.