How record DELETEs can cause index fragmentation

Question: Our team has been discussing causes of index fragmentation and someone argued that DELETE operations can cause fragmentation just like INSERT and UPDATE operations. This doesn’t make sense to me – can you explain how this is possible?

Answer: Record deletion can indeed cause fragmentation.

There are two kinds of fragmentation described by SQL Server Books Online: logical fragmentation and low page density. Some people have other names for these, including external, internal, and physical fragmentation. I always discourage people from using these names, as they are not referenced or explained by Books Online (and I wrote the Books Online around fragmentation :-)

Related: How Does Index Fragmentation Affect SELECT Performance?

Logical fragmentation is where the data file page with the next set of key values in an index is not the next physically adjacent page. A variant of this is extent fragmentation, where the adjacency is at the extent (8 contiguous data file pages) level rather than the page level. Both of these lead to reduced range scan efficiency through reduced readahead I/O size.

Low page density is when there is empty space on data file pages in an index, either caused by page split operations, record deletion, or record size where only a few records can fit on a page, forcing empty space (e.g. a 5000-byte clustered index record size, where only one record can fit per 8KB page, leading to 3000 bytes of empty, wasted space per page). This leads to reduced data density – extra space required on disk to store the data, wasted buffer pool memory, and more I/Os are required to read the same amount of data. You can read more about the performance implications in my in-depth blog post here.

As I mentioned above, record deletion can cause low page density, which is a form of index fragmentation. Consider the case where a table has a clustered index with an INT IDENTITY key. New records will always be inserted with a key value higher than all previously inserted records, so the record insertion point will be (conceptually) on the right-hand size of the index structure.

If records are randomly deleted from the table, this will cause free space ‘holes’ throughout the index structure. As the index key means that all new records are inserted at the right-hand side of the index, the free-space holes will never be filled by newly inserted records. Over time, with many deletes, the amount of free space in the index may become significant, leading to classic low data density issues as I described previously. This will necessitate removing the free space with an ALTER INDEX … REORGANIZE or ALTER INDEX … REBUILD operation.

To summarize, all DML operations (INSERT, UPDATE, and DELETE) can cause index fragmentation, if you consider both logical fragmentation and low page density, and the index structure lends itself to index fragmentation of one kind or the other occurring.