Hi! > 5 авг. 2018 г., в 16:18, Heikki Linnakangas <hlinn...@iki.fi> написал(а): > > On 31/07/18 23:06, Andrey Borodin wrote: >>> On a typical GiST index, what's the ratio of leaf vs. internal >>> pages? Perhaps an array would indeed be better. > > >> Typical GiST has around 200 tuples per internal page. I've switched >> to List since it's more efficient than bitmap. > > Hmm. A ListCell is 16 bytes, plus the AllocChunk header, 16 bytes. 32 > bytes per internal page in total, while a bitmap consumes one bit per page, > leaf or internal. If I'm doing > my math right, assuming the ratio of leaf pages vs internal pages is > 1:200, a List actually consumes more memory than a bitmap; 256 bits per > internal page, vs. 200 bits. An array, with 4 bytes per block number, > would be the winner here. We do not know size of this array beforehand. I can implement normal ArrayList though (with repallocing array) or linked list of chunks. Or anything from data structures zoo. Or just stick with bitmap (my preferred way). > >> But I have to note that default growth strategy of Bitmap is not good: we >> will be repallocing byte by byte. > > True, that repallocing seems bad. You could force it to be pre-allocated > by setting the last bit. Or add a function to explicitly enlarge the bitmap. OK, I'll think of proper resize function (ensure capacity, to be precise).
Best regards, Andrey Borodin.
