[pvillano]

I thought the trick was going to be indirection.

sorted-list/bitmap/runs, in a two level tree. cool.

it's technically missing sorted compliment-list, i.e. only the items that are missing, although worst case runs only use twice as much space, so more complexity without much savings, esp. considering real workloads

performs better with sequential ids than random uuids because you use fewer pages

further research

investigating the effect of adding more layers to the tree

using additional set representations e.g. balanced tree

[kanak]

Lucene's adaptation of Roaring uses the complement idea on a block-wise basis:

https://github.com/apache/lucene/blob/84cae4f27cfd3feb3bb42d...