Directory attributes are provided so that the time for creating an incremental backup of a file system by a scan of the file system tree is proportional generally to the number of files that change between backups instead of the number of files in the file system. A tree modification attribute indicates whether or not any file in a directory tree has changed since the last backup. If no file has changed in the directory tree, then the entire tree is skipped during the scan for changed files. In addition, a list is compiled of the files in the directory that represent branches having at least one changed file, so that the list is scanned instead of the directory entries. When a file is changed for the first time since the last backup, the file is queued so that the directory attributes are updated in a background process.