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.
Perhaps some of the page-level Copy-on-Write databases (LMDB?) might do this, since they have to rewrite ancestor pages anyway.