va bene MyISAM.

varchar occupa solo lo spazio richiesto + un paio di byte.

Per i record totali se fai una query "SELECT COUNT()... e' superveloce... infatti legge direttamente il numero dei record presenti nella chiave primaria. Non li conta insomma...