It only has to count if the index doesn't store the amounts of records in the "chunks" it manages, does it? I'm pretty sure B-trees do actually store the sizes of the subtrees.
Afaik Postgres doesn't. In my exposure it'd be quite uncommon for a b-tree to store the size of a subtree; would cause more churn/writes when updating trees.
Perhaps some of the page-level Copy-on-Write databases (LMDB?) might do this, since they have to rewrite ancestor pages anyway.
