brotherhood_of_LAN - 4:28 pm on Mar 4, 2011 (gmt 0)

- Are you using InnoDB?
- Do you use a Primary KEY?
- Is the PK numeric and inserted in ascending order
- Are these the records being deleted?

If your answer is yes to all then you don't have to do anything as InnoDB fills up the gap and frees the disk space (using innodb-file-per-table). I'm not sure what MyISAM does in these cases.

If you have a column that you mainly query by and is in an ascending order (like time) then I'd check out InnoDB as PK searches are very quick with it.

If the records you delete are at the start of the table, you might want to consider partitioning so you can 'chop off' the older values by removing older partitions and recover the space.

Either/or, try running OPTIMIZE TABLE and if its quick enough you could periodically use that on your table.

Hopefully that gives you some ideas.