Честно говоря, не в курсе, как там в InnoDB. Мне нравится, как в Оракле: в табличный тейблспейс пишется только актуальная версия строки. При изменении она же и обновляется. Для каждого вектора изменений пишется запись отмены изменений (undo), которая циклично пишется в отдельный undo tablespace (или, в далёком прошлом, rollback segment). При необходимости достать старую версию строки, берём текущую и последовательно накатываем на неё undo до нужного состояния. И никакого мусора.