How does defrag work, what is fragmentation?

 

Overview

many people have questions about fragmentation and defragmentation.

defrag is available from Start, My Computer, right click on c: or whatever drive, pick properties, in the tools tab, you should see defragment.

fragmentation

the hard disk is broken up into blocks. fragmentation means the file gets allocated out of sequence (non-sequentially), in other words, it gets broken up into pieces all over the place. the reason why is because some other file is taking up the next sequential block. space allocation is an algorithm all its own.

when you have no sequential space left, you have to use non-sequential space (unallocated "holes" in the allocated block layout) to allocate disk space for your file. NTFS tries to work from the center of the disk out to reduce disk arm movement (more speed).

defragmentation/defrag

under windows with NTFS, and probably Mac OS X with HPFS since they are essentially the same filesystem, you must have 15% free disk space to defragment due to the defrag algorithm (the alternative would be to recode the algorithm to use massively huge amounts of memory which I can almost guarantee you don't have, and memory is expensive)

defragmentation is an algorithm I have not coded myself, so I don't understand it completely (maybe it's on wikipedia) but heres how I think it's coded: use the free disk space as temporary space to sort the moveable blocks, sorting by os first, then by file, then by sequential file block number, keeping the weight toward the center of the disk, and ignoring unmoveable files, moving files as an atomic unit/transaction so that broken files do not result if someone stops the process.

by ordering the sort this way, OS files are put in the center first, then regular files are piled around it, and the files will be in sequence.

at the most basic level, sort comparison functions are all that is needed I think, and some disk I/O functions, and some appropriate sort function that is most applicable to this type of problem.

defrag is available from Start, My Computer, right click on c: or whatever drive, pick properties, in the tools tab, you should see defragment.