189 lines
4.5 KiB
Markdown
189 lines
4.5 KiB
Markdown
# RadixTree
|
|
|
|
A persistent radix tree implementation in Rust using OurDB for storage.
|
|
|
|
## Overview
|
|
|
|
RadixTree is a space-optimized tree data structure that enables efficient string key operations with persistent storage. This implementation provides a persistent radix tree that can be used for efficient prefix-based key operations, such as auto-complete, routing tables, and more.
|
|
|
|
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. Unlike a standard trie where each node represents a single character, a radix tree compresses paths by allowing nodes to represent multiple characters (key segments).
|
|
|
|
Key characteristics:
|
|
- 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
|
|
- Optimizes storage by compressing common prefixes
|
|
|
|
## 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
|
|
|
|
## Usage
|
|
|
|
Add the dependency to your `Cargo.toml`:
|
|
|
|
```toml
|
|
[dependencies]
|
|
radixtree = { path = "../radixtree" }
|
|
```
|
|
|
|
### Basic Example
|
|
|
|
```rust
|
|
use radixtree::RadixTree;
|
|
|
|
fn main() -> Result<(), radixtree::Error> {
|
|
// Create a new radix tree
|
|
let mut tree = RadixTree::new("/tmp/radix", false)?;
|
|
|
|
// Set key-value pairs
|
|
tree.set("hello", b"world".to_vec())?;
|
|
tree.set("help", b"me".to_vec())?;
|
|
|
|
// Get values by key
|
|
let value = tree.get("hello")?;
|
|
println!("hello: {}", String::from_utf8_lossy(&value)); // Prints: world
|
|
|
|
// List keys by prefix
|
|
let keys = tree.list("hel")?; // Returns ["hello", "help"]
|
|
println!("Keys with prefix 'hel': {:?}", keys);
|
|
|
|
// Get all values by prefix
|
|
let values = tree.getall("hel")?; // Returns [b"world", b"me"]
|
|
|
|
// Delete keys
|
|
tree.delete("help")?;
|
|
|
|
Ok(())
|
|
}
|
|
```
|
|
|
|
## API
|
|
|
|
### Creating a RadixTree
|
|
|
|
```rust
|
|
// Create a new radix tree
|
|
let mut tree = RadixTree::new("/tmp/radix", false)?;
|
|
|
|
// Create a new radix tree and reset if it exists
|
|
let mut tree = RadixTree::new("/tmp/radix", true)?;
|
|
```
|
|
|
|
### Setting Values
|
|
|
|
```rust
|
|
// Set a key-value pair
|
|
tree.set("key", b"value".to_vec())?;
|
|
```
|
|
|
|
### Getting Values
|
|
|
|
```rust
|
|
// Get a value by key
|
|
let value = tree.get("key")?;
|
|
```
|
|
|
|
### Updating Values
|
|
|
|
```rust
|
|
// Update a value at a given prefix
|
|
tree.update("prefix", b"new_value".to_vec())?;
|
|
```
|
|
|
|
### Deleting Keys
|
|
|
|
```rust
|
|
// Delete a key
|
|
tree.delete("key")?;
|
|
```
|
|
|
|
### Listing Keys by Prefix
|
|
|
|
```rust
|
|
// List all keys with a given prefix
|
|
let keys = tree.list("prefix")?;
|
|
```
|
|
|
|
### Getting All Values by Prefix
|
|
|
|
```rust
|
|
// Get all values for keys with a given prefix
|
|
let values = tree.getall("prefix")?;
|
|
```
|
|
|
|
## 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
|
|
|
|
## Use Cases
|
|
|
|
RadixTree is 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
|
|
|
|
## Implementation Details
|
|
|
|
The RadixTree implementation uses OurDB for persistent storage:
|
|
- 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
|
|
|
|
For more detailed information about the implementation, see the [ARCHITECTURE.md](./ARCHITECTURE.md) file.
|
|
|
|
## Running Tests
|
|
|
|
The project includes a comprehensive test suite that verifies all functionality:
|
|
|
|
```bash
|
|
# Run all tests
|
|
cargo test
|
|
|
|
# Run specific test file
|
|
cargo test --test basic_test
|
|
cargo test --test prefix_test
|
|
cargo test --test getall_test
|
|
cargo test --test serialize_test
|
|
```
|
|
|
|
## Running Examples
|
|
|
|
The project includes example applications that demonstrate how to use the RadixTree:
|
|
|
|
```bash
|
|
# Run the basic usage example
|
|
cargo run --example basic_usage
|
|
|
|
# Run the prefix operations example
|
|
cargo run --example prefix_operations
|
|
```
|
|
|
|
## Benchmarking
|
|
|
|
The project includes benchmarks to measure performance:
|
|
|
|
```bash
|
|
# Run all benchmarks
|
|
cargo bench
|
|
|
|
# Run specific benchmark
|
|
cargo bench -- set
|
|
cargo bench -- get
|
|
cargo bench -- prefix_operations
|
|
```
|
|
|
|
## License
|
|
|
|
This project is licensed under the same license as the HeroCode project. |