Tree Store Data Structure
Relevant source files
The following files were used as context for generating this wiki page:
The Tree Store Data Structure is a core component of the chkpt system responsible for representing the hierarchical structure of a workspace. It functions as a content-addressed storage system for directory manifests, allowing chkpt to reconstruct the exact state of a filesystem at any given snapshot.
The Tree Store captures metadata for files, directories, and symlinks, organizing them into a Merkle-tree-like structure where each directory's hash is derived from the hashes of its contents. This architecture enables efficient deduplication—identical directory structures across different snapshots or even within the same snapshot are stored only once.
Sources: crates/chkpt-core/src/store/tree.rs:1-12, crates/chkpt-core/src/ops/save.rs:434-440, README.md:144-153
Data Models and Entities
The Tree Store relies on two primary data structures to define filesystem nodes and their relationships.
TreeEntry
The TreeEntry is the fundamental unit of the tree. It represents a single node within a directory (a file, a subdirectory, or a symlink).
| Field | Type | Description |
|---|---|---|
name | String | The name of the file or directory. |
entry_type | EntryType | Enum indicating if the entry is a File, Dir, or Symlink. |
hash | [u8; 16] | XXH3-128 hash of the entry's content (for files/symlinks) or the subtree (for directories). |
size | u64 | The size of the file in bytes (0 for directories). |
mode | u32 | Unix filesystem permissions and mode bits. |
Sources: crates/chkpt-core/src/store/tree.rs:20-28, crates/chkpt-napi/src/store.rs:41-47
EntryType
A simple enumeration used to distinguish between different types of filesystem objects.
pub enum EntryType {
File,
Dir,
Symlink,
}
Sources: crates/chkpt-core/src/store/tree.rs:13-18
Physical Storage Layout
Trees are stored in two formats: Loose Files for small or individual operations and Tree Packs for efficient bulk storage.
Storage Hierarchy
The physical files are located within the project's store directory, specifically under the trees/ subdirectory.
The system uses a 2-character prefix for loose files to avoid directory saturation (e.g., trees/a3/b2c1...).
Sources: crates/chkpt-core/src/config.rs:59-63, crates/chkpt-core/src/store/tree.rs:89-92, crates/chkpt-cli/skills/chkpt/references/store-layout.md:6-14
Tree Pack Structure
Packs consist of two files: trees.dat (the data) and trees.idx (the index). The data file starts with a magic header CKTL followed by the entry count.
| Component | Offset/Size | Format |
|---|---|---|
| Magic Header | 0-4 bytes | b"CKTL" |
| Entry Count | 4-8 bytes | u32 (Little Endian) |
| Index Entry | 32 bytes | Hash (16) + Offset (8) + Size (8) |
Sources: crates/chkpt-core/src/store/tree.rs:10-12, crates/chkpt-core/src/store/tree.rs:135-140
Tree Construction Logic
Trees are built bottom-up during the save operation. This ensures that a parent directory's hash can only be computed after all its children (including subdirectories) have been processed.
Bottom-Up Build Process
- Grouping: Files are grouped by their parent directory path.
- Hierarchy Registration: Missing directory paths in the hierarchy are registered.
- Sorting: Directories are sorted by depth, ensuring the deepest directories are processed first.
- Hashing: For each directory, a list of
TreeEntryis encoded usingbitcodeand hashed withXXH3-128. - Persistence: The resulting tree manifests are written to the
TreeStore.
TreeStore Operations
The TreeStore struct provides the API for interacting with tree data. It utilizes memory mapping (mmap) for high-performance access to pack files.
Key Methods
| Method | Description |
|---|---|
new(base_dir) | Initializes the store and mmaps trees.dat and trees.idx if they exist. |
write(entries) | Writes a single tree to a loose file. Used for tests and small ops. |
write_pack(entries) | Appends a batch of trees to the pack file and updates the index. |
read(hash_hex) | Retrieves a tree's entries. Checks the pack first, then loose files. |
Sources: crates/chkpt-core/src/store/tree.rs:37-87, crates/chkpt-core/src/store/tree.rs:172-192
Read Path Sequence
When a tree is requested by its hash, the system performs a binary search within the memory-mapped index.
Integration with Snapshots
While the Tree Store handles the structural metadata, the Metadata Catalog (SQLite) stores the snapshot metadata. A snapshot points to a root_tree_hash, which serves as the entry point into the Tree Store for reconstructing the full workspace manifest.
In modern versions of chkpt, the system prioritizes flattened manifests in SQLite (snapshot_files table) for performance, but tree nodes remain critical for reconstruction and fallback traversal.
Sources: crates/chkpt-core/src/ops/save.rs:205-215, crates/chkpt-cli/skills/chkpt/references/store-layout.md:65-74, crates/chkpt-plugin/skills/chkpt/references/store-layout.md:14-23
Summary
The Tree Store provides the structural backbone for chkpt's content-addressable storage. By separating directory structure (Trees) from file content (Blobs), the system achieves significant deduplication. The use of memory-mapped packs and binary-searched indexes ensures that even with thousands of directories, tree traversal and snapshot reconstruction remain fast.