3.2  理解索引

在韦氏词典中，索引定义如下：

通常以字母顺序排列的某种指定资料（如作者、主题或关键字）的列表（如书目信息或对著作正文的引用）。

在数据库中，我将用更简单的方法来说明，称索引是能够以很快的速度到达数据的一种手段。尽管如此，韦氏词典的定义也还不错——即便是对于当前特定的用途而言。

或许，在韦氏词典的定义中，要指出的关键事情是使用的“通常”一词。在很多规则下，“字母顺序”的定义会发生改变。例如，在SQL Server中，有许多不同的排序选项可用。这些选项有：

l    二进制——根据字符的数字表示（例如，以ASCII表示时，空格用数字32表示，字母D是68，而字母d是100）进行排序。由于所有的事物都是数字的，因此这是最快的一种排序选择——遗憾的是，它不是人们思考问题的方式，因而实际上在WHERE子句中，可能会带来麻烦。

l    字典顺序——这种排序方式就是你在字典中看到的排序方式，不过有一点改变——可以设置许多不同的附加选项，以确定区分大小写、区分重音以及字符集选项。

理解这样的内容是相当容易的：如果告诉SQL Server注意大小写，那么A将不等于a。同样，如果告诉SQL Server不区分大小写，那么A将等同于a。当添加区分重音选项时，事情变得有点不易理解——即是说，这时SQL Server会留意变音符号，因此a与á及à均不同。排序规则不仅会影响数据是否相等，而且会影响排序的顺序（因此，会影响到在索引中存储的方式），这一点对于许多人而言则更加不易理解。

通过下面的例子，考查表中列出了几种排序规则的性质，并说明了它们对于排序顺序和相等信息有何影响。

这里的要点是，索引的顺序依赖于为数据确定的排序规则信息。排序规则可以在数据库级别和列级别设置。因此，在控制的级别上可以达到相当精细的粒度。如果想要服务器采用不区分大小写的排序规则，那么，你必须确定系统文档能处理此事，否则，就准备着接到许多技术支持电话——尤其是如果是在美国之外出售。假设你是独立软件开发商（ISV），购买你产品的客户把产品安装在现有的服务器上（对于客户来说，该服务器上的事情就像是一切合理的事情），可是，那个现有的服务器刚好是设置为区分大小写的。那么，你就等着接到非常不满意的客户打来的支持电话吧。

3.2.1  “B”还是非“B”：B树

显然，平衡树（B树）的概念不是SQL Server创建的。实际上，在数据库领域之内或之外大量的索引系统中，B树被广泛地使用着。

B树只是要提供一种一致的、成本相对较低的方法，以找到一条特定的信息。名字中的平衡非常有自我描述性——B树是自平衡的（极少有例外），即是说每当树分叉时，将近一半的数据在一边，一半的数据在另一边。在这一点上，名字中的树也很显而易见（提示：树、分枝——看出这里的倾向了吗？）——在这里使用“树”是由于：当画出结构并将其倒转时，它具有树的普遍形状。

B树从根结点（这是关于树的又一个类比，但不是最后一个）开始。如果数据量较少，根结点能够直接指向数据的实际位置。在这种情况下，整个结构看起来将像图8-2所显示的那样。

根

实际的 数据

图  8-2

那么，我们从根结点出发，开始浏览记录，直至找到最后一个起点小于我们要找寻的值的页。然后，获取到那个结点的指针，并浏览该结点，直至找到要找寻的行。

可是，多数情况下，要从根结点引用的数据实在太多了，因此，根结点指向中间结点——或者称为非叶级结点。非叶级结点位于根结点和说明数据物理存放于何处的结点之间。然后，非叶级结点能够指向其他的非叶级结点，或者指向叶级结点（最后的树的类比引用——我保证）。叶级结点是获得到真实物理数据的实际引用的结点。与叶子是沿着树的轮廓所达到的末梢很类似，顺着索引的线一直走到尽头就到达了叶级结点——从这里，能够直接到达存放了数据的实际数据结点。

