I've disovered a weird issue with a MySQL table where new records are occassionally not written at the end of the table.

The table is user registration data, 25 columns (all less than 100 characters) and there's less than 900 rows. It's been live and accepting user data for over 5 years without problems.

Today, I noticed that some new rows weren't being written at the end of the table: the table auto-increments an "id" column and when I inserted what should have been row 865, it wrote the data okay, although it and two other records entered in the past 2 days appear between records 840 and 841. The data reads okay, my scripts execute as always. I went through the entire table and discovered this had happened twice before: once 18 months ago (row 589 ended up between 550 and 551) and then two months ago with another row being inserted between two records from months earlier. The row data of the out of sequence rows is normal compared to all other rows.

My concern is that the rows not being written at the end of the table maybe a symptom of a larger problem. Has anyone ever encountered this issue, know what may cause it, and if there any remedy?

Thanks.

David