SweepStore (formerly BinaryTable)

A high-performance binary storage format for Dart applications with efficient memory management and random access capabilities.

Overview

BinaryTable is a key-value storage system designed for applications requiring fast, compact data persistence. It features a custom binary format with automatic memory management, making it ideal for game save files, caching systems, and other performance-critical data storage needs.

Features

Core Storage Types

• Integers: 32-bit signed integers
• Floats: 32-bit floating-point numbers
• Strings: Variable-length UTF-16 strings
• Uniform Arrays: Homogeneous arrays of integers or floats with O(1) random access

Memory Management

• Free List System: Automatic memory reclamation and defragmentation
• Block Merging: Contiguous free blocks are automatically merged
• File Truncation: Unused space at end of file is reclaimed
• Lift/Drop Mechanism: Prevents free list fragmentation during operations

Performance Features

• Random Access: Direct addressing for all data types
• Minimal Seeks: Optimized file layout reduces disk I/O
• Compact Format: No padding or alignment overhead
• Efficient Arrays: Uniform arrays use offset calculations for O(1) access

Usage

Basic Operations

// Initialize
File file = File('data.bin');
file.createSync();
BinaryTable table = BinaryTable(file.path);
table.initialise();

// Store values
table["player_level"] = 42;
table["player_name"] = "Hero";
table["score"] = 1337.5;

// Retrieve values
int level = table["player_level"];
String name = table["player_name"];
double score = table["score"];

// Delete entries
table.delete("old_data");

Array Operations

// Create arrays
table["inventory"] = [10, 20, 30, 40, 50];
table["coordinates"] = [1.5, 2.7, 3.9];

// Random access
table["inventory"][0] = 15;
double y = table["coordinates"][1];

// Dynamic growth
table["inventory"].add(60);
table["inventory"].addAll([70, 80, 90]);

// Pre-sized arrays (recommended for game data)
table["heightmap"] = List.filled(1024 * 1024, 0.0);

Memory Management

// Reclaim unused space
table.truncate();

// Manual cleanup (usually automatic)
table.delete("unused_key");
table.truncate();

Version History

Version 3.0 - Current

Added: Uniform Arrays

• BT_UniformArray class for homogeneous array storage
• O(1) random access for integer and float arrays
• Dynamic array growth with automatic reallocation
• Type safety enforcement for array elements
• Support for empty arrays with type inference on first use

Improvements:

• Enhanced memory management for variable-size data
• Optimized file format for array storage
• Better error handling for type mismatches

Version 2.0

Added: Persistent Free Lists

• Free list data persists across program restarts
• Automatic block merging for defragmentation
• File truncation to reclaim unused space
• "Read from end" encoding for free list metadata

Improvements:

• Eliminated memory leaks from previous version
• Reduced file size growth over time
• Better space utilization efficiency

Version 1.0

Core Features:

• Basic key-value storage (integers, floats, strings)
• Binary file format with type identification
• Address table for O(1) key lookups
• Volatile garbage collection (in-memory only)

Initial Implementation:

• RandomAccessFile-based storage
• Little-endian encoding
• Hash-based key addressing

File Format

The BinaryTable uses a custom binary format optimized for random access:

Header Structure

[Address Table Pointer: 8 bytes]
[Free List Entry Count: 4 bytes]

Data Layout

• Address Table: Hash-to-pointer mappings at variable location
• Free List: Memory management metadata at end of file
• Data Blocks: Variable-size type-prefixed data scattered throughout

Type Encoding

• Each value prefixed with type identifier byte
• Variable-length data includes size information
• Arrays store length followed by elements

Performance Characteristics

Time Complexity

• Key Lookup: O(1) average case
• Array Access: O(1) for uniform arrays
• Insertion: O(1) amortized
• Deletion: O(1) plus defragmentation cost

Space Efficiency

• Overhead: ~13 bytes per key-value pair minimum
• Arrays: 5 bytes + (5 bytes × length) for uniform arrays
• Fragmentation: Automatically managed and minimized

Use Cases

Game Development

• Save file persistence with fast loading
• Level data storage (heightmaps, object placement)
• Player progression and inventory systems
• Settings and configuration data

General Applications

• High-performance caching systems
• Embedded database applications
• Configuration file storage
• Any scenario requiring fast binary persistence

Limitations

• Hash Collisions: Uses Dart's built-in string hashCode (risk of collisions)
• File Corruption: No built-in checksums or validation
• Concurrent Access: Single-threaded access only
• Type System: Limited compared to JSON (no nested objects, mixed arrays)

SweepStore Roadmap

v1.0.0 (Current)

• ✅ Key-value storage with hash-based indexing
• ✅ Uniform arrays with random access
• ✅ Automatic memory management via free list
• ✅ Single file format (.sws)

v2.0.0 (Planned)

Core Changes

• Nested objects - Store objects within objects for hierarchical data
• Key enumeration - Query and list all keys without knowing them upfront
• Object-based architecture - Each object has its own address table and key list

File Format Changes

v1: Global address table → All keys at root level
v2: Root object → Each object manages its own keys

New API

// Nested objects
table["player"] = {};
table["player"]["name"] = "Alice";
table["player"]["inventory"] = {};

// Key discovery
List<String> keys = table.keys();
bool exists = table.containsKey("player");

// Object operations
BT_Object player = table["player"];
for (String key in player.keys()) {
  print("$key: ${player[key]}");
}

Implementation Strategy

• Introduce BT_Object type with embedded address table + key list
• BinaryTable becomes wrapper around root object
• Maintain global free list (not per-object)
• Address table entries remain absolute pointers
• Key list stored alongside each object's address table

Breaking Changes

• File format incompatible with v1.0.0
• API remains largely the same (only additions)
• Migration tool needed for v1 → v2 files

Future Considerations

• Hash collision resolution
• Checksums for data integrity
• Optimized allocation strategies
• Incremental array resizing
• Compression options