Skip to content
Tutorials Center
My learning

Topics

Lesson 56 of 79 ยท Storage and Indexing

Bitmap, Composite, Partial and LSM Indexes

Go beyond the plain B+ tree: composite index column order, partial and expression indexes in SQLite, bitmap and R-tree indexes, and LSM trees with a tiny Python LSM.

The ordinary single-column B+ tree index solves many problems, and a surprising number of production systems use nothing else. But real workloads ask for more: filters on several columns at once, indexes for only a small slice of a big table, indexes on computed values, columns with only a handful of distinct values, geographic data, and write rates that a B+ tree cannot keep up with.

This lesson tours the main variants. Composite, partial and expression indexes work in SQLite, so you can verify them with EXPLAIN QUERY PLAN in the browser. Bitmap indexes and LSM trees are shown with small Python models, and R-trees are described only in text, because the R-tree module is not part of the in-browser SQLite build.

Query-shaped indexes

Composite Several columns in one key.
Partial Only the rows that matter.
Expression An index on lower(email).
1 / 2

Composite indexes and the leftmost prefix

A composite (multi-column) index sorts its entries by the first column, then, within equal values, by the second, and so on, exactly like a phone book sorted by last name and then first name. That sorted order decides which queries it can serve:

  • It can search on the leftmost prefix: the first column, the first two columns, and so on.
  • After a run of equality tests, it can apply one range on the next column.
  • It cannot jump to the second column alone. A phone book is no help for finding everyone called "Maria" regardless of last name.

The first TryIt creates an index on (customer, status, total) and checks which queries can use it.

SQL Leftmost prefix of a composite index

Press Run (or Ctrl + Enter) to see the result here.

The plans show (customer=?), (customer=? AND status=?), (customer=? AND status=? AND total>?), SCAN orders and (customer=?) for the last one: with status skipped, the index narrows down by customer and the total test is applied to each candidate row. The order of conditions inside WHERE does not matter; the optimizer rearranges them.

Choosing the column order

Put these first, in this order, as a rule of thumb:

  1. Columns tested with equality, usually the most selective first (but see the next point).
  2. The column used for a range (>, BETWEEN) or for ordering, last. Everything to the right of a range column cannot narrow the search any more.
  3. Columns only needed to cover the query (see Indexing Basics), at the very end.

An index on (a, b) also serves queries on a alone, so you rarely need both (a) and (a, b). It does not serve b alone. When both patterns are common, you need two indexes. And an index whose order also matches ORDER BY lets the engine return rows already sorted, with no extra sort step.

Partial and expression indexes

A partial index (SQLite and PostgreSQL call it that; SQL Server calls it a filtered index) holds entries only for rows that satisfy a WHERE condition. If 2% of the orders are "open" and everyone queries open orders, indexing just those rows makes the index 50 times smaller, cheaper to maintain and faster to search.

An expression index is built on a computed value instead of a raw column. It fixes the classic problem of a function applied to an indexed column: WHERE lower(email) = ... cannot use a plain index on email, because the stored values are not lowercased.

SQL Partial and expression indexes

Press Run (or Ctrl + Enter) to see the result here.

Only the first partial-index query is SEARCH orders USING INDEX idx_open_placed (placed>?); the other two are scans, because their condition does not imply status = 'open'. The plain email = ... query is a scan as well, and the lower(email) = ... query shows SEARCH orders USING INDEX idx_lower_email (<expr>=?). The matching row is order 5, whose stored address is [email protected].

The query must repeat the exact expression (or an equivalent condition for a partial index) for the optimizer to match it. A partial index is also a neat way to enforce "unique among active rows" in engines that allow CREATE UNIQUE INDEX ... WHERE.

Bitmap indexes

A bitmap index stores, for each distinct value of a column, a string of bits with one bit per row: bit i is 1 when row i has that value. It is ideal for low-cardinality columns (gender, status, country, a yes/no flag) in read-mostly analytical tables. Combining conditions is a bitwise operation on whole machine words: AND for AND, OR for OR, NOT for NOT. COUNT(*) of the result is just counting bits, and no rows are read at all.

