Quando um arquivo é excluído no seu computador, somente um ponteiro para o arquivo é excluído . Se sim, por que demora tanto para recuperá-lo? Eu coincidentemente formato meu pendrive, que costumava ter cerca de 500 GB de dados. O processo de formatação leva aproximadamente um minuto, mas o processo de recuperação me leva uma noite (acho que deve ser mais porque depois de uma hora, o processo atinge apenas 2%, o que significa que levará 50 horas para atingir 100%). Eu entendo que ele precisa varrer a unidade inteira porque você não tem o índice, mas mesmo copiar todos esses dados não leva tanto tempo.
Como Ramhound apontado no comentário, os arquivos podem se tornar fragmentados, o que significa que eles não ocupam um espaço contíguo em um meio. Quando você exclui o índice para um arquivo, o programa de recuperação precisa agora examinar toda a mídia para encontrar todas as peças para reuni-las. Isto é apenas para um arquivo. Imagine quanto tempo esse processo é para cada arquivo.
Um arquivo pode estar espalhado em pedaços no seu disco. Então, quando você exclui o arquivo, essas partes ainda estão lá, mas são órfãs da entrada em uma tabela que permite encontrá-las. Para "desfazer a exclusão" do arquivo, é necessário verificar todo o disco.
Quando você formata um disco, está apagando uma tabela, não apagando todo o disco. Após o formato, os arquivos ainda estão lá.