在实现数据查找时，对无序数据进行查找，最快的查找算法是哈希查找，对有序数据进行查找，最快的查找算法是平衡树查找。在传统的关系型数据库中，聚集索引和非聚集索引都是平衡树类型的存储结构，用于顺序存储数据，便于对数据进行快速的平衡树查找。索引结构是BTree结构，分为叶子节点和非叶子节点，叶子节点用于存储数据，而非叶子节点（中间节点和根节点）用于存储索引键，节点数据按照索引键排序。理论上，一旦数据集确定下来，索引查找的时间消耗就只跟索引结构的层次有关系，层次越多，查找消耗的时间越多，而碎片会影响索引的层次结构。

在数据的物理存储上，索引和数据存储在硬盘文件上，硬盘文件以页（Page）为最小单位分割，每一个Page是8KB，物理位置上连续的8个Page叫做一个区（Extent），每一个区是64KB。区是空间分配的基本单位，而页是数据存储的基本单位。

从物理存储上来看，索引是由一系列的分段（Fragment）构成的，每个分段是由连续的数据页（Page）构成的。理想情况下，数据存储的物理顺序和索引键定义的逻辑顺序保持一致，这对数据的范围查询有利，这是因为机械硬盘不需要移动磁头就可以获取到所需数据；由于数据的更新（Insert，Update或Delete），会导致索引产生碎片，少量的碎片能够减少页拆分（page split）发生的次数，提高数据更新的性能；而大量的碎片碎片是十分有害的，增加IO的次数，降低查询性能。

索引除了能够提升数据查找的性能，还能减少硬盘IO和内存消耗。通常情况下，硬盘IO是查找性能的瓶颈，由于索引是数据表的列的子集，占用的硬盘空间教少，数据库引擎只需要消耗相对较少的硬盘IO和内存buffer，就能把索引数据加载到内存中。

数据更新和数据查找是此消彼长的关系，在索引页中预留空闲空间会增加索引的Size，然而，额外占用的硬盘空间需要额外的硬盘IO加载到内存中，这不利于数据的查找，然而，当发生数据更新时，预留的空间能够容纳数据行Size的增加，减少页拆分发生的次数，这有利于数据的更新，因此，在频繁更新的数据库系统中，为了减少页拆分的次数，需要人为增加索引的内部碎片：

• FILLFACTOR = fillfactor
• PAD_INDEX = { ON | OFF }

在创建索引时，需要权衡填充因子和数据查找对系统的影响，维护平衡状态，使数据库达到最优状态。

一，索引碎片

索引碎片分为内部碎片（Internal Fragmentation）和外部碎片（External Fragmentation），内部碎片是指索引页内部的碎片，在索引页内部存在没有使用的空间，部分空间被闲置，这意味索引页存在空间的浪费，数据实际占用的空间多于需要的空间，因此，当存储相同的数据集时，如果索引的碎片越多，索引结构占用的硬盘空间越多；在处理数据时，数据库引擎需要读取的索引页越多，加载到内存消耗的缓存页（Buffer）越多。内部碎片会出现在索引结构的叶子节点或中间节点，叶子节点中的碎片会导致数据密度降低，而中间节点中的碎片会导致索引键的密度降低。

外部碎片是指存储数据的页或区（Extent）的逻辑顺序和物理顺序不一致，逻辑顺序（Logical Order）是由索引键定义的，物理顺序（Physical Order）是在硬盘文件中，用于存储数据的页或区的顺序，也就是索引的叶子节点占用的页或区在硬盘上的物理存储的顺序。如果在逻辑上连续的Page或Extent在物理上也是连续的，那么就不存在外部碎片。最有效的顺序是：逻辑顺序上相邻的数据页，在物理顺序上也相邻。

The most efficient order is where the logical order of the pages and extents(as defined by the index keys, following the next-page pointers from the page headers) is the same as the physical order of the pages and extents with the data files. In other words, the index leaf-lelvel page that has the row with the next index key is also the next physical contiguous page int the data file.

 二，检测索引碎片

