Garbage collection in database?
MyISAM is especially bad about garbage collection.  That is one of several reasons you really should move to InnoDB.  MyISAM will be removed in the next release.

MyISAM, more so than InnoDB, can sometimes benefit from OPTIMIZE TABLE.  That is the command for freeing up wasted space and otherwise defragmenting a table.  It is tedious and takes a long time (depending on size of table).

As already pointed out, InnoDB, with FOREIGN KEYs, could take care of the deleting.

I would prefer to have an API that handles the delete -- plus any cleanup that might be needed.  Built into that API could be


Cascading delete, or
Application code to do the delete(s), or
A stored procedure to do the delete(s).
A cron job "because it could take a long time to do all the deleted".


A cron job?  -- Suggest you have the app copy the deleted userid into a ToBeDeleted table.  This could be done with a simple TRIGGER.  Then the cron job would select one row from that table, proceed to do deletes from various other tables (COMMITting as it goes), and finally delete from ToBeDeleted.  Rinse and Repeat.

Better yet, don't make it a cron job, make it a continually running job.  (OK, add a "keep-alive" cron job to make sure it does not vanish, especially after a reboot.)  When this continual job finds nothing to do, it sleeps for, say, a minute.  Otherwise, it runs full-tilt.