6.1 索引的作用与结构

6.1.1 索引概述

1.什么叫索引

索引是对数据库表中一个或多个列的值进行排序的结构。每个索引都有一个特定的搜索码与表中的记录相关联，索引按顺序存储搜索码的值。比如，数据库中的一种非聚集索引与书籍中的索引类似，在一本书中，利用索引可以快速查找所需信息，无须阅读整本书；在数据库中，索引使数据库程序无须对整个表进行扫描，就可以在其中找到所需数据。书中的索引是一个词语列表，其中注明了包含各个词的页码。而数据库中的索引是某个表中一列或若干列值的集合，以及相应的指向表中物理标识这些值的数据页的逻辑指针清单。

2.索引的作用

通过创建唯一索引，可以保证数据记录的唯一性。

索引可以大大加快数据检索速度。如果对于一个未建立索引的表执行查询操作，SQL Server将逐行扫描表数据页面中的数据行，并从中挑选出所有符合条件的数据行，显然，使用这种方式查询，会降低系统查询效率。对建立索引的表执行查询操作，SQL Server将根据索引的指示，直接定位到需要查询的数据行，从而加快数据检索速度。

可以加速表与表之间的连接，这一点在实现数据的参照完整性方面有特别的意义。

在使用ORDER BY和GROUP BY子句进行检索数据时，可以显著减少查询中分组和排序的时间。

使用索引可以在检索数据的过程中使用查询优化器，提高系统性能。

6.1.2 SQL Server索引下的数据组织结构

在SQL Server数据库内，索引页的结构与数据页的结构非常相似。索引页的大小也是固定的8 KB，和数据页一样，索引页也有一个96字节的页头，其中包含类似拥有该页的表的标识符（ID）这样的系统信息。如果页链接在列表中，则页头还包含指向下一页及前面用过的页的指针；但不像数据页那样，索引页的尾部没有用来表示页中偏移的两字节的行偏移数组。

SQL Server索引是通过sysindexes表进行管理的。sysindexes表内的页指针可以定位表、索引和索引视图的所有页集合。每个表和索引视图有一个数据页集合，以及其他一些实现为这个表或视图定义的各个索引的页集合。

每个表、索引和索引视图在sysindexes内有一记录行，由对象标识符（id）列和索引标识符（indid）列的组合唯一标识。索引分配映象（Index Allocation Map，简称IAM）页管理分配表、索引和索引视图所使用的页的空间。FirstIAM列指向IAM页链的IAM首页。如果对象有索引，则root列指向索引B树的顶端。

1.堆集结构

堆集结构不按任何特殊顺序存储数据行，数据页序列也没有任何特殊顺序。数据页不在链表内链接。堆集存储方式是最简单、最原始、最早使用的一种存储结构，在这种结构中，记录按其插入的先后顺序存放，好像堆货物一样，来了新的货物就堆在上面，所以叫做堆结构。堆集在sysindexes内有一记录，其indid = 0。sysindexes.FirstIAM列指向IAM页链的IAM首页，IAM页链管理分配给堆集的空间，如图6-1所示。SQL Server使用IAM 页在堆集中浏览。堆集内的数据页和行没有任何特定的顺序，也不链接在一起。数据页之间唯一的逻辑连接是记录在IAM页内的连接信息。

通过扫描IAM页可以对堆集进行表扫描或串行读，以找到容纳这个堆集的页的扩展盘区。因为IAM按扩展盘区在数据文件内的顺序表示它们，所以这意味着串行堆集扫描一律沿每个文件进行。使用IAM页设置扫描顺序还意味着堆集中的行一般不按照插入的顺序返回。

堆集结构插入很容易，但查找就不方便了。因为它所提供的唯一存取路径就是顺序搜索或顺序扫描，这种操作称为表扫描，即按记录的自然顺序查找所需记录，查找到某一个特定记录行，访问的平均记录数为（N+1）/2。这是一种非常低效的操作。堆集存储方式删除比较麻烦，因为这涉及删除记录的空间回收问题。一般在删除时只做删除标记，等删除的记录累计到一定量后再集中清理一次。

2.聚集索引结构

聚集索引类似于电话簿，如果电话号码按姓氏排列，也就是按姓名索引，则其后的电话号码也随之跟着姓名排列。由于聚集索引规定数据在表中的物理存储顺序，数据行本身只能按一个顺序存储，因此一个表只能包含一个聚集索引。聚集索引对表的物理数据页中的数据按列进行排序，然后再重新存储到磁盘上，即聚集索引与数据是混为一体的，它的叶结点中存储的是实际的数据。

