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((
140                Bound::Included(start.to_vec()),
141                Bound::Included(end.to_vec()),
142            ))
143            .map(|(k, v)| (k.clone(), v.clone()))
144            .collect();
145
146        Ok(results)
147    }
148
149    /// Prefix scan: find all entries where key starts with the given prefix.
150    ///
151    /// Returns a vector of (key, values) pairs in sorted order.
152    pub fn prefix_scan(&self, prefix: &[u8]) -> crate::Result<Vec<(Vec<u8>, Vec<u64>)>> {
153        let results: Vec<_> = self
154            .tree
155            .range(prefix.to_vec()..)
156            .take_while(|(k, _)| k.starts_with(prefix))
157            .map(|(k, v)| (k.clone(), v.clone()))
158            .collect();
159
160        Ok(results)
161    }
162
163    /// Get the minimum key in the index, if any.
164    pub fn min_key(&self) -> Option<&[u8]> {
165        self.tree.keys().next().map(|k| k.as_slice())
166    }
167
168    /// Get the maximum key in the index, if any.
169    pub fn max_key(&self) -> Option<&[u8]> {
170        self.tree.keys().next_back().map(|k| k.as_slice())
171    }
172
173    /// Iterate over all entries in sorted order.
174    pub fn iter(&self) -> impl Iterator<Item = (&[u8], &[u64])> {
175        self.tree.iter().map(|(k, v)| (k.as_slice(), v.as_slice()))
176    }
177}
178
179impl Default for BTreeIndex {
180    fn default() -> Self {
181        Self::new()
182    }
183}
184
185impl Index for BTreeIndex {
186    fn insert(&mut self, key: &[u8], value: u64) -> crate::Result<()> {
187        self.tree.entry(key.to_vec()).or_default().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.entry(key.to_vec()).or_default().push(value);
302        self.entry_count += 1;
303        Ok(())
304    }
305
306    fn find(&self, key: &[u8]) -> crate::Result<Vec<u64>> {
307        Ok(self.map.get(key).cloned().unwrap_or_default())
308    }
309
310    fn remove(&mut self, key: &[u8]) -> crate::Result<bool> {
311        if let Some(values) = self.map.remove(key) {
312            self.entry_count -= values.len();
313            Ok(true)
314        } else {
315            Ok(false)
316        }
317    }
318
319    fn len(&self) -> usize {
320        self.entry_count
321    }
322
323    fn clear(&mut self) {
324        self.map.clear();
325        self.entry_count = 0;
326    }
327
328    fn index_type(&self) -> IndexType {
329        IndexType::Hash
330    }
331}
332
333// ============================================================================
334// Index Manager
335// ============================================================================
336
337/// Manages multiple indexes for a database.
338///
339/// The IndexManager provides a centralized way to create, access, and manage
340/// indexes across the database. It supports both B-Tree and Hash indexes.
341///
342/// ## Example
343///
344/// ```rust
345/// use rustlite_core::index::{IndexManager, IndexType};
346///
347/// let mut manager = IndexManager::new();
348///
349/// // Create indexes
350/// manager.create_index("users_by_id", IndexType::Hash).unwrap();
351/// manager.create_index("users_by_name", IndexType::BTree).unwrap();
352///
353/// // Use indexes
354/// manager.insert("users_by_id", b"user:1", 100).unwrap();
355/// manager.insert("users_by_name", b"alice", 100).unwrap();
356/// ```
357pub struct IndexManager {
358    /// Named indexes
359    indexes: HashMap<String, Box<dyn Index>>,
360}
361
362impl IndexManager {
363    /// Create a new empty index manager.
364    pub fn new() -> Self {
365        Self {
366            indexes: HashMap::new(),
367        }
368    }
369
370    /// Create a new index with the given name and type.
371    pub fn create_index(&mut self, name: &str, index_type: IndexType) -> crate::Result<()> {
372        if self.indexes.contains_key(name) {
373            return Err(crate::Error::InvalidOperation(format!(
374                "Index '{}' already exists",
375                name
376            )));
377        }
378
379        let index: Box<dyn Index> = match index_type {
380            IndexType::BTree => Box::new(BTreeIndex::new()),
381            IndexType::Hash => Box::new(HashIndex::new()),
382            IndexType::FullText => {
383                return Err(crate::Error::InvalidOperation(
384                    "FullText index not yet implemented".to_string(),
385                ))
386            }
387        };
388
389        self.indexes.insert(name.to_string(), index);
390        Ok(())
391    }
392
393    /// Drop an index by name.
394    pub fn drop_index(&mut self, name: &str) -> crate::Result<bool> {
395        Ok(self.indexes.remove(name).is_some())
396    }
397
398    /// Get a reference to an index by name.
399    pub fn get_index(&self, name: &str) -> Option<&dyn Index> {
400        self.indexes.get(name).map(|b| b.as_ref())
401    }
402
403    /// Get a mutable reference to an index by name.
404    pub fn get_index_mut(&mut self, name: &str) -> Option<&mut (dyn Index + 'static)> {
405        self.indexes.get_mut(name).map(|b| b.as_mut())
406    }
407
408    /// Insert a key-value pair into a named index.
409    pub fn insert(&mut self, name: &str, key: &[u8], value: u64) -> crate::Result<()> {
410        let index = self.indexes.get_mut(name).ok_or(crate::Error::NotFound)?;
411        index.insert(key, value)
412    }
413
414    /// Find values in a named index.
415    pub fn find(&self, name: &str, key: &[u8]) -> crate::Result<Vec<u64>> {
416        let index = self.indexes.get(name).ok_or(crate::Error::NotFound)?;
417        index.find(key)
418    }
419
420    /// Remove a key from a named index.
421    pub fn remove(&mut self, name: &str, key: &[u8]) -> crate::Result<bool> {
422        let index = self.indexes.get_mut(name).ok_or(crate::Error::NotFound)?;
423        index.remove(key)
424    }
425
426    /// List all index names.
427    pub fn list_indexes(&self) -> Vec<&str> {
428        self.indexes.keys().map(|s| s.as_str()).collect()
429    }
430
431    /// Get information about all indexes.
432    pub fn index_info(&self) -> Vec<IndexInfo> {
433        self.indexes
434            .iter()
435            .map(|(name, index)| IndexInfo {
436                name: name.clone(),
437                index_type: index.index_type(),
438                entry_count: index.len(),
439            })
440            .collect()
441    }
442}
443
444impl Default for IndexManager {
445    fn default() -> Self {
446        Self::new()
447    }
448}
449
450/// Information about an index.
451#[derive(Debug, Clone)]
452pub struct IndexInfo {
453    /// The name of the index.
454    pub name: String,
455    /// The type of the index.
456    pub index_type: IndexType,
457    /// The number of entries in the index.
458    pub entry_count: usize,
459}
460
461// ============================================================================
462// Tests
463// ============================================================================
464
465#[cfg(test)]
466mod tests {
467    use super::*;
468
469    #[test]
470    fn test_btree_index_basic_operations() {
471        let mut index = BTreeIndex::new();
472
473        // Insert
474        index.insert(b"key1", 100).unwrap();
475        index.insert(b"key2", 200).unwrap();
476        index.insert(b"key1", 101).unwrap(); // Duplicate key with different value
477
478        // Find
479        assert_eq!(index.find(b"key1").unwrap(), vec![100, 101]);
480        assert_eq!(index.find(b"key2").unwrap(), vec![200]);
481        assert!(index.find(b"key3").unwrap().is_empty());
482
483        // Length
484        assert_eq!(index.len(), 3);
485
486        // Remove
487        assert!(index.remove(b"key1").unwrap());
488        assert!(!index.remove(b"key1").unwrap());
489        assert_eq!(index.len(), 1);
490    }
491
492    #[test]
493    fn test_btree_index_range_query() {
494        let mut index = BTreeIndex::new();
495
496        index.insert(b"a", 1).unwrap();
497        index.insert(b"b", 2).unwrap();
498        index.insert(b"c", 3).unwrap();
499        index.insert(b"d", 4).unwrap();
500        index.insert(b"e", 5).unwrap();
501
502        let range = index.range(b"b", b"d").unwrap();
503        assert_eq!(range.len(), 3);
504        assert_eq!(range[0].0, b"b");
505        assert_eq!(range[1].0, b"c");
506        assert_eq!(range[2].0, b"d");
507    }
508
509    #[test]
510    fn test_btree_index_prefix_scan() {
511        let mut index = BTreeIndex::new();
512
513        index.insert(b"user:001", 1).unwrap();
514        index.insert(b"user:002", 2).unwrap();
515        index.insert(b"user:003", 3).unwrap();
516        index.insert(b"order:001", 10).unwrap();
517        index.insert(b"order:002", 20).unwrap();
518
519        let users = index.prefix_scan(b"user:").unwrap();
520        assert_eq!(users.len(), 3);
521
522        let orders = index.prefix_scan(b"order:").unwrap();
523        assert_eq!(orders.len(), 2);
524    }
525
526    #[test]
527    fn test_btree_index_min_max() {
528        let mut index = BTreeIndex::new();
529
530        assert!(index.min_key().is_none());
531        assert!(index.max_key().is_none());
532
533        index.insert(b"middle", 2).unwrap();
534        index.insert(b"first", 1).unwrap();
535        index.insert(b"last", 3).unwrap();
536
537        assert_eq!(index.min_key(), Some(b"first".as_slice()));
538        assert_eq!(index.max_key(), Some(b"middle".as_slice()));
539    }
540
541    #[test]
542    fn test_hash_index_basic_operations() {
543        let mut index = HashIndex::new();
544
545        // Insert
546        index.insert(b"session:abc", 100).unwrap();
547        index.insert(b"session:def", 200).unwrap();
548        index.insert(b"session:abc", 101).unwrap();
549
550        // Find
551        assert_eq!(index.find(b"session:abc").unwrap(), vec![100, 101]);
552        assert_eq!(index.find(b"session:def").unwrap(), vec![200]);
553        assert!(index.find(b"session:xyz").unwrap().is_empty());
554
555        // Contains
556        assert!(index.contains_key(b"session:abc"));
557        assert!(!index.contains_key(b"session:xyz"));
558
559        // Length
560        assert_eq!(index.len(), 3);
561        assert_eq!(index.key_count(), 2);
562    }
563
564    #[test]
565    fn test_hash_index_with_capacity() {
566        let index = HashIndex::with_capacity(100);
567        assert!(index.is_empty());
568    }
569
570    #[test]
571    fn test_index_manager() {
572        let mut manager = IndexManager::new();
573
574        // Create indexes
575        manager.create_index("users", IndexType::Hash).unwrap();
576        manager.create_index("names", IndexType::BTree).unwrap();
577
578        // Duplicate name should fail
579        assert!(manager.create_index("users", IndexType::Hash).is_err());
580
581        // Insert into indexes
582        manager.insert("users", b"user:1", 100).unwrap();
583        manager.insert("names", b"alice", 100).unwrap();
584        manager.insert("names", b"bob", 101).unwrap();
585
586        // Find
587        assert_eq!(manager.find("users", b"user:1").unwrap(), vec![100]);
588        assert_eq!(manager.find("names", b"alice").unwrap(), vec![100]);
589
590        // List indexes
591        let names = manager.list_indexes();
592        assert_eq!(names.len(), 2);
593
594        // Index info
595        let info = manager.index_info();
596        assert_eq!(info.len(), 2);
597
598        // Drop index
599        assert!(manager.drop_index("users").unwrap());
600        assert!(!manager.drop_index("users").unwrap());
601        assert_eq!(manager.list_indexes().len(), 1);
602    }
603
604    #[test]
605    fn test_index_clear() {
606        let mut btree = BTreeIndex::new();
607        let mut hash = HashIndex::new();
608
609        btree.insert(b"key", 1).unwrap();
610        hash.insert(b"key", 1).unwrap();
611
612        assert!(!btree.is_empty());
613        assert!(!hash.is_empty());
614
615        btree.clear();
616        hash.clear();
617
618        assert!(btree.is_empty());
619        assert!(hash.is_empty());
620    }
621}
rustlite_core/index.rs

rustlite_core/
index.rs
