MySQL stores a copy of the PK in every secondary index, so it can start adding up quite a bit. I agree that the overall size of 10 billion rows would dwarf that, but since you're presumably doing some decent indexing on a table of that size, index size matters more IMO.

For any RDBMS (I assume... I don't know a lot about SQL Server or Oracle), the binpacking for pages also impacts query speed for queries where there are many results.