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.