CSE Roadmap

Specialist tier · about 2 hours · 5 parts

Part 1 of 5 · 1 min read

Why this page comes first

In this module you will

  • Explain what a Bloom filter checks, and what kind of answer it gives.
  • Explain why a Bloom filter can have false positives but never false negatives.
  • Explain what a bitmap index is, and when it beats a B+-tree.
  • Recognize the column characteristics that make a bitmap index a good fit.

The previous page on LSM-trees mentioned checking several SSTables to find a key. This page covers a structure, the Bloom filter, often used to skip that check entirely for files that cannot possibly contain the key. It also covers a second, unrelated structure suited to a very different kind of column.