索引修改内幕

索引修改的大致规则：

 

对表的任何修改操作(UDI)，总会对表上的非聚集索引执行等价的操作。某些更新操作除外。

 

对表的任何修改操作，都会先修改堆或者聚集索引，然后再修改非聚集索引。

 

如果修改的数据行，正是过滤索引过滤掉的行(过滤索引的叶级页不包含的行)，则不会对过滤索引产生任何操作。

 

插入数据行

 

对于聚集和非聚集索引的插入，新行(不管是数据行还是索引行)所包含的索引键列值就决定了它将被插入的位置。插入操作的可能来源有：

 

直接的INSERT命令

 

UPDATE导致的行移动(原来的地方已经容不下被更新后的行)，内部使用先DELETE,再INSERT的UPDATE策略。

 

UPDATE导致的索引键列变更。索引行是有序的，行的索引键值变更会导致行在索引中的位置变更，从而需要移动到新位置。同样是先DELETE，再INSERT。

 

如果当前索引的叶级(叶级在聚集索引中是数据页，非聚集索引中是索引页)没有空间存放插入的新行，则索引会发生页拆分(Page Split)。行在索引中的位置是有序的，所以当新行将要被插入的某个特定页没有可用空间时，就需要分配新页给索引。会先从已经分配的区中找是未使用的页，如果没有，则会分配一个新的统一区给索引，然后再使用新区中的页。

 

页拆分

 

得到新页之后，SQL Server会尽量按照”对半分“原则，拆分原来页上的一半数据行到新页。第一次拆分是基于页上偏移阵列(Offset Array)来计算的。每次索引页拆分，还要向B+树中的父级页添加一行。有时需要多次页拆分才能将新行保存下来。页拆分发生的越多，新页也载多，需要向你级页添加的行数载多，很有可能同时导致父级页也发生页拆分。

 

索引树的查找方式是从根节点向叶节点进行的，所以Insert导致的页拆分也是从根节点向下发生的。这样在Insert导致的拆分未完成前，索引树需要使用闩锁(Latch)对索引进行保护，以防止索引被其它的操作修改。当从磁盘上读/写页时或者对数据页进行操作时(如页拆分)，为了保护页中的数据的物理完整性，需要对页加上闩锁进行保护。当子节点的拆分完成并且不再需要对父节点进行更新时，索引树中父节点的闩锁才会被释放。 

 

在父节点的闩锁释放前，SQL Server会检测父节点页中是否还能容纳两行新数据。如果不能，则拆分它。这种情况只会当查找索引，并且需要向索引页中添加新行时才会发生。这样做的目的是当由于子级页发生页拆分而需要向父级页插入新行时，父级页总是有空间存放这些新行。

 

页拆分的类型由发生拆分的页的类型决定

 

根页拆分

 

当根页发生拆分时，会分配两个新页给索引。原来根页的数据会被插入到这两个新页中。原来的根页仍然是索引的根页，它上面只有两行数据，分别指向两个新页。原来的根页被保留，可以避免修改系统目录中指向根页的指针值。根页拆分会导致索引增加新的一级索引层次(深度增加一级)。这种拆分很少发生。

 

中间级页拆分

 

中间索引页发生拆分时，会增加一个新页，然后根据索引键的中间点(Midpoint)将一半的行拆分到新页，再往父级页中插入一行指向新页。这种拆分也很少发生。

 

叶级页拆分

 

这是最常见，也是最需要关注的拆分类型。聚集索引数据页和非聚集索引叶级页的拆分机制是一样的。虽然数据页拆分只会发生在对聚集索引表执行Insert操作时，但是也可能是Update操作导致的内部Insert操作。前文提过了，当Update不是原地更新时，会执行先Delete再Insert的操作。

 

叶级页的拆分与中间级页的方式类似。但是需要索引管理器决定两页中的谁来接收后续的新行，还要处理两个页面谁也存不下的大型行(Large Row)。数据页拆分不会改变聚集索引键，所以相关的非聚集索引不会受到影响。

 

下面通过例子观察一下叶级页拆分。创建一个表，定义并插入大型行，使得一个页只能存放5行数据，然后插入第6行数据后，观察页拆分的情况。注意第6行的聚集键小于第5行。

USE test
go
CREATE TABLE bigrows
(
 a int primary key,
 b varchar(1600)
);
GO
/* Insert five rows into the table */
INSERT INTO bigrows
 VALUES (5, REPLICATE('a', 1600));
INSERT INTO bigrows
 VALUES (10, replicate('b', 1600));
INSERT INTO bigrows
 VALUES (15, replicate('c', 1600));
INSERT INTO bigrows
 VALUES (20, replicate('d', 1600));
INSERT INTO bigrows
 VALUES (25, replicate('e', 1600));
GO
--get the data page id
select allocated_page_file_id as PageFID,allocated_page_page_id as PagePID,page_type_desc
from sys.dm_db_database_page_allocations(db_id('test'),object_id('bigrows'),null,null,'Detailed')
go
dbcc traceon(3604)
dbcc page(test,1,168,1)
go
 
