"MySQL tables, including MyISAM and InnoDB, two of the most
common types, experience fragmentation as data is inserted and
deleted randomly. Fragmentation can leave large holes in your
table, blocks which must be read when scanning the table.
Optimizing your table can therefore make full table scans and range
scans more efficient.
"Fragmentation - an example
"MySQL has quite a few different storage engines to store data
in tables. Whenever MySQL deletes rows from your table, the space
left behind is then empty. Over time with a lot of DELETEs, this
space can grow larger than the used space in your table. When MySQL
goes to scan that data, it scans to the high water mark of the
table, that is the highest point at which data has been added. If
new inserts occur, MySQL will try to use that space, but
nevertheless gaps will persist."