如图8-3所示，我们像前面一样从根结点出发，在小于或等于要找寻值的所有值中找到最大的一个值，移动到以该值为起点的结点，同样，在下一级结点中亦如此。然后，重复这一过程——在小于或等于要找寻值的所有值中，找寻最大的一个值，寻找到以该值为起点的结点。不断重复这样的过程，沿着树一级一级地向下，直至到达叶级——从这里能够知道数据的物理位置，并能迅速导航到那里。

叶级

非叶级

根

图  8-3

页拆分——深入探讨

在读取数据方面，一切都进展顺利——但是插入数据会有点棘手。记得前面讲过，B树中的B代表平衡（balanced）。同样，你可能还记得我说过，由于每当进入树的一个分枝时，任何一边有大约一半的数据，因此B树是平衡的。有时称B树是自平衡的，因为新数据加入到树中的方式通常会防止它们变得不平衡。

当向树中加入数据时，结点最终会被填满，进而需要拆分。由于在SQL Server中，结点等同于页，因此这种拆分被称为页拆分，如图8-4所示。

当发生页拆分时，数据被自动移动以保持平衡。前面的一半数据留在旧的页中，而剩余的数据被加入到新页——这样就有了一个差不多对半的拆分，因而树依然保持平衡。

聚集键中，顺序地作为中间记录插入

由于新的记录要插入到中间，因此必须拆分页

要插入新的记录，但是页已经填满

图  8-4

考虑一下拆分的过程，会意识到在拆分时增加了大量的开销。不仅仅是插入一个页，而是：

l    创建新页；

l    把数据从现有页上移动到新页；

l    向其中一个页加入新行；

l    向父结点中加入另一个条目。

开销不会只停止在这里。由于是在树的排列中，有可能会产生一些级联的操作。当创建一个新页时（因为拆分），需要在父结点中另外加入一个条目。父结点中的条目也可能导致那一级别的页拆分，拆分的过程又全部重头开始。实际上，可能性会一直向上延伸，甚至会影响到根结点。

如果根结点发生拆分，那么，实际上最终将创建两个额外的页。因为只能有一个根结点，原来的根结点页拆分成两个页，进而成为了树中新的中间结点。然后，创建一个全新的根结点，该结点中有两个条目（一个指向旧的根结点，另一个是指向拆分页）。

勿庸讳言，页拆分会对系统的性能造成非常负面的影响。并且，在进行页拆分处理的服务器上会表现出停顿好几秒的行为（当对页进行拆分和重写时）。

在结束本章前，我们将讨论如果防止页拆分。

叶级的页拆分是极其平常的，中间结点的页拆分则少得多。随着表的增大，索引的每一级都将经历页拆分，但是，由于中间结点中的一个条目对应着下一级结点中的几个条目，因而，随着在树中级别的升高，页拆分的发生次数也越来越少。尽管如此，在叶级的上一级发生了拆分，则下一级结点必定已经进行了拆分——实际上，这意味着沿着树向上页拆分是累积的（并且在性能上的开销是昂贵的）。

SQL Server有许多不同类型的索引（很快将在后面讨论），但它们都以这样或那样的方法使用B树方法。事实上，由于B树的灵活性，它们在结构上非常相似。然而，我们仍将看到确实存在一些显著的区别，并且，它们对系统的性能会有影响。

对于SQL Server的索引而言，树的结点是以页的形式存在的，但是，实际上可以把根结点、非叶级和叶级以及树的结构应用到SQL Server之外，或者甚至应用到数据库之外的领域。

3.2.2  在SQL Server中如何访问数据

大体上，SQL Server检索请求的数据的方式只有两种：

l    使用表扫描；

l    使用索引。

SQL Server将使用哪一种方法执行特定的查询，这取决于有什么索引可用、询问的是什么列、在进行什么类型的联结以及表的大小。

1．使用表扫描

表扫描是非常直观的过程。在执行表扫描时，SQL Server从表的物理起点开始，浏览表中的每一行。当发现符合查询条件的行时，把这些行包含在结果集中。

