Categories: Track most used categories

We could track categories usage so we can suggest most used ones for folks. 

Do we need to track only categories of existing records? 
What to do on record's category change?
When record is deleted? 