Hi!
> 14 марта 2019 г., в 0:18, Heikki Linnakangas <hlinnaka@iki.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
distributionof 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
issuesin 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
performantversions for main memory. Like AVL-tree and RB-tree.
Brest regards, Andrey Borodin.
[0] https://github.com/RoaringBitmap/CRoaring