Efficient database indexes form the backbone of modern database systems, and Rust’s powerful features make it an excellent choice for implementing high-performance indexing structures. I’ll share seven essential techniques for creating cache-efficient database indexes in Rust.

Custom B-Tree implementations serve as the foundation for many database indexes. The key to cache efficiency lies in memory alignment and optimal node sizing:

#[repr(align(64))]
struct BTreeNode<K, V> {
    keys: Vec<K>,
    values: Vec<V>,
    children: Vec<Option<Box<BTreeNode<K, V>>>>,
    size: usize,
}

impl<K: Ord, V> BTreeNode<K, V> {
    fn new() -> Self {
        BTreeNode {
            keys: Vec::with_capacity(NODE_SIZE),
            values: Vec::with_capacity(NODE_SIZE),
            children: Vec::with_capacity(NODE_SIZE + 1),
            size: 0,
        }
    }
}

Prefix compression significantly reduces memory usage when dealing with string keys. This technique is particularly effective for indexes with similar key prefixes:

struct CompressedString {
    shared_prefix: Arc<[u8]>,
    suffix: Vec<u8>,
}

impl CompressedString {
    fn compress(strings: &[String]) -> Vec<CompressedString> {
        let prefix = find_common_prefix(strings);
        strings
            .iter()
            .map(|s| CompressedString {
                shared_prefix: Arc::from(prefix.as_bytes()),
                suffix: s[prefix.len()..].as_bytes().to_vec(),
            })
            .collect()
    }
}

Memory-mapped files provide efficient access to disk-based indexes. This approach leverages the operating system’s virtual memory system:

use memmap2::MmapMut;

struct MappedIndex {
    mmap: MmapMut,
    page_size: usize,
}

impl MappedIndex {
    fn new(path: &Path, size: usize) -> io::Result<Self> {
        let file = OpenOptions::new()
            .read(true)
            .write(true)
            .create(true)
            .open(path)?;
        file.set_len(size as u64)?;
        
        Ok(MappedIndex {
            mmap: unsafe { MmapMut::map_mut(&file)? },
            page_size: page_size::get(),
        })
    }
}

Page management ensures efficient disk I/O operations by maintaining properly aligned memory pages:

struct Page {
    data: [u8; PAGE_SIZE],
    id: PageId,
    dirty: bool,
}

struct PageManager {
    pages: HashMap<PageId, Arc<RwLock<Page>>>,
    free_list: Vec<PageId>,
}

impl PageManager {
    fn allocate_page(&mut self) -> PageId {
        self.free_list.pop().unwrap_or_else(|| {
            let id = PageId(self.pages.len());
            let page = Arc::new(RwLock::new(Page::new(id)));
            self.pages.insert(id, page);
            id
        })
    }
}

Bloom filters provide quick negative lookups, preventing unnecessary disk access:

struct BloomFilter {
    bits: BitVec,
    hash_count: usize,
    item_count: usize,
}

impl BloomFilter {
    fn new(expected_items: usize, false_positive_rate: f64) -> Self {
        let bit_count = optimal_bits(expected_items, false_positive_rate);
        let hash_count = optimal_hashes(bit_count, expected_items);
        
        BloomFilter {
            bits: BitVec::from_elem(bit_count, false),
            hash_count,
            item_count: 0,
        }
    }
    
    fn insert<T: Hash>(&mut self, item: &T) {
        for i in 0..self.hash_count {
            let index = self.hash_at(item, i);
            self.bits.set(index, true);
        }
        self.item_count += 1;
    }
}

Buffer pools cache frequently accessed pages in memory, reducing disk I/O:

struct BufferPool {
    pages: LruCache<PageId, Arc<RwLock<Page>>>,
    max_size: usize,
}

impl BufferPool {
    fn get_page(&mut self, id: PageId) -> io::Result<Arc<RwLock<Page>>> {
        if let Some(page) = self.pages.get(&id) {
            return Ok(Arc::clone(page));
        }
        
        let page = self.load_page_from_disk(id)?;
        self.pages.put(id, Arc::clone(&page));
        Ok(page)
    }
}

Skip lists offer an alternative to B-trees with simpler implementation and good cache behavior:

struct SkipNode<K, V> {
    key: K,
    value: V,
    forward: Vec<Option<Arc<RwLock<SkipNode<K, V>>>>>,
}

struct SkipList<K, V> {
    head: Arc<RwLock<SkipNode<K, V>>>,
    max_level: usize,
    size: usize,
}

impl<K: Ord, V> SkipList<K, V> {
    fn insert(&mut self, key: K, value: V) {
        let level = random_level(self.max_level);
        let new_node = Arc::new(RwLock::new(SkipNode {
            key,
            value,
            forward: vec![None; level + 1],
        }));
        
        let mut current = Arc::clone(&self.head);
        for i in (0..=level).rev() {
            while let Some(next) = &current.read().unwrap().forward[i] {
                if next.read().unwrap().key >= key {
                    break;
                }
                current = Arc::clone(next);
            }
            let mut node = current.write().unwrap();
            node.forward[i] = Some(Arc::clone(&new_node));
        }
        self.size += 1;
    }
}

These techniques form a comprehensive toolkit for building high-performance database indexes in Rust. The combination of memory alignment, compression, efficient page management, and intelligent caching creates indexes that make optimal use of CPU caches and memory hierarchies.

I’ve found that implementing these patterns requires careful attention to memory layout and access patterns. The key is to minimize cache misses and reduce memory overhead while maintaining the index’s structural integrity and performance characteristics.

Remember to benchmark your specific use case, as the effectiveness of each technique depends on your data patterns and access requirements. The code examples provided serve as a starting point for building robust, cache-efficient database indexes in Rust.