File Fragmentation

The file system divides each file into one or more storage clusters. For a contiguous file, the clusters are sequential (cluster 100, then 101, then 102, then 103, etc.). For a fragmented file, the clusters are scattered: cluster 100, then 247, then 891, then 1456, then 2103. Both arrangements are valid; both store the same file data; both are accessed transparently by normal file operations.¹

A concrete example

Consider a 20 KB JPEG image saved to an NTFS partition with 4 KB clusters. The image needs five clusters to store its data. Two scenarios:

• Contiguous: the image lives in clusters 1000, 1001, 1002, 1003, 1004. The file system records “JPEG starts at cluster 1000, length 5 clusters.”
• Fragmented: the image lives in clusters 1000, 1547, 1548, 4203, 4204. The file system records the cluster list explicitly: “JPEG occupies clusters 1000, 1547, 1548, 4203, 4204.”

Reading the image from the contiguous arrangement requires one read operation that spans five sequential clusters. Reading the fragmented version requires three read operations (one for cluster 1000, one for clusters 1547-1548, one for clusters 4203-4204) and seeks between them. The user sees an identical JPEG; the difference is invisible at the application level.

External vs internal fragmentation

The fragmentation discussed here is “external fragmentation”: a file’s clusters are scattered across the disk. There’s a separate concept of “internal fragmentation,” which is the wasted space within an allocated cluster when the file’s size doesn’t fill it. Internal fragmentation is what data recovery literature usually calls slack space. The two concepts are unrelated despite the shared “fragmentation” word; this entry covers external fragmentation, which is the recovery-significant phenomenon.

How file systems track fragmented files

Each file system has its own mechanism for recording where a file’s clusters live:

• NTFS uses data runs in the MFT record. A data run encodes a sequence of contiguous clusters as (start, length) pairs; a fragmented file has multiple data runs in its MFT record.
• FAT32 uses cluster chains in the File Allocation Table. Each cluster’s FAT entry contains the number of the next cluster; fragmented files have non-sequential cluster numbers in their chains.
• ext4 uses extents: contiguous ranges of clusters represented compactly. A fragmented file has multiple extents.
• APFS uses extents similar to ext4, with copy-on-write semantics that further complicate fragmentation behavior.

For normal file access, the file system reads its tracking metadata, follows the cluster references, and presents the file to the application as a contiguous stream of bytes. The fragmentation is invisible above the file system layer.

Fragmentation isn’t a defect; it’s a natural consequence of how file systems allocate space over time. Several patterns produce fragmentation in normal use.²

File growth after creation

When a file is first written, the file system allocates clusters for the file’s initial size. If the user later appends to the file (saving more data to a document, adding records to a database), the file system needs to allocate additional clusters. If contiguous clusters aren’t available adjacent to the file’s existing clusters, the file system allocates from elsewhere on the disk, fragmenting the file. Database files, virtual machine disk images, log files that grow over time, and email mailboxes are particularly prone to this pattern.

Fill-and-delete cycles

Normal file system use creates and deletes files continuously. Each delete leaves a gap of available space; each new file gets allocated from the available pool. Over time, the available space becomes a patchwork of small gaps rather than large contiguous regions. New files have to fragment to fit into the available patchwork; the longer the drive has been in use, the worse the fragmentation pattern.

Allocation algorithm choices

File systems make different allocation decisions to balance fragmentation against performance:

• First-fit: allocates from the first available region large enough. Fast but produces heavy fragmentation over time.
• Best-fit: allocates from the smallest available region that fits. Slower but reduces overall fragmentation.
• Delayed allocation (used in ext4): defers cluster assignment until the file is actually written, allowing the file system to allocate larger contiguous regions when possible. Reduces fragmentation significantly.
• Extent-based allocation (used in ext4 and APFS): allocates large contiguous ranges as a single unit, naturally producing less fragmentation than per-cluster allocation.

File types prone to heavy fragmentation

Certain file types fragment more heavily than others due to how applications use them:

• Outlook PST files: Garfinkel’s research found up to 58% of Outlook PST files in real-world drive samples were fragmented. The pattern reflects how Outlook continuously appends new mail to the PST file.
• Database files: SQL Server MDF files, MySQL InnoDB files, SQLite databases all grow incrementally as records are added.
• Virtual machine disks: VMDK, VHD, VHDX files grow as the VM uses storage; thin-provisioned disks are particularly fragmentation-prone.
• Video files: particularly when recorded directly to disk (security camera DVR systems, screen recordings); the streaming write pattern can produce highly fragmented files.
• Log files: system logs, application logs, web server access logs all append continuously.
• Email databases: Mbox files, Maildir files, modern email client databases all grow over time.

