Prolly Tree

Prolly Tree 是一种结合了 B 树和 Merkle 树特性的混合数据结构，它提供了高效的数据访问和可验证的数据完整性。它专门设计用于处理分布式系统和大型数据库的需求，使索引能够在点对点（P2P）网络上进行同步和分发。

入门指南

构建项目

cargo build

运行测试

cargo test

检查格式和样式

cargo fmt
cargo clippy

关键特性

• 平衡结构：Prolly Tree 继承了 B 树的平衡结构，这确保了插入、删除和查找等操作的高效性。这是通过保持一个平衡的树来实现的，其中每个节点可以有多个子节点，确保树保持浅层，操作复杂度为对数级别。

• 概率平衡：所谓的“概率”方面指的是用于以非严格确定性的方式维护树平衡的技术。这允许更灵活地处理突变（插入和删除），同时仍然确保树保持有效的平衡。

• Merkle 属性：Prolly Tree 中的每个节点都包含一个基于其自身内容及其子节点哈希的加密哈希。这创建了一个可验证的结构，其中任何对数据的修改都可以通过比较根哈希来检测。这种 Merkle 哈希提供了包含/排除证明，使数据的高效和安全验证成为可能。

• 高效数据访问：与 B 树一样，Prolly Tree 支持高效随机读取和写入以及有序扫描。这使得它们适用于需要同时进行随机访问和顺序访问模式的数据库操作。Prolly Tree 中的块大小得到严格控制，有助于优化读写操作。

• 分布式和可同步：Prolly Tree 设计用于在分布式环境中使用。Merkle 树属性使不同节点之间数据的同步、差异比较和合并变得高效且正确。这使得 Prolly Tree 成为数据需要在多个位置或设备上分发并保持同步的应用程序的理想选择。

优势

• 可验证性：Prolly Tree 中的加密哈希确保数据完整性，并允许进行包含/排除的可验证证明。
• 性能：平衡树结构提供了类似于 B 树的高效数据访问模式，确保了随机和顺序访问的高性能。
• 可扩展性：Prolly 树适合用于大规模应用，提供高效的索引维护和数据分布能力。
• 灵活性：概率平衡允许处理各种变异模式，而不会降低性能或结构。

用例

• 分布式数据库：在分布式系统中高效维护和同步索引。
• 版本控制系统：为大型数据集启用可验证的差异、同步和合并操作。
• 区块链和P2P网络：管理并同步具有可验证完整性的数据。
• 实时协同编辑：支持多个用户同时进行高效合并的更改。
• 云存储服务：管理文件版本并确保高效的数据检索和同步。

使用方法

要使用此库，请将以下内容添加到您的 Cargo.toml

[dependencies]
prollytree = "0.1.0-beta.1"

use prollytree::tree::ProllyTree;

fn main() {
    // 1. Create a custom tree config
    let config = TreeConfig {
        base: 131,
        modulus: 1_000_000_009,
        min_chunk_size: 4,
        max_chunk_size: 8 * 1024,
        pattern: 0b101,
        root_hash: None,
    };

    // 2. Create and Wrap the Storage Backend
    let storage = InMemoryNodeStorage::<32>::new();

    // 3. Create the Prolly Tree
    let mut tree = ProllyTree::new(storage, config);

    // 4. Insert New Key-Value Pairs
    tree.insert(b"key1".to_vec(), b"value1".to_vec());
    tree.insert(b"key2".to_vec(), b"value2".to_vec());

    // 5. Traverse the Tree with a Custom Formatter
    let traversal = tree.formatted_traverse(|node| {
        let keys_as_strings: Vec<String> = node.keys.iter().map(|k| format!("{:?}", k)).collect();
        format!("[L{}: {}]", node.level, keys_as_strings.join(", "))
    });
    println!("Traversal: {}", traversal);

    // 6. Update the Value for an Existing Key
    tree.update(b"key1".to_vec(), b"new_value1".to_vec());

    // 7. Find or Search for a Key
    if let Some(node) = tree.find(b"key1") {
        println!("Found key1 with value: {:?}", node);
    } else {
        println!("key1 not found");
    }

    // 8. Delete a Key-Value Pair
    if tree.delete(b"key2") {
        println!("key2 deleted");
    } else {
        println!("key2 not found");
    }

    // 9. Print tree stats
    println!("Size: {}", tree.size());
    println!("Depth: {}", tree.depth());
    println!("Summary: {}", tree.summary());

    // 10. Print tree structure
    println!("{:?}", tree.root.print_tree(&tree.storage));    
}

Prolly 树结构示例

以下是具有3个层的Prolly树结构的示例

root:
└── *[0, 23, 63, 85]
    ├── *[0, 2, 7, 13]
    │   ├── [0, 1]
    │   ├── [2, 3, 4, 5, 6]
    │   ├── [7, 8, 9, 10, 11, 12]
    │   └── [13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
    ├── *[23, 29, 36, 47, 58]
    │   ├── [23, 24, 25, 26, 27, 28]
    │   ├── [29, 30, 31, 32, 33, 34, 35]
    │   ├── [36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46]
    │   ├── [47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57]
    │   └── [58, 59, 60, 61, 62]
    ├── *[63, 77, 80]
    │   ├── [63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76]
    │   ├── [77, 78, 79]
    │   └── [80, 81, 82, 83, 84]
    └── *[85, 89, 92, 98]
        ├── [85, 86, 87, 88]
        ├── [89, 90, 91]
        ├── [92, 93, 94, 95, 96, 97]
        └── [98, 99, 100]

Note: *[keys] indicates internal node, [keys] indicates leaf node

这可以通过在树的根节点上使用 print_tree 方法生成。

文档

有关详细文档和示例，请访问 docs.rs/prollytree。

路线图

以下功能是为0.1.0版本的Prolly树库提供的

• 实现基本的Prolly树结构
• 实现插入和删除操作
• 实现树遍历和搜索
• 实现树大小和深度计算
• 实现树配置和树元数据处理
• 实现证明生成和验证
• 批量插入和删除

以下功能是为0.2.0版本的Prolly树库提供的

• Arrow块编码和解码
• Parquet/Avro块编码和解码
• 高级概率树平衡

贡献

欢迎贡献！请提交一个pull request或打开一个issue来讨论改进或功能。

许可证

本项目采用MIT许可证。有关详细信息，请参阅LICENSE文件。