There is no such thing as an efficient record count with a table that size.
You need to maintain the count in a separate area but I caution you, doing
so in a trigger will cause a hot-spot. You will need to feed a queue table
with increment/decrement amounts and then have a separate app (service app
running on server) do the rollups.

Jason Wharton
CPS - Mesa AZ
http://www.ibobjects.com