在SQL Server中，聚集索引在系统表sysindexes内的indid = 1，root列指向聚集索引 B 树的顶端，如图6-2所示。索引内的每一页包含一个页首，页首后面跟着索引行。每个索引行都包含一个键值及一个指向较低级页或数据行的指针。索引的每个页称为索引结点。顶端结点称为根结点。索引的底层结点称为叶结点，叶结点包含数据页，而不仅仅是索引键值。根和叶之间的任何索引级统称为中间级。每级索引中的页链接在双向链接列表中，当到达聚集索引的叶级时，真正的数据也找到了，而不简单是一个指针。

大多数表都应该有一个聚集索引，尤其是当表只有一个索引时，它最好是聚集的。

在SQL Server中，所有的聚集索引都是唯一的。如果创建了一个聚集索引却没有指定关键词UNIQUE，SQL Server会根据需要给行增加一个唯一标识来保证索引的唯一性。

3.非聚集索引结构

非聚集索引与课本中的索引类似。数据存储在一个地方，索引存储在另一个地方，索引带有指针，指向数据的存储位置。索引中的项目按索引键值的顺序存储，而表中的信息按另一种顺序存储，非聚集索引在系统表sysindexes内的indid＞1，root列指向非聚集索引B树的顶端，如图6-3所示。非聚集索引具有完全独立于数据行的结构，使用非聚集索引不用将物理数据页中的数据按列排序。

在SQL Server中，每个表最多可以创建249个非聚集索引。

非聚集索引与聚集索引一样有B树结构，但是有两个重大区别：

（1）数据行不按非聚集索引键的顺序排列和存储。

（2）非聚集索引的叶层不包含数据页。相反，叶结点包含索引行。非聚集索引可以在有聚集索引的表、堆集或索引视图上定义。

在SQL Server中，非聚集索引中的行定位器有两种形式：

（1）如果表是堆集（没有聚集索引），行定位器就是指向行的指针。该指针用文件标识符（ID）、页码和页上的行数生成。整个指针称为行ID。

（2）如果表有聚集索引，或者索引在索引视图上，则行定位器就是行的聚集索引键。

4.扩展盘区空间的管理

索引分配映射表（IAM）页映射数据库文件中由堆集或索引使用的扩展盘区。对于任何具有ntext、text和image类型的列的表，IAM页还映射分配给这些类型的页链的扩展盘区。每个对象对每个包含扩展盘区的文件都至少有一个IAM。如果分配给对象的文件上的扩展盘区的范围超过了一个IAM页可以记录的范围，则扩展盘区可能会在文件上有多个IAM页。如图6-4所示。

IAM页按需要分配给每个对象，并在文件内随机定位。Sysindexes.dbo.FirstIAM指向对象的IAM首页，这个对象的所有IAM 页用链条链接在一起。如图6-5所示。

IAM页的页首说明IAM所映射的扩展盘区范围的起始扩展盘区。IAM中还有大位图，该位图内的每个位代表一个扩展盘区。位图的第一个位代表范围内的第一个扩展盘区，第二个位代表范围内的第二个扩展盘区，依此类推。如果一个位是0，则不将它代表的扩展盘区分配给拥有该IAM的对象。如果这个位是1，则将它代表的扩展盘区分配给拥有该IAM页的对象。

当SQL Server需要插入新行而当前页没有可用空间时，它使用IAM和PFS页查找具有足够空间容纳该行的页。SQL Server使用IAM页查找分配给对象的扩展盘区。对于每个扩展盘区，SQL Server 搜索PFS页以查看是否有一页具有足够的空间容纳这一行。每个IAM和PFS页涵盖大量数据页，因此，一个数据库内只有很少的IAM和PFS页。这意味着IAM和PFS页一般在SQL Server缓冲池的内存中，所以能很快找到它们。

SQL Server只有当无法在现有的扩展盘区内快速找到一页有足够空间容纳正插入的行时，才给对象分配新的扩展盘区。SQL Server使用按比例分配算法，从文件组内的可用扩展盘区中分配扩展盘区。如果一个文件组有两个文件，其中一个的可用空间是另一个的两倍，那么每从后者分配一页，就从前者分配两页。这意味着文件组内的每个文件应该有近似的空间使用百分比。