Re: Performance of PostgreSQL B+-tree algorithm

Kyle Lanclos <lanclos(at)ucolick(dot)org> writes:
> Tom Lane wrote:
>> Well, that would depend on the data type being indexed, which you did
>> not specify; and if it's a variable-length type then it's really hard to
>> give a concrete answer.

> In my specific case, I have an index on (text, double). There are individual
> indexes on (text) and (double) that are of some interest, but the main
> interest is the two-column index.
> The text column in question typically does not contain values longer than
> ten characters.

>> Basically it's 4 bytes for line pointer, plus 8 bytes for index tuple
>> header, plus maxalign'ed size of the index key, divided into page size
>> (less a couple dozen bytes for page header).

> So, it is the size of the index key that varies depending on the column
> type?

Yeah. You could probably safely assume that the text column occupies at
most 16 bytes (and because of the alignment requirement for the double,
it's unlikely to be much less either). So that gives 4+8+16+8 = 36
bytes per index entry for this case, so you could expect to fit at least
220 or so entries per index page.

BTW, I'm unsure that that's a representative number in practice. The
traditional wisdom for btree indexes on changing data is that the fill
factor averages only around 2/3rds, which would mean you'd really find
maybe 150 or so entries on a typical index page. Not sure if the model
you're planning to use accounts for index slack space separately or not.

regards, tom lane