理解索引的内部结构对于整体的理解索引是至关重要的,只有理解了索引的内部结构以及SQL Server是如何维护索引的,你才能理解数据插入,删除,更新,索引的创建、修改、删除所带来的成本。

  叶子层级和非叶子层级

  所有的索引都是由叶子层级和非叶子层级组成的。前面的文章主要关注了索引的叶子层级。对于聚集索引来说,叶子节点是索引本身,每一个叶子节点所包含的条目其实是表中的行。对于非聚集索引来说,叶子节点每一个叶子包含的一行是一个条目。每一个条目由索引键列,可选的包含列以及书签构成,而书签又由聚集索引键或RID构成。

  无论索引中条目是来自表行(聚集索引叶子节点),指向表行(非聚集索引叶子节点)或是指向低层级的节点(非叶子节点),索引条目都可以被称为索引行。

  非叶子节点是叶子节点层级的上层,SQL Server使用非叶子节点来:

  ● 使得索引按照索引键聚集有序

  ● 根据索引键快速找到叶子节点

  在本系列第一篇文章中,我们使用电话本的类比来解释为什么索引能够带来性能的提升。用户知道电话本是按照姓氏进行排序的,因此如果需要找”Meyer, Helen”根据首字母M知道这个人大概在电话本的中间位置,用户直接翻开大约一半电话本开始查找。但对于SQL Server来说,可并不知道什么是按字母表排序,也不知道哪一些页是所谓的中间页,除非把索引中的所有页扫描一遍。为了不用扫描所有的页来找到所需条目,SQL Server为在叶子节点之上增加了额外的页。

  非叶子层级

  这些额外的页也是所谓的非叶子节点,或被称为索引的节点层级,是建立在叶子层级之上的层级。非叶子层级的作用是使得SQL Server对于特定的索引进行查找时,不仅有了统一的入口页,并且不再需要扫描所有的页。

  在索引中的所有页,无论哪个层级,都包含索引条目。正如文章中不断重复说的,对于聚集索引来说,叶子节点的条目包含实际的行,所以如果一个表中包含了10亿行,那么叶子节点包含了10亿个条目。

  在叶子节点之上的层级,也是非叶子节点的底层,非叶子节点的底层每一个索引条目都指向叶子节点。如果说表中每一页能容纳100个条目,那么刚才的十亿行需要1000000000/100=1000万个页,与之对应的是,那么底层的非叶子节点包含了1000万的条目,也是分布在1000万/100=10万个页中。(译者注:原作者这里没说全,通常来说非叶子节点只包含索引键,因此每个条目的大小会远远小于叶子节点的条目大小,因此每页可以容纳更多的行,所以这里非叶子节点应该远远小于10W个页,后面的段落我们先不管这个,还是按照10W个页算)。

  再上一层的非叶子节点包含了指向这10万个页的条目,也是10万个条目,这10W个索引条目分布在10万/1000=1000页中。根据这个规律,我们知道再上一层包含10个页,直至上层的节点只有一个页了。

  索引中上层的节点被称为根页。剩下的除了根页和叶子之外的层级是所谓的中间层级。层级的编号是从叶子节点以0开始向上增长的,因此中间层级是以1开始的。

  非叶子节点仅仅包含索引键,对于拥有包含列的索引来说,包含列仅仅存在于叶子节点。

  索引中的页,除了根页之外,都含有两个额外的指针,分别指向按照索引顺序当前页之前和之后的页。这种双向链表结构使得SQL Server在索引扫描的时候更加有效。

  一个简单的例子

  让我们通过一个简单的图示来真正理解索引的内部结构吧,如下图1所示。我们在Personnel.Employee表上创建了一个非聚集索引,代码如下:

 

CREATE NONCLUSTERED INDEX IX_Full_Name ON Personnel.Employee ( LastName,
FirstName, ) GO

  图例注释:

  指向页的指针包含了文件号和页号。比如说5:4567指向的是第5个文件的4567个页。

图1.索引的竖切图