Depends on the storage engine afair, but both innodb an myisam have either index or global metadata based solution for this. I think in myisam its an estimste if you use count(*) so you need to use count(id) to get an exact value. This is all well documented
count(*) doesn't do full table scan as it's not tied to specific data. It has special handling logic. The only case where it might have to do a full table scan is if you try to count() on a specific (nullable?) column without an index.