--OFFSET TABLE:
--Row - Offset                        
--4 (0x4) - 6556 (0x199c)            
--3 (0x3) - 4941 (0x134d)            
--2 (0x2) - 3326 (0xcfe)              
--1 (0x1) - 1711 (0x6af)              
--0 (0x0) - 96 (0x60)
 
INSERT INTO bigrows
 VALUES (21, replicate('f', 1600));
GO
select allocated_page_file_id as PageFID,allocated_page_page_id as PagePID,page_type_desc
from sys.dm_db_database_page_allocations(db_id('test'),object_id('bigrows'),null,null,'Detailed')
go
dbcc traceon(3604)
dbcc page(test,1,168,1)
dbcc page(test,1,172,1)
go
--Page 168
--OFFSET TABLE:
--Row - Offset                        
--2 (0x2) - 3326 (0xcfe)              
--1 (0x1) - 1711 (0x6af)              
--0 (0x0) - 96 (0x60)
 
--Page 172
--OFFSET TABLE:
--Row - Offset                        
--2 (0x2) - 1711 (0x6af)              
--1 (0x1) - 3326 (0xcfe)              
--0 (0x0) - 96 (0x60)  

 

通过偏移阵列，可以看出页拆分后原来的页和新页各有三行。通过观察DBCC PAGE的输出的行内容，可以看到：

 

原来的页(PID:168)保存着聚集索引键值为5，10和15的行，新页(PID:172)保存着20，21和25的行。

 

在新页上，21这行存储在Slot1的位置上。根据Offset的值，21实际的物理位置却是在25之后。

 

21的逻辑位置在25之前，物理位置在25之后。可以看出：行的聚集索引键顺序是由Slot编号表示的，而不是行的物理位置。也就是聚集索引表中，某行的Slot编号小于另一行，则它的聚集索引键值也小于它。这其实是一种优化的设计结果：当页上发生数据修改时，只需要修改页上偏移阵列的值来保证行的顺序，而不需要物理性的移动数据行位置来保证顺序。极大地减少数据修改的开销。所以“索引中行的物理存储顺序总是与它的索引键值的顺序是一样的。”这种说法是不正确的。实际上，只要偏移阵列提供了正确的逻辑顺序，行可以存储页的任意位置。

 

页拆分的代价是很大的。页拆分过程中对旧页、新页和父页的修改操作，都需要完整写入事务日志。最小化业务高峰期发生页拆分的办法，通常有：

 

选择一个更合理的聚集索引键。比如，让新行插入到表的末尾，而不是像GUID那样随机插入。

 

对于更新变长列引起的页拆分，可以通过减少索引的填充因子(Fill Factor)，在页上保留多一些可用空间给变长列更新使用。

 

删除数据行

 

删除数据行时，需要同时考虑数据页和索引页的变化。聚集索引表中删除行与非聚集索引叶级中删除行是一样的方式。

 

叶级中删除行

 

当索引叶级的行被删除时会被标记为幻影行(Ghost Record)。行被删除后，行头的一个位(Bit)被修改，行就标记为幻影，但是行还是保留于页上。页头的元数据m_ghostRecCnt表示当前页的幻影行的数量。幻影行的用途有：

 

快速回滚。当行没有被物理删除时，回滚Delete操作只需要修改行头的表示幻影行的位即可。

 

键值范围锁定(key-Range Locking)和其它锁定的并发优化

 

用于行版本控制

 

幻影行什么时候被清除，由系统负载决定。SQL Server有一个叫做ghost-cleanup的后台线程，用于清理那些不再需要被活动事务和其它功能使用的幻影行。幻影行可能很快被ghost-cleanup线程清除掉。所以为了观察幻影行，可以将Delete包裹在未被提交或者回滚的用户事务中，或者使用末公开的(Undocumented)跟踪标记661来禁用幻影行清理功能。可以使用存储过程sp_clean_db_free_space清除整个库的幻影行，也可以用sp_clean_db_fie_free_space清除库中指定数据文件中的全部幻影行。

 

下面的例子，删除聚集索引表中的一行，观察幻影行。

USE test
GO
IF object_id('dbo.smallrows') IS NOT NULL
 DROP TABLE dbo.smallrows;
GO
CREATE TABLE dbo.smallrows
(
 a int IDENTITY PRIMARY KEY,
 b char(10)
);
GO
INSERT INTO dbo.smallrows
 VALUES ('row 1');
INSERT INTO dbo.smallrows
 VALUES ('row 2');
INSERT INTO dbo.smallrows
 VALUES ('row 3');
INSERT INTO dbo.smallrows
 VALUES ('row 4');
INSERT INTO dbo.smallrows
 VALUES ('row 5');
GO
--get data page id
select allocated_page_file_id as PageFID,allocated_page_page_id as PagePID,page_type_desc
from sys.dm_db_database_page_allocations(db_id('test'),object_id('smallrows'),null,null,'Detailed')
go
DELETE FROM dbo.smallrows
WHERE a = 3;
GO
dbcc traceon(3604)
dbcc page(test,1,174,1)
go

 