Garfinkel’s fragmentation statistics

Simson Garfinkel’s foundational 2007 research on file fragmentation produced widely-cited rates from real-world drive samples:

• Up to 58% of Outlook PST files were fragmented
• 17% of JPEG image files were fragmented
• 16% of Microsoft Word documents were fragmented

These rates established that fragmentation is not an edge case but a substantial fraction of files on real drives. The numbers also motivated subsequent research into fragmented-file carving algorithms (SmartCarving, bifragment gap carving) that specifically target the fragmentation problem.

Recovery from fragmented files is dramatically harder than recovery from contiguous files. The reason is that recovery techniques fall into two categories with very different fragmentation responses.³

File-system-based recovery handles fragmentation gracefully

When file system metadata is intact (recently deleted files where the MFT record or directory entry still exists), recovery software simply reads the metadata, follows the cluster references, and reads the file’s clusters in their recorded order. The fragmentation pattern is encoded in the metadata; recovery is no harder than normal file access. This is the primary recovery path for most consumer recovery scenarios and works equally well for contiguous and fragmented files.

Signature-based recovery breaks on fragmented files

When file system metadata is gone (formatted volumes, corrupted MFT records, severely damaged file systems), recovery falls back to file carving: scanning the disk for known file signatures and reconstructing files from raw cluster content. The Forensics Wiki documentation captures the central problem: “The majority of file carving programs will only recover files that are contiguous on the media (in other words files that are not fragmented).”

The standard carving approach reads forward from a recognized signature until it hits a footer, a known file size, or invalid content. For contiguous files, this works well. For fragmented files, the cluster after the first fragment belongs to a different file (or is unallocated), and the carving tool either:

• Stops too early (the next cluster looks invalid; the tool truncates the file to the first fragment, producing a partial file).
• Reads through (the next cluster’s content gets included in the output, producing a corrupted file with foreign data inserted).
• Stops at the wrong boundary (the tool finds something that looks like a footer somewhere in unrelated data).

Why most carvers don’t handle fragmentation

Adding fragmentation handling to a carver is computationally expensive. To find the rest of a fragmented file, the carver has to search the entire unallocated space for clusters that might continue the file, validate each candidate, and order the candidates correctly. For files with multiple fragments, the search space grows combinatorially; brute-force approaches are infeasible on real-world drives. Specialized algorithms (covered in the next section) reduce the search space using heuristics, but most basic carving tools (Foremost, Scalpel) don’t implement them and produce poor results on fragmented files.

The DFRWS Carving Challenge

The Digital Forensic Research Workshop introduced the DFRWS Carving Challenge in 2006, which established fragmentation as the central unsolved problem in file carving. The challenge dataset included deliberately fragmented files; competitors had to recover them as completely as possible. The challenge motivated subsequent algorithmic work on fragmented-file recovery and remains a reference benchmark for evaluating carving tools.

Several specialized techniques attempt to recover fragmented files where standard carving fails. Each has its own trade-offs and applicability range.⁴

Header / Footer carving (the baseline)

The simplest approach: find a header signature, read forward until finding a footer signature, treat everything between as the file. The SalvationDATA reference confirms this as the foundational method. Works only for contiguous files with both header and footer signatures (JPEG, PDF, ZIP). Produces broken or wrong files for fragmented inputs. Despite the limitation, it’s the fastest method and the default mode for tools like Scalpel and Foremost.

Header-Size carving

Some file types embed their total size in the header (for example, PNG includes total chunk lengths; ZIP includes uncompressed-size and compressed-size fields). The carver reads the header, extracts the size, then reads exactly that many bytes after the header. Works only for contiguous files; the read-forward assumption still applies.

Bifragment gap carving

The Klennet Carver documentation describes bifragment gap carving as a specialized technique for files split into exactly two fragments with a gap of unrelated data between them. The technique works because for a file with known total size and known boundaries (header at one end, footer at the other), the size of the gap can be computed: gap size equals the total distance between header and footer minus the known file size.

The carving tool then tests possible gap positions, validating each candidate by checking whether the resulting file is structurally valid. The major advantage is that bifragment gap carving works with a validation function alone, without requiring a proximity function. For each possible gap position, the tool runs validation; the position that produces a valid file is the correct gap location. The limitation is that the technique only handles files split into exactly two fragments; files with three or more fragments require different approaches.

SmartCarving (Pal, Memon, Sencar, Shanmugasundaram)