可以通过内置函数: sys.dm_db_index_physical_stats，查看索引的外部碎片，字段 avg_fragmentation_in_percent 用于表示外部碎片的程度，对于索引，以Page为单位统计碎片；对于堆（Heap），以Extent为单位统计碎片，这是因为Heap结构的页（Page）是没有顺序的。在堆（Heap）的 Page Header中，字段 next_page 和 Pre_page pointer是null。字段 avg_page_space_used_in_percent 用于表示内部碎片的程度，百分比越高，说明单个Page的空间利用率越高。

1，扫描模式

检测索引的碎片，需要对索引进行扫描，参数mode指定为了获取碎片数据，数据库引擎必须执行的扫描模式，共有三种模式：LIMITED, SAMPLED, or DETAILED，默认值是LIMITED。

• Limited 模式是最快的，只扫描最小数据量的Page，Limited模式不会扫描数据页（Data Page），对于索引，扫描叶子节点的直接父节点；对于Heap，扫描堆表对应的IAM 和 PFS系统页。
• 在Sampled模式下，数据库引擎从索引或堆表中抽取1%的Page作为样本数据，根据样本数据来估计碎片的程度。
• Detailed 模式扫描所有的数据页，耗时最久，返回的信息最详细。

2，分段和碎片

分段（Fragment），也叫片段，是指在硬盘文件中，数据的物理存储的集中/分散程度。一个片段是由在物理位置上连续的索引页组成的，Fragment的Size 越大，说明页的物理位置越集中，读取相同数量的Page所需的IO越少，范围读取性能越好。

碎片（Fragmentation）用于描述数据更新对索引结构产生的副作用。页内碎片是指Page 内部存在空闲空间，外部碎片是指Page 或 extent 的物理顺序和所以键定义的逻辑顺序不一致。

• avg_fragmentation_in_percent：碎片百分比，合理的比例是在10左右，比例越大，索引碎片越多，读取性能越差；
• fragment_count：分段的数量，理论上，分段（Fragment）数量越少越好，间接说明索引的物理顺序和逻辑顺序越匹配；
• avg_fragment_size_in_pages：每个分段平均包含的Page数量，Fragment的Size 越大，读取相同数量的Pages所需的IO越少，读取性能越好；
• avg_page_space_used_in_percent：Page空间的平均利用率，值越大，页内碎片越小；

3，检测碎片的脚本

通过执行函数，检测索引的碎片：

select ps.database_id,    ps.object_id,    ps.index_id,    ps.partition_number,    ps.index_type_desc,    ps.alloc_unit_type_desc,    ps.index_depth,    ps.index_level,    ps.avg_fragmentation_in_percent,    ps.fragment_count,    ps.avg_fragment_size_in_pages,    ps.page_count,    ps.avg_page_space_used_in_percent,    ps.record_count,    ps.ghost_record_count,    ps.version_ghost_record_count,    ps.min_record_size_in_bytes,    ps.max_record_size_in_bytes,    ps.avg_record_size_in_bytes,    ps.forwarded_record_count,    ps.compressed_page_countfrom sys.dm_db_index_physical_stats(database_id,object_id,index_id,partition_number,‘detailed‘) as psorder by ps.index_level

View Code

字段avg_fragmentation_in_percent 表示索引碎片的密度，可以接受的百分比是从0到10%，根据碎片的百分比，选择重新组织索引或重新创建索引，以整理碎片。

返回的字段分析：

• Index_level=0，表示是索引结构的深度，0表示叶子级别；
• avg_fragmentation_in_percent：碎片的百分比，表示物理顺序不连续的pages所占的百分比；如果基础表是BTree， 碎片的计量单位是Page，avg_fragmentation_in_percent和page_count 的乘积就是物理顺序和逻辑顺序不一致的pages的总数量。
• fragment_count：片段的数量
• page_count：page 的数量
• avg_fragment_size_in_pages：每个Index 片段平均使用的Pages，是Page_Count和Fragment_Count的比值。
• avg_page_space_used_in_percent：每个Page内空间的平均使用程度

三，碎片整理

