A ver, como es eso que no tienes un indice en la tabla, supongo que tienes un campo ID, te recomiendo que al eliminar un registro no lo borres de la tabla sino que lo desactives usando un campo digamos llamado enabled,
O sino deberias tener un campo que sirva como referencia para lograr lo que tu deseas, ¿no tienes un campo de alta del registro? o similar,
La query para obtener los ultimos 5 seria algo asi
Código PHP:
SELECT * FROM tabla ORDER BY date DESC LIMIT 5
debes ordenarlo en función de un campo cronológico