Why not just use a set or database index if disk and CPU are cheap?
Sets and indices work at application level but require memory (O(n) pointers) and serialize lookups through the software stack, causing context switches and cache misses. A Bloom filter in RAM answers with a single CPU op per hash function—millions per second with zero I/O, making it ideal for high-frequency checks like username uniqueness.
Answered in
Bloom Filters: The One-Way Membership TestA probabilistic data structure: zero false negatives, tunable false positives. Check membership in RAM with bits instead of database queries.
Read the full analysisOther questions this article answers
More system design questions
- Why does an index's internal data structure matter if it all ends up 'faster than a scan'?
- Why is disk I/O the thing index structures are actually optimizing for?
- Why can't a hash index handle range queries?
- What makes a bitmap index different from a B-tree, and when is it better?
- Why do B-trees stay balanced automatically as data is inserted?
- Why does a database need an index at all — why can't it just scan the table?
- When is a hash index better than a B-tree index?
- What is a composite index and why does column order matter?
Every answer on Crashtech is written by the editor of the article it comes from — never auto-summarised. Browse all answers or the System Design beat.