Module engine

Expand description

RedDB Storage Engine

A page-based storage engine inspired by SQLite/Turso architecture. Implements 4KB aligned pages for efficient disk I/O with SIEVE caching.

§Architecture

┌─────────────────────────────────────────────────────────────┐
│                       Database API                          │
├─────────────────────────────────────────────────────────────┤
│                       B-Tree Engine                         │
├─────────────────────────────────────────────────────────────┤
│  Page Cache (SIEVE)  │     Pager (I/O)     │   Free List   │
├─────────────────────────────────────────────────────────────┤
│                     Page Structure                          │
├─────────────────────────────────────────────────────────────┤
│                   File System / WAL                         │
└─────────────────────────────────────────────────────────────┘

§References

Turso core/storage/pager.rs - Page I/O management
Turso core/storage/page_cache.rs - SIEVE eviction algorithm
Turso core/storage/btree.rs - B-tree page layout

Modules§

algorithms: Graph Algorithms for RedDB
binary_quantize: Binary Quantization for Vector Embeddings
btree: B+ Tree Implementation for Page-Based Storage
bulk_writer: Page-Based Bulk Writer — like PostgreSQL COPY FROM
clustering: Standalone vector clustering: K-Means and DBSCAN.
crc32: CRC32 checksum implementation (IEEE 802.3 polynomial)
database: RedDB Database Engine
distance: Distance Functions for Vector Operations
encrypted_pager: Encrypted Pager (deprecated wrapper).
freelist: Free Page List Management
graph_store: High-Performance Disk-Backed Graph Storage Engine
graph_table_index: Bidirectional Graph-Table Index
hnsw: HNSW (Hierarchical Navigable Small World) Index
hot_update: HOT (Heap-Only Tuple) update decision — pure policy helper.
hybrid: Hybrid Search for RedDB
int8_quantize: int8 Quantization for Vector Embeddings
ivf: IVF (Inverted File Index) for Vector Search
page: Page structure for RedDB storage engine
page_cache: SIEVE Page Cache Implementation
pager: Pager - Page I/O Manager
pathfinding: Path Finding Algorithms for RedDB
pq: Product Quantization (PQ) for Vector Compression
projection: Graph Projections for RedDB
simd_distance: SIMD-Optimized Distance Functions
store_strategy: Triple Store Strategies
tiered_search: Tiered Vector Search Pipeline
unified_index: Unified Cross-Storage Index
vector_metadata: Vector Metadata Storage
vector_store: Vector Store

Structs§

