When I was a Windows user, I used a small program (named Second Copy) that was responsible for doing backups to my external Hard Disk.
But Second Copy had a special way to do its work. He reviewed the computer files one by one and compared with the backup that was on the external hard disk, so he noticed which files had been eliminated, changed or added. And then, he just synchronized the hard disks, without have to copy all the files again ... he just copied the files that were new to the external HD, deleted the files that had been deleted in the local hd, and replaced the files that had been changed.
Does anyone know any software that does this under linux?