roaring-rs

roaring-rs is a pure-Rust implementation of Roaring bitmaps, a compressed bitset data structure that combines the speed of uncompressed bitmaps with the memory efficiency of compression. It provides RoaringBitmap for dense sets of 32-bit integers and RoaringTreemap for 64-bit values, exposing fast set operations such as union, intersection, difference, rank, and select.

Widely used as the indexing backbone of search engines and databases, Roaring bitmaps adaptively store integer sets in the most efficient container for their density. The crate supports no_std environments, optional serde serialization, and an experimental SIMD feature, making it suitable for everything from embedded contexts to high-throughput analytics.

What You Get

• RoaringBitmap for compressed sets of u32 values with full set-algebra operations
• RoaringTreemap for u64 values, built as a BTreeMap of RoaringBitmaps
• Portable, versioned serialization compatible with the cross-language Roaring format
• Optional serde support and an experimental portable-SIMD acceleration feature
• no_std compatibility for constrained and embedded environments

Common Use Cases

• Building inverted indexes and posting lists for full-text search engines
• Representing large sets of document or row IDs in databases and analytics engines
• Fast set intersection and union for faceted filtering and boolean queries
• Memory-efficient bitset storage in data pipelines processing millions of integers

Under The Hood

Architecture - The crate splits into two top-level modules, bitmap and treemap. A RoaringBitmap holds a sorted vector of containers keyed by the high 16 bits of each u32; each container (in src/bitmap/container.rs and store) chooses an array, bitmap, or run representation based on cardinality, and set operations dispatch per-container. RoaringTreemap layers a BTreeMap<u32, RoaringBitmap> on top to reach u64 values.

Tech Stack - Pure Rust (edition 2021, MSRV 1.90) with zero required runtime dependencies; optional bytemuck and byteorder back the std serialization path, serde is feature-gated, and proptest/serde_json/postcard are dev-only. Built and benchmarked with Cargo and Criterion.

Code Quality - The crate warns on missing_docs and denies unsafe-op lints, and is backed by an extensive test suite: dozens of integration tests under roaring/tests, property-based tests via proptest, fuzz targets, and serialization fixtures verified against the cross-language format.

API Design - The public surface mirrors Rust’s standard collection idioms (insert, contains, iter, bit-operator overloads for set algebra), so it feels familiar with minimal boilerplate. Feature flags keep the default build lean while exposing serde and SIMD for advanced users.