AStar: A* Algorithm for heuristic-guided shortest paths
AllPathsResult: Result of all shortest paths query
AllShortestPaths: Find all shortest paths (same minimum length) between two nodes
BFS: Breadth-First Search for unweighted shortest paths
BM25Config: BM25 parameters
BTree: B+ Tree implementation
BTreeCursor: B+ Tree cursor for iteration
BellmanFord: Bellman-Ford Algorithm for graphs with negative weights
BellmanFordResult: Result of Bellman-Ford algorithm
BetweennessCentrality: Betweenness centrality computation using Brandes’ algorithm
BetweennessResult: Result of betweenness centrality computation
BinaryIndex: Index of binary vectors for fast batch search
BinarySearchResult: Result from binary search with rescoring capability
BinaryVector: Binary quantized vector stored as packed u64 words
Bitset: Bitset for efficient filtering
ClosenessCentrality: Closeness centrality measures how close a node is to all other nodes
ClosenessResult: Result of closeness centrality computation
ClusteringCoefficient: Local and global clustering coefficient
ClusteringResult: Result of clustering coefficient computation
CommunitiesResult: Result of community detection
Community: A community of nodes
Component: A connected component in the graph
ComponentsResult: Result of connected components computation
ConnectedComponents: Connected components finder
CrossRef: Cross-reference between two storage elements
Cycle: A cycle in the graph
CycleDetector: DFS-based cycle detection
CyclesResult: Result of cycle detection
DFS: Depth-First Search for deep graph exploration
Database: RedDB Database Engine
DatabaseConfig: Database configuration
DegreeCentrality: Degree centrality measures node importance by connection count
DegreeCentralityResult: Result of degree centrality computation
Dijkstra: Dijkstra’s Algorithm for weighted shortest paths
Distance: A distance value that can be compared and used in heaps
DistanceResult: Result of a distance computation with an ID
EdgeFilter: Edge filter specification
EigenvectorCentrality: Eigenvector centrality: importance based on neighbor importance
EigenvectorResult: Result of eigenvector centrality computation
EncryptedPagerDeprecated: Thin wrapper around Pager that maps the legacy EncryptedPager::{read_page, write_page} calls onto the new Pager::{read_page_decrypted, write_page_encrypted} surface.
EncryptedPagerConfig
ExactMatchReranker: Simple re-ranker that boosts exact matches
FreeList: In-memory freelist tracking
GraphProjection: A projected view of a graph
GraphStore: High-performance graph storage engine
GraphTableIndex: Bidirectional index for graph-table linkage
GraphTableIndexStats: Statistics for GraphTableIndex
HITS: HITS algorithm: Identifies hubs and authorities
HITSResult: Result of HITS computation
HnswConfig: HNSW index configuration parameters
HnswIndex: HNSW Index for approximate nearest neighbor search
HnswStats: Statistics about an HNSW index
HybridQueryBuilder: Builder for hybrid queries
HybridResult: Result from hybrid search
HybridSearch: Hybrid search combining dense and sparse retrieval
Int8Index: Index of int8 vectors for batch operations
Int8Vector: int8 quantized vector with scale factor
IvfConfig: IVF configuration
IvfIndex: IVF Index for approximate nearest neighbor search
IvfStats: IVF index statistics
KShortestPaths: K-Shortest Paths using Yen’s Algorithm
LabelId: Densely-numbered identifier for a label string within a LabelRegistry.
LabelPropagation: Label Propagation Algorithm for community detection
LabelRegistry: Bidirectional label ↔ LabelId catalog with concurrent access.
Louvain: Louvain algorithm for community detection
LouvainResult: Result of Louvain community detection
MemoryConstraint: Memory constraint configuration for resource-limited systems
MemoryLimitError: Error returned when memory limit is reached
MetadataEntry: A metadata entry containing key-value pairs organized by type
MetadataStore: Metadata storage with inverted indexes for filtering
NodeFilter: Node filter specification
PQConfig: PQ configuration
PQIndex: PQ-based index for compressed vector search
Page: A 4KB page with header and content
PageCache: Sharded page cache.
PageHeader: Page header structure (32 bytes)
PageRank: PageRank algorithm for identifying critical nodes
PageRankResult: Result of PageRank computation
Pager: Page I/O Manager
PagerConfig: Pager configuration
Path: A path through the graph
PersonalizedPageRank: Personalized PageRank - teleport only to specified seed nodes
PhysicalFileHeader: Minimal physical state published into page 0 for paged databases.
ProductQuantizer: Product Quantizer
ProjectedNode: A projected node with minimal data for algorithms
ProjectionBuilder: Builder for creating graph projections with fluent API
ProjectionStats: Statistics about the projection
PropertyProjection: Specifies which properties to include in the projection
RerankerPipeline: Re-ranking pipeline
RowKey: Composite key for row lookups: (table_id, row_id)
SCCResult: Result of SCC computation
SearchResult: Result of a vector search
SegmentConfig: Configuration for vector segments
ShortestPathResult: Result of a shortest path query
SparseIndex: Sparse inverted index for keyword search
SparseResult: Result from sparse search
StoredEdge: A graph edge stored on disk
StoredNode: A graph node stored on disk
StronglyConnectedComponents: Strongly connected components using Tarjan’s algorithm
TableRef: Reference to a table row (for linking graph nodes to tabular data)
TableRowKey: Unique identifier for a row in a table
TieredIndex: Tiered vector index with binary, int8, and optional fp32 representations
TieredIndexBuilder: Builder for creating tiered indexes with custom configuration
TieredMemoryStats: Memory usage statistics for tiered index
TieredSearchConfig: Configuration for tiered search
TieredSearchResult: Result from tiered search
TriangleCounting: Count triangles in the graph
TriangleResult: Result of triangle counting
UnifiedIndex: Unified index for cross-storage lookups
UnifiedIndexStats: Statistics about the unified index
VectorCollection: Vector collection containing multiple segments
VectorKey: Unique identifier for a vector in a collection
VectorSegment: A vector segment containing vectors, metadata, and optional index
VectorStore: Multi-collection vector store
WCCResult: Result of weakly connected components
WeaklyConnectedComponents: Weakly connected components - treats directed graph as undirected

Enums§

AggregationStrategy: Strategy for aggregating parallel edges
BTreeError: B+ Tree error types
DatabaseError: Database error types
DistanceMetric: Distance metric types supported by vector operations
EncryptedPagerError: Errors emitted by the deprecated wrapper. Surface kept stable for existing callers; new code should use PagerError directly.
FusionMethod: Method for combining dense and sparse scores
MetadataFilter: Metadata filter operators
MetadataValue: A metadata value that can be one of several types
PageType: Page type enumeration
SegmentState: Segment state in its lifecycle
StorageRef: A reference to any storage element
VectorStoreError: Vector store errors

Constants§

HEADER_SIZE: Header size in bytes
PAGE_SIZE: Page size in bytes (4KB, standard for most file systems)

Traits§

Reranker: Re-ranker for adjusting hybrid search results

Functions§

cosine_distance: Compute cosine distance between two vectors
crc32: Compute CRC32 checksum of data.
dbsf_fusion: Distribution-Based Score Fusion
distance: Compute distance between two vectors using the specified metric
dot_product: Compute dot product (inner product) between two vectors
dot_product_i8_f32_simd: Compute dot product of i8 vector with f32 query (asymmetric)
dot_product_i8_simd: Compute dot product of two i8 vectors using SIMD
hamming_distance_simd: Compute Hamming distance between two packed binary vectors using SIMD
inner_product_distance: Compute inner product distance (negated for min-heap compatibility)
l2: Compute L2 (Euclidean) distance between two vectors
l2_norm: Compute the L2 norm (magnitude) of a vector
l2_squared: Compute L2 (Euclidean) squared distance between two vectors
linear_fusion: Linear combination of scores
normalize: Normalize a vector to unit length (in-place)
normalized: Create a normalized copy of a vector
reciprocal_rank_fusion: Reciprocal Rank Fusion

Type Aliases§

NodeId: Node identifier in the HNSW graph
PQCode: PQ code for a single vector (M bytes)
SegmentId: Unique identifier for a segment
VectorId: Unique identifier for a vector within a collection

Module engine

Module engine Copy item path

§Architecture

§References

Modules§

Structs§

Enums§

Constants§

Traits§

Functions§

Type Aliases§

Module engine