你可能听到过很多关于表扫描不好的事情，一般来说，这是真的。然而，在某些实例中，表扫描实际上可能是最快的访问方法。典型的情况是，当从相当小的表中检索数据时就是如此。在表的大小具体为多少时表扫描会成为最快的访问方法，这将随表的宽度和查询的特定性质而有很大的差异。

看看你是否能够说明，为什么当适当的时候，在查询的WHERE子句中使用EXISTS能够极大地提升性能。当使用EXISTS运算符时，SQL Server只要一找到匹配查询条件的记录就会立刻停止查找。假如有一个有一百万条记录的表，表中第三个记录就是匹配的记录，那么，使用EXISTS选项将省却读取999 997条记录的工作量！NOT EXISTS也以同样的方式起作用。

2．使用索引

当SQL Server决定使用索引时，实际上，其处理过程与表扫描多少有些相似，只是这里有一些捷径。

在查询优化过程中，优化器考查所有可用的索引，然后选择最佳的一个（这主要基于联结和WHERE子句中指定的信息，结合SQL Server保存的关于索引组成的统计信息）。一旦选定了索引，SQL Server在索引的树结构中导航，到达匹配查询条件的数据，再提取需要的记录。区别之处在于，由于数据是排序的，因此查询引擎知道何时到达当前找寻范围的终点。于是，它能够结束查询，或者在需要时继续移动到下一级的数据范围。

思考一下迄今为止学过的查询主题（尤其是第6章），可能会注意到，索引与EXISTS选项的作用方式有惊人的相似之处。EXISTS关键字允许查询在找到匹配值后立即退出运行。由于利用索引搜索数据的过程以类似的方式进行，因而使用索引能同样或者甚至更好地改进性能——即，服务器能够了解什么时候再没有任何相关的数据存在，并能停止于此。然而，使用索引甚至能更好，因为无需局限于布尔逻辑的情形中（要找寻的数据是否存在——是或不是？）。可以在范围的开始和结束处应用同样的概念——可以把数据范围聚集在一起，本质上具有与查找数据时使用索引同样的好处。此外，能够进行非常快速的数据查找（称为SEEK），而不是在整个表中搜索数据。

不要从我对于索引与EXISTS运算符能为你做什么的比较中得出这样的印象：索引会完全取代EXISTS运算符（或相反）。两者并不是互相排斥的，它们能够一起使用，并且常常这样使用。这里把它们放在一起讲述只是因为，它们能够了解何时完成了其工作并能在抵达表的物理末尾之前退出，在这一点上它们具有相似之处。

3.2.3  索引类型和索引导航

虽然在SQL Server中名义上有两种类型的索引（聚集索引和非聚集索引），但实际上，内部说来，有3种索引类型。

l    聚集索引；

l    非聚集索引——包含：

堆上的非聚集索引；

聚集索引上的非聚集索引。

物理数据的存储方式在聚集索引和非聚集索引之间有所不同。SQL Server遍历B树到达最终数据的方式在3种索引类型之间各不相同。

所有SQL Server索引都有叶级页和非叶级页。在讨论B树时曾说过，叶级是保存标识记录的“键”的，非叶级是引导到叶级的。

索引要么构建在聚集表（有聚集索引的表）上，要么构建在堆（没有聚集索引的表）上。

l    聚集表（clusteredtable）是任何有聚集索引的表。很快将详细讨论聚集索引，不过它们对于表的意义是按照指定的顺序物理地存储数据。通过使用聚集键（clusteredkey）（定义聚集索引的列）唯一标识单独的行。

你可能会产生这样的疑问，“如果聚集索引不是唯一的，将会怎样呢？”即是说，如果聚集索引不是唯一索引，怎样才能用聚集索引唯一标识一行呢？答案是隐蔽的——SQL Server强制所有的聚集索引唯一，即使没有把聚集索引定义成唯一的。幸运的是，它强制索引唯一的方式不会改变索引的使用方式。如果你愿意，仍然能够插入重复的行，只是SQL Server将在内部为键添加后缀，以确保该行具有唯一的标识符。

