Choose a bit-level structure
A structure is read far more often than it changes, say row-ID lists in an index, postings for a column value, or offsets into a file. It could be packed into a fraction of its size and still be queried without decompressing it. Smaller is not automatically better, though: packing makes updates expensive and code more complex. Is it worth it here, and which representation fits?
You will end with whether compact encoding is worth it here, and which representation to use.
Decide
Is the structure read-mostly, and rebuilt anyway rather than updated in place?
Why
Several packed values share one machine word, so any update rewrites the word, and neighbouring updates fight over cache lines. Packed structures are therefore built once and replaced, with new changes kept in a small side structure until the next rebuild.
Does shrinking it change where it lives?
It would now fit in memory instead of on disk, or in CPU cache instead of memory.
Why
If the structure stays in the same tier, compactness buys only its I/O ratio, and the simpler structure usually wins. If it moves up a tier, the gain is an order of magnitude or more, worth almost any complexity.
Do queries combine sets (AND, OR over rows), or look up single positions?
Combine setsCompressed bitmaps (Roaring)
Single positionsGo to 4
Why
Bitmaps turn "rows matching A and B" into word-wide bit operations. Point access into packed data needs a way to jump to the i-th item, which is what rank/select directories provide.
Are the values sorted and increasing?
Row IDs in a posting list, offsets into a file.
Why
For increasing values, Elias-Fano gets close to the minimum possible size and still supports random access. Delta encoding plus variable-length integers gives up both space and random access by comparison.
Where you can land
Keep the simpler structure
Use it when compacting it would not move it to a faster tier.
What it costs: some space you could have saved.
Compressed bitmaps (Roaring)
Use it when queries combine sets of rows.
Roaring picks a representation per block (array, bitmap or runs) to fit the density. What it costs: branchy code, and implementation complexity.
Elias-Fano
Use it when the values are sorted and increasing.
What it costs: read-only; any change means a rebuild.
Packed array with rank/select
Use it when you need point access into packed values that are not monotone.
What it costs: a small extra directory (o(n) bits) and a cache-line access per lookup.
If you want min/max statistics to prune blocks
Measure correlation before adding metadata
Per-block min/max statistics (zone maps) skip blocks only if the column is correlated with the physical order of rows. Measure it: average block range ÷ the column's full range. If it is near 1: no amount of statistics will prune; sort or cluster the data first. Watch for sentinel values (9999-12-31 for "no end date"): one in a block widens its range to everything.