rustlite_core/
index.rs

1//! Indexing module for RustLite.
2//!
3//! This module provides B-Tree and Hash index implementations for efficient data retrieval.
4//! 
5//! ## Index Types
6//! 
7//! - **B-Tree Index**: Ordered index supporting range queries and prefix scans
8//! - **Hash Index**: Fast O(1) exact-match lookups
9//! 
10//! ## Example
11//! 
12//! ```rust
13//! use rustlite_core::index::{BTreeIndex, HashIndex, Index};
14//! 
15//! // B-Tree index for ordered access
16//! let mut btree = BTreeIndex::new();
17//! btree.insert(b"user:001", 100).unwrap();
18//! btree.insert(b"user:002", 200).unwrap();
19//! 
20//! // Range query
21//! let range = btree.range(b"user:001", b"user:999").unwrap();
22//! 
23//! // Hash index for fast lookups
24//! let mut hash = HashIndex::new();
25//! hash.insert(b"session:abc", 500).unwrap();
26//! assert_eq!(hash.find(b"session:abc").unwrap(), vec![500]);
27//! ```
28
29use std::collections::{BTreeMap, HashMap};
30
31/// Index type enumeration
32#[derive(Debug, Clone, Copy, PartialEq, Eq)]
33pub enum IndexType {
34    /// B-Tree index for ordered data and range queries
35    BTree,
36    /// Hash index for O(1) exact matches
37    Hash,
38    /// Full-text search index (planned for future)
39    FullText,
40}
41
42impl std::fmt::Display for IndexType {
43    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
44        match self {
45            IndexType::BTree => write!(f, "BTree"),
46            IndexType::Hash => write!(f, "Hash"),
47            IndexType::FullText => write!(f, "FullText"),
48        }
49    }
50}
51
52/// Index trait defining the common interface for all index types
53pub trait Index: Send + Sync {
54    /// Insert a key-value pair into the index.
55    /// The value is typically a pointer/offset to the actual data.
56    fn insert(&mut self, key: &[u8], value: u64) -> crate::Result<()>;
57
58    /// Find all values matching the exact key.
59    fn find(&self, key: &[u8]) -> crate::Result<Vec<u64>>;
60
61    /// Remove all entries for a key from the index.
62    /// Returns true if any entries were removed.
63    fn remove(&mut self, key: &[u8]) -> crate::Result<bool>;
64
65    /// Returns the number of entries in the index.
66    fn len(&self) -> usize;
67
68    /// Returns true if the index is empty.
69    fn is_empty(&self) -> bool {
70        self.len() == 0
71    }
72
73    /// Clear all entries from the index.
74    fn clear(&mut self);
75
76    /// Returns the index type.
77    fn index_type(&self) -> IndexType;
78}
79
80// ============================================================================
81// B-Tree Index Implementation
82// ============================================================================
83
84/// B-Tree based index for ordered key lookups and range queries.
85///
86/// This index maintains keys in sorted order, enabling:
87/// - Exact key lookups
88/// - Range queries (e.g., all keys between "a" and "z")
89/// - Prefix scans (e.g., all keys starting with "user:")
90/// - Ordered iteration
91///
92/// ## Performance
93/// - Insert: O(log n)
94/// - Lookup: O(log n)
95/// - Range query: O(log n + k) where k is the number of results
96///
97/// ## Example
98///
99/// ```rust
100/// use rustlite_core::index::{BTreeIndex, Index};
101///
102/// let mut index = BTreeIndex::new();
103/// index.insert(b"apple", 1).unwrap();
104/// index.insert(b"banana", 2).unwrap();
105/// index.insert(b"cherry", 3).unwrap();
106///
107/// // Exact lookup
108/// assert_eq!(index.find(b"banana").unwrap(), vec![2]);
109///
110/// // Range query
111/// let range = index.range(b"apple", b"cherry").unwrap();
112/// assert_eq!(range.len(), 3);
113/// ```
114#[derive(Debug, Clone)]
115pub struct BTreeIndex {
116    /// The underlying B-Tree map storing key -> list of values
117    tree: BTreeMap<Vec<u8>, Vec<u64>>,
118    /// Total number of key-value pairs (a key can have multiple values)
119    entry_count: usize,
120}
121
122impl BTreeIndex {
123    /// Create a new empty B-Tree index.
124    pub fn new() -> Self {
125        Self {
126            tree: BTreeMap::new(),
127            entry_count: 0,
128        }
129    }
130
131    /// Range query: find all entries where key is in [start, end] inclusive.
132    ///
133    /// Returns a vector of (key, values) pairs in sorted order.
134    pub fn range(&self, start: &[u8], end: &[u8]) -> crate::Result<Vec<(Vec<u8>, Vec<u64>)>> {
135        use std::ops::Bound;
136        
137        let results: Vec<_> = self
138            .tree
139            .range((Bound::Included(start.to_vec()), Bound::Included(end.to_vec())))
140            .map(|(k, v)| (k.clone(), v.clone()))
141            .collect();
142        
143        Ok(results)
144    }
145
146    /// Prefix scan: find all entries where key starts with the given prefix.
147    ///
148    /// Returns a vector of (key, values) pairs in sorted order.
149    pub fn prefix_scan(&self, prefix: &[u8]) -> crate::Result<Vec<(Vec<u8>, Vec<u64>)>> {
150        let results: Vec<_> = self
151            .tree
152            .range(prefix.to_vec()..)
153            .take_while(|(k, _)| k.starts_with(prefix))
154            .map(|(k, v)| (k.clone(), v.clone()))
155            .collect();
156        
157        Ok(results)
158    }
159
160    /// Get the minimum key in the index, if any.
161    pub fn min_key(&self) -> Option<&[u8]> {
162        self.tree.keys().next().map(|k| k.as_slice())
163    }
164
165    /// Get the maximum key in the index, if any.
166    pub fn max_key(&self) -> Option<&[u8]> {
167        self.tree.keys().next_back().map(|k| k.as_slice())
168    }
169
170    /// Iterate over all entries in sorted order.
171    pub fn iter(&self) -> impl Iterator<Item = (&[u8], &[u64])> {
172        self.tree.iter().map(|(k, v)| (k.as_slice(), v.as_slice()))
173    }
174}
175
176impl Default for BTreeIndex {
177    fn default() -> Self {
178        Self::new()
179    }
180}
181
182impl Index for BTreeIndex {
183    fn insert(&mut self, key: &[u8], value: u64) -> crate::Result<()> {
184        self.tree
185            .entry(key.to_vec())
186            .or_insert_with(Vec::new)
187            .push(value);
188        self.entry_count += 1;
189        Ok(())
190    }
191
192    fn find(&self, key: &[u8]) -> crate::Result<Vec<u64>> {
193        Ok(self.tree.get(key).cloned().unwrap_or_default())
194    }
195
196    fn remove(&mut self, key: &[u8]) -> crate::Result<bool> {
197        if let Some(values) = self.tree.remove(key) {
198            self.entry_count -= values.len();
199            Ok(true)
200        } else {
201            Ok(false)
202        }
203    }
204
205    fn len(&self) -> usize {
206        self.entry_count
207    }
208
209    fn clear(&mut self) {
210        self.tree.clear();
211        self.entry_count = 0;
212    }
213
214    fn index_type(&self) -> IndexType {
215        IndexType::BTree
216    }
217}
218
219// ============================================================================
220// Hash Index Implementation
221// ============================================================================
222
223/// Hash-based index for fast O(1) exact-match lookups.
224///
225/// This index uses a hash map for constant-time key lookups, making it ideal for:
226/// - Primary key lookups
227/// - Session/token lookups
228/// - Any scenario where you only need exact matches
229///
230/// ## Performance
231/// - Insert: O(1) average
232/// - Lookup: O(1) average
233/// - Delete: O(1) average
234///
235/// ## Limitations
236/// - Does not support range queries (use BTreeIndex for that)
237/// - Does not maintain order
238///
239/// ## Example
240///
241/// ```rust
242/// use rustlite_core::index::{HashIndex, Index};
243///
244/// let mut index = HashIndex::new();
245/// index.insert(b"session:abc123", 42).unwrap();
246/// index.insert(b"session:def456", 43).unwrap();
247///
248/// // Fast O(1) lookup
249/// assert_eq!(index.find(b"session:abc123").unwrap(), vec![42]);
250/// assert!(index.find(b"nonexistent").unwrap().is_empty());
251/// ```
252#[derive(Debug, Clone)]
253pub struct HashIndex {
254    /// The underlying hash map storing key -> list of values
255    map: HashMap<Vec<u8>, Vec<u64>>,
256    /// Total number of key-value pairs
257    entry_count: usize,
258}
259
260impl HashIndex {
261    /// Create a new empty Hash index.
262    pub fn new() -> Self {
263        Self {
264            map: HashMap::new(),
265            entry_count: 0,
266        }
267    }
268
269    /// Create a new Hash index with the specified capacity.
270    pub fn with_capacity(capacity: usize) -> Self {
271        Self {
272            map: HashMap::with_capacity(capacity),
273            entry_count: 0,
274        }
275    }
276
277    /// Check if the index contains a key.
278    pub fn contains_key(&self, key: &[u8]) -> bool {
279        self.map.contains_key(key)
280    }
281
282    /// Get the number of unique keys in the index.
283    pub fn key_count(&self) -> usize {
284        self.map.len()
285    }
286
287    /// Iterate over all entries (unordered).
288    pub fn iter(&self) -> impl Iterator<Item = (&[u8], &[u64])> {
289        self.map.iter().map(|(k, v)| (k.as_slice(), v.as_slice()))
290    }
291}
292
293impl Default for HashIndex {
294    fn default() -> Self {
295        Self::new()
296    }
297}
298
299impl Index for HashIndex {
300    fn insert(&mut self, key: &[u8], value: u64) -> crate::Result<()> {
301        self.map
302            .entry(key.to_vec())
303            .or_insert_with(Vec::new)
304            .push(value);
305        self.entry_count += 1;
306        Ok(())
307    }
308
309    fn find(&self, key: &[u8]) -> crate::Result<Vec<u64>> {
310        Ok(self.map.get(key).cloned().unwrap_or_default())
311    }
312
313    fn remove(&mut self, key: &[u8]) -> crate::Result<bool> {
314        if let Some(values) = self.map.remove(key) {
315            self.entry_count -= values.len();
316            Ok(true)
317        } else {
318            Ok(false)
319        }
320    }
321
322    fn len(&self) -> usize {
323        self.entry_count
324    }
325
326    fn clear(&mut self) {
327        self.map.clear();
328        self.entry_count = 0;
329    }
330
331    fn index_type(&self) -> IndexType {
332        IndexType::Hash
333    }
334}
335
336// ============================================================================
337// Index Manager
338// ============================================================================
339
340/// Manages multiple indexes for a database.
341///
342/// The IndexManager provides a centralized way to create, access, and manage
343/// indexes across the database. It supports both B-Tree and Hash indexes.
344///
345/// ## Example
346///
347/// ```rust
348/// use rustlite_core::index::{IndexManager, IndexType};
349///
350/// let mut manager = IndexManager::new();
351///
352/// // Create indexes
353/// manager.create_index("users_by_id", IndexType::Hash).unwrap();
354/// manager.create_index("users_by_name", IndexType::BTree).unwrap();
355///
356/// // Use indexes
357/// manager.insert("users_by_id", b"user:1", 100).unwrap();
358/// manager.insert("users_by_name", b"alice", 100).unwrap();
359/// ```
360pub struct IndexManager {
361    /// Named indexes
362    indexes: HashMap<String, Box<dyn Index>>,
363}
364
365impl IndexManager {
366    /// Create a new empty index manager.
367    pub fn new() -> Self {
368        Self {
369            indexes: HashMap::new(),
370        }
371    }
372
373    /// Create a new index with the given name and type.
374    pub fn create_index(&mut self, name: &str, index_type: IndexType) -> crate::Result<()> {
375        if self.indexes.contains_key(name) {
376            return Err(crate::Error::InvalidOperation(format!(
377                "Index '{}' already exists",
378                name
379            )));
380        }
381
382        let index: Box<dyn Index> = match index_type {
383            IndexType::BTree => Box::new(BTreeIndex::new()),
384            IndexType::Hash => Box::new(HashIndex::new()),
385            IndexType::FullText => {
386                return Err(crate::Error::InvalidOperation(
387                    "FullText index not yet implemented".to_string(),
388                ))
389            }
390        };
391
392        self.indexes.insert(name.to_string(), index);
393        Ok(())
394    }
395
396    /// Drop an index by name.
397    pub fn drop_index(&mut self, name: &str) -> crate::Result<bool> {
398        Ok(self.indexes.remove(name).is_some())
399    }
400
401    /// Get a reference to an index by name.
402    pub fn get_index(&self, name: &str) -> Option<&dyn Index> {
403        self.indexes.get(name).map(|b| b.as_ref())
404    }
405
406    /// Get a mutable reference to an index by name.
407    pub fn get_index_mut(&mut self, name: &str) -> Option<&mut (dyn Index + 'static)> {
408        self.indexes.get_mut(name).map(|b| b.as_mut())
409    }
410
411    /// Insert a key-value pair into a named index.
412    pub fn insert(&mut self, name: &str, key: &[u8], value: u64) -> crate::Result<()> {
413        let index = self.indexes.get_mut(name).ok_or_else(|| {
414            crate::Error::NotFound
415        })?;
416        index.insert(key, value)
417    }
418
419    /// Find values in a named index.
420    pub fn find(&self, name: &str, key: &[u8]) -> crate::Result<Vec<u64>> {
421        let index = self.indexes.get(name).ok_or_else(|| {
422            crate::Error::NotFound
423        })?;
424        index.find(key)
425    }
426
427    /// Remove a key from a named index.
428    pub fn remove(&mut self, name: &str, key: &[u8]) -> crate::Result<bool> {
429        let index = self.indexes.get_mut(name).ok_or_else(|| {
430            crate::Error::NotFound
431        })?;
432        index.remove(key)
433    }
434
435    /// List all index names.
436    pub fn list_indexes(&self) -> Vec<&str> {
437        self.indexes.keys().map(|s| s.as_str()).collect()
438    }
439
440    /// Get information about all indexes.
441    pub fn index_info(&self) -> Vec<IndexInfo> {
442        self.indexes
443            .iter()
444            .map(|(name, index)| IndexInfo {
445                name: name.clone(),
446                index_type: index.index_type(),
447                entry_count: index.len(),
448            })
449            .collect()
450    }
451}
452
453impl Default for IndexManager {
454    fn default() -> Self {
455        Self::new()
456    }
457}
458
459/// Information about an index.
460#[derive(Debug, Clone)]
461pub struct IndexInfo {
462    /// The name of the index.
463    pub name: String,
464    /// The type of the index.
465    pub index_type: IndexType,
466    /// The number of entries in the index.
467    pub entry_count: usize,
468}
469
470// ============================================================================
471// Tests
472// ============================================================================
473
474#[cfg(test)]
475mod tests {
476    use super::*;
477
478    #[test]
479    fn test_btree_index_basic_operations() {
480        let mut index = BTreeIndex::new();
481        
482        // Insert
483        index.insert(b"key1", 100).unwrap();
484        index.insert(b"key2", 200).unwrap();
485        index.insert(b"key1", 101).unwrap(); // Duplicate key with different value
486        
487        // Find
488        assert_eq!(index.find(b"key1").unwrap(), vec![100, 101]);
489        assert_eq!(index.find(b"key2").unwrap(), vec![200]);
490        assert!(index.find(b"key3").unwrap().is_empty());
491        
492        // Length
493        assert_eq!(index.len(), 3);
494        
495        // Remove
496        assert!(index.remove(b"key1").unwrap());
497        assert!(!index.remove(b"key1").unwrap());
498        assert_eq!(index.len(), 1);
499    }
500
501    #[test]
502    fn test_btree_index_range_query() {
503        let mut index = BTreeIndex::new();
504        
505        index.insert(b"a", 1).unwrap();
506        index.insert(b"b", 2).unwrap();
507        index.insert(b"c", 3).unwrap();
508        index.insert(b"d", 4).unwrap();
509        index.insert(b"e", 5).unwrap();
510        
511        let range = index.range(b"b", b"d").unwrap();
512        assert_eq!(range.len(), 3);
513        assert_eq!(range[0].0, b"b");
514        assert_eq!(range[1].0, b"c");
515        assert_eq!(range[2].0, b"d");
516    }
517
518    #[test]
519    fn test_btree_index_prefix_scan() {
520        let mut index = BTreeIndex::new();
521        
522        index.insert(b"user:001", 1).unwrap();
523        index.insert(b"user:002", 2).unwrap();
524        index.insert(b"user:003", 3).unwrap();
525        index.insert(b"order:001", 10).unwrap();
526        index.insert(b"order:002", 20).unwrap();
527        
528        let users = index.prefix_scan(b"user:").unwrap();
529        assert_eq!(users.len(), 3);
530        
531        let orders = index.prefix_scan(b"order:").unwrap();
532        assert_eq!(orders.len(), 2);
533    }
534
535    #[test]
536    fn test_btree_index_min_max() {
537        let mut index = BTreeIndex::new();
538        
539        assert!(index.min_key().is_none());
540        assert!(index.max_key().is_none());
541        
542        index.insert(b"middle", 2).unwrap();
543        index.insert(b"first", 1).unwrap();
544        index.insert(b"last", 3).unwrap();
545        
546        assert_eq!(index.min_key(), Some(b"first".as_slice()));
547        assert_eq!(index.max_key(), Some(b"middle".as_slice()));
548    }
549
550    #[test]
551    fn test_hash_index_basic_operations() {
552        let mut index = HashIndex::new();
553        
554        // Insert
555        index.insert(b"session:abc", 100).unwrap();
556        index.insert(b"session:def", 200).unwrap();
557        index.insert(b"session:abc", 101).unwrap();
558        
559        // Find
560        assert_eq!(index.find(b"session:abc").unwrap(), vec![100, 101]);
561        assert_eq!(index.find(b"session:def").unwrap(), vec![200]);
562        assert!(index.find(b"session:xyz").unwrap().is_empty());
563        
564        // Contains
565        assert!(index.contains_key(b"session:abc"));
566        assert!(!index.contains_key(b"session:xyz"));
567        
568        // Length
569        assert_eq!(index.len(), 3);
570        assert_eq!(index.key_count(), 2);
571    }
572
573    #[test]
574    fn test_hash_index_with_capacity() {
575        let index = HashIndex::with_capacity(100);
576        assert!(index.is_empty());
577    }
578
579    #[test]
580    fn test_index_manager() {
581        let mut manager = IndexManager::new();
582        
583        // Create indexes
584        manager.create_index("users", IndexType::Hash).unwrap();
585        manager.create_index("names", IndexType::BTree).unwrap();
586        
587        // Duplicate name should fail
588        assert!(manager.create_index("users", IndexType::Hash).is_err());
589        
590        // Insert into indexes
591        manager.insert("users", b"user:1", 100).unwrap();
592        manager.insert("names", b"alice", 100).unwrap();
593        manager.insert("names", b"bob", 101).unwrap();
594        
595        // Find
596        assert_eq!(manager.find("users", b"user:1").unwrap(), vec![100]);
597        assert_eq!(manager.find("names", b"alice").unwrap(), vec![100]);
598        
599        // List indexes
600        let names = manager.list_indexes();
601        assert_eq!(names.len(), 2);
602        
603        // Index info
604        let info = manager.index_info();
605        assert_eq!(info.len(), 2);
606        
607        // Drop index
608        assert!(manager.drop_index("users").unwrap());
609        assert!(!manager.drop_index("users").unwrap());
610        assert_eq!(manager.list_indexes().len(), 1);
611    }
612
613    #[test]
614    fn test_index_clear() {
615        let mut btree = BTreeIndex::new();
616        let mut hash = HashIndex::new();
617        
618        btree.insert(b"key", 1).unwrap();
619        hash.insert(b"key", 1).unwrap();
620        
621        assert!(!btree.is_empty());
622        assert!(!hash.is_empty());
623        
624        btree.clear();
625        hash.clear();
626        
627        assert!(btree.is_empty());
628        assert!(hash.is_empty());
629    }
630}
rustlite_core/index.rs

rustlite_core/
index.rs