l    堆（heap）是任何没有聚集索引的表。在这种情况下，将基于该行的区、页和行偏移量（从页首到该行的距离）的组合来创建唯一标识符或行ID（RID）。只有当没有聚集键可用时（没有聚集索引），RID才是必需的。

1．聚集索引

对任何指定的表来说，聚集索引（clustered index）是唯一的——每个表只能有一个聚集索引。并非一定要有聚集索引。但是，你会发现它是最经常作为第一个索引选用的索引类型，由于各种各样的原因，当查看索引类型时，那将是很明显的。

聚集索引的特殊之处在于，它的叶级是真正的数据——即是说，数据按照索引排序标准所说明的物理顺序进行排序存储。这意味着，一旦到达索引的叶级，就到达了终点——这里是真正的数据。新记录根据它在聚集索引里正确的物理顺序进行插入。创建新页的方式根据需要在哪里插入记录而变化。

当新记录必须插入到索引结构的中间时，会发生常规的页拆分。来自原来页中后半部分的记录被移动到新页上，新记录适当地插入到新的或旧的页中。

当新记录逻辑上位于索引结构的末尾时，将创建一个新页。但是，只有新记录添加到新页中，如图8-5所示。

要插入新的记录，但是页已经填充满。由于新记录是最后一条记录，因此，把它添加到全新的页中而不必扰乱已有的数据。

作为聚集键中最后一条记录的顺序插入

图  8-5

  ● 在树中导航

我在前面说过，SQL Server中的索引以B树结构存储。理论上，在作为B树分叉的每一个可能的方向上，总是有一半的剩余信息。下面来看一下聚集索引的B树的图示（图8-6）。

叶级 是数据页

根

非叶级

寻找158～400的记录

图  8-6

可以看出，它实际上与本章前面讨论的更一般的B树是一样的。在这里进行的是范围搜索（聚集索引尤为擅长此类事情），搜索158～400的数字。只需按照如下步骤进行：

导航到第一条记录，并包含进该页中所有其余的记录——之所以知道需要该页中其余的记录是因为：我们从上一级结点的信息中得知还需要来自其他页中的数据。由于这是一个有序的列表，因而能够确定它是连续的——这意味着如果下一页中有需要包含进来的记录，那么本页中其余的记录必定都要包含进来。我们能够开始从这些页中提取记录，而无需做确认方面的事情。

我们从导航到根结点开始。根据保存在名为sysindexes的系统表中的条目，SQL Server能够定位根结点。

浏览作为根结点的页，能够知道接下来要检查的页是什么（正如图中所画出的，我们要查看第二级的第二页）。然后，继续处理。随着我们沿着树一步步向下，将得到越来越小的数据子集。

最终，将会到达索引级别的叶级。在聚集索引中，到达索引的叶级意味着也到达了要找寻的行和要找寻的数据。

2．堆上的非聚集索引

堆上的非聚集索引在各方面都与聚集索引的作用方式很类似。然而，它们确实有几个显著的区别。

叶级不是数据，而是到数据的指针。指针以索引所指向的特定行的行标识符（RID）形式出现，本章前面介绍过RID，它由区、页和行偏移量组成。尽管叶级并非真正的数据（而是RID），但是，这里不过比使用聚集索引多了一步而已——因为RID包含行位置的完整信息，因而可以直接访问到数据。

然而，不要误以为“多了一步”意味着在开销上只有一点点的差别，进而误以为堆上的非聚集索引与聚集索引运行得一样快。使用聚集索引时，数据的物理顺序是索引顺序。这意味着，对于一个数据范围，当找到该范围上数据起点所在的行时，很可能该页上其他行也在范围之中（即由于记录存储在一起，因而物理上后面的记录差不多就是接下来的数据）。使用堆时，数据没有链接在一起，唯一的连接就是通过索引。从物理的观点看，这里完全没有任何形式的排序。就是说，从物理读取的观点看，系统可能要在文件中四处检索数据。实际上，十分可能（或者很可能）要花上单独的几次从同一个页中获取数据——因为数据间没有链接，所以SQL Server无法知道它将返回该物理位置。使用聚集索引时，由于知道物理的顺序，因此能够只访问一次页面就获取到所有的数据。

