Hacker News Reader

Can someone please explain this to me

> For efficiency reasons it is common not to index every single key of the sorted records, rather only the key of every n-th record, i.e., the first key of a page. [1] This helps to significantly reduce the number of keys the index has to store without any significant performance penalty

Is this true of B-Tree indexes in Postgres, for example?

View on HN

This only applies to indexes over a pre-sorted structure. For unordered, PG has something vaguely similar in the form of BRIN indexes, but really they're totally different tricks

I'd say this is a generally misleading statement, but if you like it is right in some context.

In particular, one could argue that it is true for clustered indexes (e.g. in SQL Server or MySQL/InnoDB). In that case the table is actually in an ordered fashion and happens to be identical to the leaf-node-level of the index. However, if you argue that this level doesn't belong to the index but is just the payload, the level above the leaf nodes is as they say: it has one pointer per page.

Reply on news.ycombinator.com