Radix Tree Implementation

A radix tree (also known as a patricia trie or radix trie) is a space-optimized tree data structure that enables efficient string key operations. This implementation provides a persistent radix tree backed by OurDB for durable storage.

Key Features

• Efficient prefix-based key operations
• Persistent storage using OurDB backend
• Memory-efficient storage of strings with common prefixes
• Support for binary values
• Thread-safe operations through OurDB

How It Works

Data Structure

The radix tree is composed of nodes where:- Each node stores a segment of a key (not just a single character)

• Nodes can have multiple children, each representing a different branch
• Leaf nodes contain the actual values
• Each node is persisted in OurDB with a unique ID

struct Node {
mut:
    key_segment string    // The segment of the key stored at this node
    value      []u8      // Value stored at this node (empty if not a leaf)
    children   []NodeRef // References to child nodes
    is_leaf    bool      // Whether this node is a leaf node
}

OurDB Integration

The radix tree uses OurDB as its persistent storage backend:- Each node is serialized and stored as a record in OurDB

• Node references use OurDB record IDs
• The tree maintains a root node ID for traversal
• Node serialization includes version tracking for format evolution

Key Operations

Insertion

1. Traverse the tree following matching prefixes
2. Split nodes when partial matches are found
3. Create new nodes for unmatched segments
4. Update node values and references in OurDB

Search

1. Start from the root node
2. Follow child nodes whose key segments match the search key
3. Return the value if an exact match is found at a leaf node

Deletion

1. Locate the node containing the key
2. Remove the value and leaf status
3. Clean up empty nodes if necessary
4. Update parent references

Usage Example

import freeflowuniverse.herolib.data.radixtree

// Create a new radix tree
mut tree := radixtree.new('/path/to/storage')!

// Insert key-value pairs
tree.insert('hello', 'world'.bytes())!
tree.insert('help', 'me'.bytes())!

// Search for values
value := tree.search('hello')! // Returns 'world' as bytes
println(value.bytestr()) // Prints: world

// Delete keys
tree.delete('help')!

Implementation Details

Node Serialization

Nodes are serialized in a compact binary format:

[Version(1B)][KeySegment][ValueLength(2B)][Value][ChildrenCount(2B)][Children][IsLeaf(1B)]

Where each child is stored as:

[KeyPart][NodeID(4B)]

Space Optimization

The radix tree optimizes space usage by:1. Sharing common prefixes between keys2. Storing only key segments at each node instead of complete keys3. Merging nodes with single children when possible4. Using OurDB's efficient storage and retrieval mechanisms

Performance Characteristics

• Search: O(k) where k is the key length
• Insert: O(k) for new keys, may require node splitting
• Delete: O(k) plus potential node cleanup
• Space: O(n) where n is the total length of all keys

Relationship with OurDB

This radix tree implementation leverages OurDB's features:- Persistent storage with automatic file management

• Record-based storage with unique IDs
• Data integrity through CRC32 checksums
• Configurable record sizes
• Automatic file size management

The integration provides:- Durability: All tree operations are persisted

• Consistency: Tree state is maintained across restarts
• Efficiency: Leverages OurDB's optimized storage
• Scalability: Handles large datasets through OurDB's file management

Use Cases

Radix trees are particularly useful for:- Prefix-based searching

• IP routing tables
• Dictionary implementations
• Auto-complete systems
• File system paths
• Any application requiring efficient string key operations with persistence

fn new(args NewArgs) !&RadixTree

Creates a new radix tree with the specified database path

struct NewArgs {
pub mut:
	path  string
	reset bool
}

struct RadixTree {
mut:
	db      &ourdb.OurDB // Database for persistent storage
	root_id u32          // Database ID of the root node
}

RadixTree represents a radix tree data structure

fn (mut rt RadixTree) debug_db() !

Prints the current state of the database

fn (mut rt RadixTree) debug_node(id u32, msg string) !

Logs the current state of a node

fn (mut rt RadixTree) delete(key string) !

Deletes a key from the tree

fn (mut rt RadixTree) get_node_by_id(id u32) !Node

Gets a node from the database by its ID

fn (mut rt RadixTree) get_node_info(id u32) !string

Gets detailed information about a specific node

fn (mut rt RadixTree) insert(key string, value []u8) !

Inserts a key-value pair into the tree

fn (mut rt RadixTree) print_tree() !

Prints the entire tree structure starting from root

fn (mut rt RadixTree) print_tree_from_node(node_id u32, indent string) !

Prints the tree structure starting from a given node ID

fn (mut rt RadixTree) search(key string) ![]u8

Searches for a key in the tree