截取DBCC PAGE输出中与幻影行相关的内容。

 

页头中(Page Header)中的 m_ghostRecCnt = 1，表示当前页中幻影行数量是1。

 

Slot2中的Record Type = GHOST_DATA_RECORD，表示当前行是幻影行。

 

偏移阵列中，Slot2的偏移量没有变，其它Slot的偏移理也没有变化。表示没有行发生移动。

OFFSET TABLE:

Row - Offset

4 (0x4) - 180 (0xb4)

3 (0x3) - 159 (0x9f)

2 (0x2) - 138 (0x8a)

1 (0x1) - 117 (0x75)

0 (0x0) - 96 (0x60)   

 

可以通过sys.dm_db_index_physical_stats查看表中的幻影行总数。

 

中间级中删除行

 

中间级中删除行与从堆表中删除行类似。中间级页中被删除行，不会被标记为幻影行，所占用的页空间也不会立刻释放，当有新索引行需要页面上的空间时才被释放和重用。

 

页回收

 

数据页上所有行被删除后，这个页会被ghost-cleanup线程回收(Dealocated)。堆表是个例外。如果表只有一个数据页，此页也不会被回收。当数据页被删除，指向这些数据页的索引行会被删除。中间级页上索引行全被删除，不会马上回收，而是会在页上保留一行，这一行稍后会被移动到邻近的有空闲空间的页上，然后回收原来的空页。

 

更新行

 

SQL Server会自动选择最优的数据更新策略。基于受影响行数，访问数据的方式和是否需要修改索引键来选择最优的策略。更新实现方式包括：直接将旧值原地修改为新值;删除旧行再插入新行。

 

行移动

 

发生行移动的两种情况：

 

当行中的变长列被更新后，原来位置无法再存储它时

 

因为行的逻辑顺序由索引键决定，所以当聚集索引或者非聚集索引的键列发生修改后，行的逻辑顺序发生改变时。例如当在lastname列上建立聚集索引，lastname为Abel的行存储在接近表开始的位置，如果将Abel修改为Zek，则将会被移动到接近表结束的位置。

 

非聚集索引的叶级中包含指向表中每一行的行定位器。聚集索引表中，行定位器就是聚集索引键。所以仅当聚集索引键被修改时，非聚集索引才会被修改。因此选择聚集索引键列时，尽量选择非易失性的列(数据修改率极低，如Identity)。聚集索引表中，就算表的物理位置发生改变，也不会导致索引键改变，所心非聚集索引也不会被修改。

 

堆表中，行定位器是行的物理地址。行移动不会导致非聚集索引修改，因为它在行的原地址放置一个转发指针指向新地址，非聚集索引仍然引用原来的行地址，通过转发指针做重定向而已。但是堆表物理位置改变，会导致所有非聚集索引被修改。

 

原地更新

 

原地更新行是SQL Server的更新规则。每一个原地更新操作都会在向事务日志写入一行，除非表上有更新触发器或者被标记为复制时。

 

如果原地更新需要修改索引键，则每个操作会向事务日志先写入一条DELETE记录，然后再写入一样INSERT记录。

 

原地更新的场景：

 

更新堆，被更新的页有足够的空间存放更新后的行。

 

更新聚集索引表，且聚集索引列没有被更新。

 

更新聚集索引表的聚集索引列，但是更新后的行不会发生移动。

 

非原地更新

 

非原地更新发生在更新聚集索引的索引键时。更新会变成先删除再插入两个操作。更新索引键也有可能是混合更新，即有些行是原地更新，其它行是非原地更新。更新聚集索引键时，SQL Server会生成一个包含删除和插入操作涉及到的所有行的列表。这个列表较小就存在内存，较大就存在tempdb。然后根据键值和操作符(删除或者插入)对列表排序。接下来分种情况：

 

如果索引键值非唯一，则先删除再插入。

 

如果索引键值唯一，则会将删除和插入这两个操作合并成一个更新操作。这样更高效。

 

表级修改vs.索引级修改

 

在多索引的表上修改多行数据时，SQL Server提供两种索引维护策略：表级修改和索引级修改。表级修改也叫做"一次一行"(row-at-a-time)，索引级修改也叫做”一次一索引“(index-at-a-time)。

 

在表级修改中，每一行数据被修改时，所有的索引都需要被维护一次。如果更新流是无序的，则SQL Server每更新一行就需要访问一次索引，这样就增加很多的随机访问。如果更新流是有序的，因为只能按一种条件排序，所以最多有一个索引不需要随机访问。

 

在索引级修改中，SQL Server将所有将要被修改的行汇总起来，并针对索引进行排序(有几个索引，就会有几次排序)。然后将所有的修改汇总再应用到每个索引上。可以看出，这个过程中每个索引页最多被访问一次。

 

修改大表和索引上中的很少部分数据，SQL Server一般采用表级修改。如果修改的量非常大，则一般会选择索引级修改。通过执行计划可以看出采用的哪种修改方式：每个受影响的索引前都有一个UPDATE操作符，则是索引级。如果只有UPDATE操作符，则是表级。