为了公平对待堆上的非聚集索引与聚集索引，需要说明，任何已经读过一次的页极有可能依然存在于内存缓存中，因而对其进行的检索将是非常快的。然而，它在检索数据上还是增加了另外的逻辑操作。

图8-7显示了曾在聚集索引上进行过的同样搜索，不过，这一次使用的是堆上的非聚集索引。

非叶级

数据页

根

叶级

查找从158到400的记录

图  8-7

在大多数索引导航中，这里所做的事情与以前完全一样。从同样的根结点开始，遍历树处理越来越集中的页，直至到达索引级别的叶级。此时，事情开始与以前有所不同。使用聚集索引时，就到此为止了，而使用非聚集索引时，要做更多的事情。如果非聚集索引在堆上，那么还有一个级别需要到达。从叶级页获取行标识符，然后导航到该行——直到这时方才到达了实际的数据。

聚集表上的非聚集索引

使用聚集表上的非聚集索引时，同样有相似之处，但也同样有不同之处。与堆上的非聚集索引一样，索引的非叶级看起来和聚集索引非常类似。到达叶级才出现不同之处。

在叶级，它与其他两种索引结构有显著的区别——这里还有一个索引需要查看。使用聚集索引时，到达了叶级便找到了真正的数据。使用堆上的非聚集索引时，到达叶级还没有得到真正的数据，但是，找到了引领你直达数据的标识符（只剩最后一步要走）。使用聚集表上的非聚集索引，在叶级得到的是聚集键。这就是说，在这里找到了足够的信息来使用聚集索引。

你将看到类似图8-8所示的情形。

最终得到的是两个类型完全不同的查找。

在图中的例子里，从范围查找开始——在索引中进行一个查找，并能够从浏览非聚集索引中找到满足条件（LIKE 'T%'）的连续的数据范围。这种能够直接到索引中具体的地点的查找称为seek。

然后，开始了第二种类型的查找——使用聚集索引的查找。第二种查找非常快，这里问题是它将发生多次。我们来看，SQL Server从第一个索引查找中获取了一个列表（所有以“T”开始的名字列表），但是，该列表逻辑上不以任何连续的方式与索引键匹配——必须单独查找每一条记录，如图8-9所示。

到聚集索引的位置

叶级

非叶级

根

查找FName类似 “T%”的EmployeeID

图  8-8

显然，这种多次查找的情形比起从一开始就使用聚集索引的情形，引入了更多的管理开销。第一个索引搜索（通过非聚集索引进行的搜索）只需要很少的逻辑读。

例如，如果有一个表，表中每一行为1000字节，要对该表进行与前面图中类似的查找（如返回5、6行的查找），从非聚集索引中获得信息将只需要8-10次逻辑读。然而，到此为止，只是准备好了在聚集索引中查找行。这些查找中的每一个将花费大约3-4次逻辑读。乍看上去这似乎不是什么大问题，但是，假如像下面这样考虑：

从最小3次到最大24次逻辑读——比起以前，在工作量上增加了800％。

再展开想象，假设从非聚集索引中查找的值的范围不是5、6行，而是5000或6000行，或者是500 000或600 000行——那么，在工作量上将会有巨大的影响。

别让这里比聚集索引增加的额外开销吓倒了——重点并不是要吓倒你让你远离索引的使用，而是要让你意识到，从读的观点来看，非聚集索引不会像聚集索引那样有效（实际上，某些情况下，在进行插入的时候它能够成为更好的选择）。通常（有例外的时候），任何类型的索引都是进行查找的最快的方法。在本章的后面，将说明使用什么索引以及为什么要使用这种索引。