The Wikipedia file carving documentation describes SmartCarving as a more general algorithm. Unlike bifragment gap carving, SmartCarving handles files split into many fragments. The algorithm has three phases:

1. Preprocessing: blocks are decompressed or decrypted if necessary, normalizing them for analysis.
2. Collation: blocks are sorted according to their file type using content-based heuristics about the fragmentation behavior of known file systems.
3. Reassembly: blocks are placed in sequence to reproduce the deleted file using statistical methods to determine the most likely fragment ordering.

SmartCarving is the basis for the Adroit Photo Forensics and Adroit Photo Recovery applications from Digital Assembly. The approach is more computationally expensive than traditional carving but recovers fragmented files that traditional methods would miss entirely.

Sequential hypothesis testing

Wikipedia notes that “state-of-the-art file carving algorithms use statistical techniques like sequential hypothesis testing for determining fragmentation points.” The approach analyzes the data stream for statistical anomalies that indicate where one file ends and another begins, allowing the carver to identify fragment boundaries even when no clear footer signature exists.

Fragment Recovery Carving (Garfinkel’s “Split Carving”)

The Forensics Wiki describes Fragment Recovery Carving as a carving method in which two or more fragments are reassembled to form the original file or object. Garfinkel previously called this approach “Split Carving.” This is the general category that bifragment gap carving and SmartCarving both fall under; the term covers any technique that explicitly handles fragmentation rather than assuming contiguity.

Tool ecosystem

Tools that implement fragmentation-aware carving:

• Klennet Carver: implements bifragment gap carving as a primary recovery technique; published real-world data on bifragment recovery applicability.
• Adroit Photo Forensics / Adroit Photo Recovery: implements SmartCarving for image recovery.
• R-Studio: includes fragmentation-aware carving for many file types as part of its scanning pipeline.
• X-Ways Forensics: supports manual fragment reassembly through its hex editor and structured analysis features.
• PhotoRec: the open-source standard for signature-based recovery; primarily contiguous-file oriented but handles some fragmented file types with heuristics.
• Foremost / Scalpel: open-source carvers; primarily contiguous-only.

The performance impact and the recovery impact of fragmentation differ significantly between hard drives and solid-state drives. Understanding the difference is important both for general system maintenance and for setting recovery expectations.

HDD physical impact: seek penalty

On a hard drive, reading non-contiguous clusters requires the read head to physically move between tracks. Each seek operation takes several milliseconds; a heavily fragmented file can require many seeks to read sequentially, dramatically slowing access. Defragmentation tools rearrange files into contiguous clusters, eliminating the seeks and improving sequential read performance. Windows includes a built-in Disk Defragmenter; third-party tools (Auslogics Disk Defrag, Defraggler) provide additional control and visibility.

SSD physical reality: no seek penalty

On a solid-state drive, there’s no read head and no physical movement. SSDs are random-access at the cell level, and reading any cell takes the same time regardless of which cells came before or after. The wear-leveling translation layer means that even logically contiguous files are physically scattered across NAND cells; the SSD’s controller distributes writes for wear-leveling reasons rather than for performance reasons. Defragmenting an SSD provides zero performance benefit while adding significant write wear to the cells. Modern Windows recognizes SSDs and skips defragmentation accordingly; manual defragmentation of SSDs is actively counterproductive.

Recovery impact is identical

From a recovery perspective, the carving complications are the same on both storage types. Logical fragmentation (the file system’s view of which clusters belong to which file) creates the carving problem; the underlying physical layout doesn’t change the carving problem. A fragmented file on an HDD is just as hard to carve as the same fragmented file would be on an SSD. The TRIM-on-SSD issue (covered in the unallocated space entry) is a separate problem that’s specific to SSDs but unrelated to fragmentation per se.

Per-file-system fragmentation rates

Different file systems produce different fragmentation rates under similar workloads:

• NTFS: heavy fragmentation under typical Windows usage; defragmentation tools commonly used. NTFS uses an MFT record per file with data runs encoding fragmentation.
• FAT32 / exFAT: heavy fragmentation; the FAT structure inherently encodes per-cluster pointers that fragment naturally.
• ext4: reduced fragmentation due to delayed allocation and extent-based storage; defragmentation rarely needed.
• APFS: low fragmentation due to extent-based copy-on-write architecture; defragmentation isn’t a normal maintenance operation.
• Btrfs / ZFS: copy-on-write file systems can produce high fragmentation under certain workloads (large files updated in place); both have specific tools to handle the issue.