Python A bitmap index in 25 lines

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Real bitmaps are compressed (run-length encoded), so a sparse bitmap costs little. The weakness is writes: changing one row changes bits in the bitmaps of several values, and in some engines a single update locks a large section of bitmaps. That is why bitmap indexes are common in data warehouses (Oracle, and as on-the-fly bitmaps inside PostgreSQL scans) and rare in OLTP systems. They are also poor for high-cardinality columns such as an email, where there would be as many bitmaps as rows.

R-tree indexes

A B+ tree orders values on a line. Geographic and spatial data has two or more dimensions: "all shops inside this rectangle", "the five nearest hotels". An R-tree indexes rectangles. Each node stores the minimum bounding rectangle of everything below it, rectangles of siblings may overlap, and a search descends into every child whose rectangle intersects the query area. Inserts and splits keep the tree balanced like a B-tree.

SQLite has an R-tree extension (CREATE VIRTUAL TABLE places USING rtree(id, minX, maxX, minY, maxY)) and PostgreSQL has GiST/SP-GiST indexes for the same purpose. The module is not part of the browser build that runs the examples here, so R-trees remain a read-only topic in this lesson.

LSM trees

A B+ tree updates pages in place: a random write per insert, possibly several (leaf, split, parent). For write-heavy workloads such as logging, time series and key-value stores, log-structured merge trees (LSM trees) turn random writes into sequential ones.

  1. New writes go to an in-memory sorted structure, the memtable (and to a write-ahead log for durability, see Logging and Write-Ahead Logging).
  2. When the memtable is full, it is written to disk as an immutable sorted file, an SSTable (sorted string table). Files are never modified.
  3. A read checks the memtable, then the SSTables from newest to oldest; the first hit wins. Per-file Bloom filters and sparse indexes make most misses cheap.
  4. A deletion writes a special marker, a tombstone.
  5. In the background, compaction merges SSTables, drops overwritten versions and tombstones, and keeps the number of files under control.

The tiny model below keeps three keys per memtable and shows flushes, newest-first reads, a tombstone and compaction.

Python A tiny LSM tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at get b: it returns 10, the newer value, and only two SSTables were examined. get a has to check all three tables, and a missing key such as z checks them all too: that is read amplification, the price of cheap writes. After compaction there is one table, the old b=1 and the tombstoned d are gone, and reads are cheap again. Compaction rewrites data, which is write amplification. Engines tune this trade-off with different compaction strategies. LSM trees power RocksDB, LevelDB, Cassandra, HBase and many other stores.

B+ tree LSM tree
Writes In-place, random Append and merge, sequential
Reads One path, predictable Several files, helped by Bloom filters
Space Pages ~69% full Dense, but old versions wait for compaction
Typical use OLTP relational engines Write-heavy key-value, time series

What runs live here: SQLite composite, partial and expression indexes, plus Python models of bitmaps and LSM trees. R-tree indexes and the vendor-specific bitmap, GiST and filtered-index syntax are only described.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A composite index is on (country, city, zip). Which query can NOT use it to narrow the search?

    The index is sorted by country first. Without a condition on the leftmost column, the matching entries are scattered across the whole index.
  2. 2. Why does WHERE lower(email) = 'x' ignore a plain index on email?

    An expression index on lower(email) stores the computed values and the query can search it, if it repeats the same expression.
  3. 3. For which column is a bitmap index most suitable?

    Bitmaps work best with few distinct values and analytical queries that combine many conditions using AND and OR.
  4. 4. In an LSM tree, why does a read sometimes have to check several SSTables?

    Files are immutable, so updates and deletes create new versions in newer files. Compaction later removes the stale ones.
  5. 5. What is a tombstone?

    Because SSTables cannot be edited, a delete is recorded as a new entry that shadows the older value.

Summary

  • A composite index is sorted by its first column, then the second, and so on. It serves leftmost prefixes, plus one range after equalities; put equality columns first, the range or ordering column last.
  • Partial indexes cover only rows matching a condition; expression indexes cover computed values. Queries must match the indexed condition or expression.
  • Bitmap indexes keep a bit string per value, fit low-cardinality columns in read-mostly warehouses, and combine conditions with bitwise operations.
  • R-trees index rectangles for spatial queries by storing nested bounding boxes.
  • LSM trees buffer writes in a memtable, flush immutable sorted files and compact them in the background, trading read and write amplification for fast, sequential writes.

Next: The Query Processing Pipeline.