Re: Sparse bit set data structure

Hi!

> 14 марта 2019 г., в 0:18, Heikki Linnakangas <hlinnaka(at)iki(dot)fi> написал(а):
> <0001-Add-SparseBitset-to-hold-a-large-set-of-64-bit-ints-.patch><0002-Andrey-Borodin-s-test_blockset-tool-adapted-for-Spar.patch>

That is very interesting idea. Basically, B-tree and radix tree is a tradeoff between space and time.

In general, lookup into radix tree will touch less CPU cache lines.
In this terms Bitmapset is on most performant and memory-wasteful side: lookup into Bitmapset is always 1 cache line.
Performance of radix tree can be good in case of skewed distribution, while B-tree will be OK on uniform. I think that distribution of GiST inner pages is uniform, distribution of empty leafs is... I have no idea, let's consider uniform too.

I'd review this data structure ASAP. I just need to understand: do we aim to v12 or v13? (I did not solve concurrency issues in GiST VACUUM yet, but will fix them at weekend)

Also, maybe we should consider using RoaringBitmaps? [0]
As a side not I would add that while balanced trees are widely used for operations on external memory, there are more performant versions for main memory. Like AVL-tree and RB-tree.

Brest regards, Andrey Borodin.

[0] https://github.com/RoaringBitmap/CRoaring