碎片整理有两种方式：重新组织索引和重新创建索引，重建索引是指在一个事务中，删除旧的索引，并重建新的索引，这种方式会回收原有索引的硬盘空间，并分配新的存储空间，以创建索引结构。重组索引是指不分配新的存储空间，在原有的空间基础上，重新组织索引结构的叶子节点，使数据页的逻辑顺序和物理顺序保持一致，并释放索引中多余的空间，这就是说，重组索引是为了减少叶子节点的外部碎片。

使用函数 sys.dm_db_index_physical_stats 检测碎片的程度，字段 avg_fragmentation_in_percent   返回的逻辑碎片的百分比，一般情况下，微软推荐以30%为阈值：

• avg_fragmentation_in_percent >5% and <=30%： 重组索引（ALTER INDEX REORGANIZE）；
• avg_fragmentation_in_percent >30%： 重建索引（ALTER INDEX REBUILD）；

以下脚本使用游标（Cusor）逐个整理索引碎片，在重建索引（Rebuild Index）时，使用的索引选项是：FILLFACTOR = 95, ONLINE = OFF, DATA_COMPRESSION = PAGE

DECLARE @SchemeName NVARCHAR(MAX)=N‘‘;DECLARE @TableName NVARCHAR(MAX)=N‘‘;DECLARE @IndexName NVARCHAR(MAX)=N‘‘;DECLARE @avg_fragmentation_in_percent FLOAT=0;DECLARE @SQL NVARCHAR(MAX)=N‘‘;DECLARE cur_index CURSORLOCALFORWARD_ONLYFAST_FORWARDREAD_ONLYFORSELECT    ‘[‘+s.name+‘]‘ AS SchemeName,    ‘[‘+o.name+‘]‘ AS TableName,    ‘[‘+i.name+‘]‘ AS IndexName,    MAX(ps.avg_fragmentation_in_percent) AS avg_fragmentation_in_percentFROM sys.indexes iINNER JOIN sys.objects o    ON i.object_id = o.object_idINNER JOIN sys.schemas s    ON o.schema_id = s.schema_idINNER JOIN sys.dm_db_index_physical_stats(DB_ID(), NULL, NULL, NULL, N‘DETAILED‘) AS ps    ON ps.object_id = i.object_id    AND ps.index_id = i.index_idWHERE ps.avg_fragmentation_in_percent >= 10AND i.type IN (1, 2)    --1: CLUSTERED, 2: NONCLUSTEREDAND o.type = N‘U‘        --U: USER_TABLEAND ps.index_level = 0    --Index leaf-level GROUP BY    s.name,            o.name,            i.nameORDER BY avg_fragmentation_in_percent DESC;OPEN cur_index;FETCH NEXT FROM cur_indexINTO @SchemeName, @TableName, @IndexName, @avg_fragmentation_in_percent;WHILE(@@FETCH_STATUS=0)BEGIN    IF (@avg_fragmentation_in_percent>30)    BEGIN        SELECT @SQL = N‘ALTER INDEX ‘ + @IndexName + N‘ ON ‘ + @SchemeName + N‘.‘ + @TableName                         + N‘ REBUILD PARTITION=ALL WITH (FILLFACTOR = 95, ONLINE = OFF, DATA_COMPRESSION = PAGE );‘    END     ELSE --@avg_fragmentation_in_percent between 10 and 30    BEGIN        SELECT @SQL = N‘ALTER INDEX ‘ + @IndexName + N‘ ON ‘ + @SchemeName + N‘.‘ + @TableName                         + N‘ REORGANIZE PARTITION=ALL;‘    END    EXEC (@SQL)    FETCH NEXT FROM cur_index    INTO @SchemeName, @TableName, @IndexName, @avg_fragmentation_in_percent;ENDCLOSE cur_index;DEALLOCATE cur_index;

View Code

这个阈值，可以根据产品环境数据更新和查找的实际情况，适度调整。

参考文档：

Reorganize and Rebuild Indexes

sys.dm_db_index_physical_stats (Transact-SQL)

索引碎片检测和整理