large mbox files

How are messages deleted from large mbox files, are these files completely rewritten? I can't really believe that as some are bigger than the free disk space available.