SQL Server索引进阶之索引的内部结构

上一篇 / 下一篇 2012-09-14 13:57:37 / 个人分类：数据库

%{7J9W QtnL7z Q+E0　　理解索引的内部结构对于整体的理解索引是至关重要的，只有理解了索引的内部结构以及SQLServer是如何维护索引的，你才能理解数据插入，删除，更新，索引的创建、修改、删除所带来的成本。

;]@(IGYie0i0　　叶子层级和非叶子层级

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

k'x*`z-z0l i_0　　无论索引中条目是来自表行（聚集索引叶子节点），指向表行（非聚集索引叶子节点）或是指向低层级的节点（非叶子节点），索引条目都可以被称为索引行。

&]7rO p kt6sih0　　非叶子节点是叶子节点层级的上层，SQL Server使用非叶子节点来：51Testing软件测试网W3N9P5Wvs

zq K3S*c&M%N3a y0　　● 使得索引按照索引键聚集有序

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

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

H3HZg7J*@A4o0　　非叶子层级51Testing软件测试网I3b@'vkF!M

|U%`u(wL2uj.em0　　这些额外的页也就是所谓的非叶子节点，或被称为索引的节点层级，是建立在叶子层级之上的层级。非叶子层级的作用是使得SQL Server对于特定的索引进行查找时，不仅有了统一的入口页，并且不再需要扫描所有的页。51Testing软件测试网x;bv.G,wh$D

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

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

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

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

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

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

;N Cxg!J&gV} \4w0M0　　一个简单的例子

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

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

　　图例注释：

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

图1.索引的竖切图

qJ.[}1l6Gh#`.W0　　值得说明的是，上面的图只是一个样子，正常的情况下一个页中会包含远多于上面例子的行，并且页也会远远多于上面的例子。51Testing软件测试网_Y5n&G6h3@P

　　实际在页中索引条目并不是有序的，而是靠偏移指针进行定位的，这个页尾的偏移表是有序的。51Testing软件测试网W(t[v.RM

&O4Um-O[@0　　很多情况下，页中并不像上面图中所展现的那样，页之间物理上是连续的，但它们之间逻辑上是连续的，逻辑和物理上的差异被称之为碎片。

X;J'nPJ_0　　正如我们之前所说，每一个索引可以包含不止一层的中间页。51Testing软件测试网*y pK6Px

　　继续使用我们之前电话本的类比。比如你查找名为Helen Meyer的联系人，打开电话本找到第一页，对于在区间 “Fernandez， Zelda”和 “Olsen， Karl”之间的名字，去看页5：431.然后你找到431页，这页告诉你对于Kumar， Kevin”和“Nara， Alison”之间的名字，去找页5：2006。然后你找到5：2006就找到了你所需的联系人。

　　索引深度

　　索引的根页以及相关信息是存在系统表中的。每当SQL Server进行页查找时，SQL Server都会从根页开始查找，经过中间节点，直到找到叶子节点，然后从叶子中找到需要的索引条目。对于我们10亿行的表来说，从根节点到叶子节点共需要读取5层。而对图1所示的节点来说，只需要读取3次IO。

(V3Bfr O;q(rM] X0　　上面所说的层数，也被成为索引深度。取决于索引键的大小和数量。在AdventureWorks示例数据库中，没有哪个索引的层级超过3层。但对于其它索引键宽或是数据量大的表，就会有更深的层级。

　　sys.dm_db_index_physical_stats函数可以展示索引的详细信息，深度和大小。这是一个表值函数，比如下面代码我们可以找到SalesOrderDetai表相关的索引信息。51Testing软件测试网MpFj^3a4N$U

!Q;^j3lH6l#Hh c9|0

SELECT OBJECT_NAME(P.OBJECT_ID) AS 'Table' ,
        I.name AS 'Index' ,
        P.index_id AS 'IndexID' ,
        P.index_type_desc ,
        P.index_depth ,
        P.page_count
FROM    sys.dm_db_index_physical_stats(DB_ID(),
                                       OBJECT_ID('Sales.SalesOrderDetail'),
                                       NULL, NULL, NULL) P         JOIN
sys.indexes I ON I.OBJECT_ID = P.OBJECT_ID
                              AND I.index_id = P.index_id ;

　　得到的结果如图2所示。

图2.查询sys.dm_db_index_physical_stats函数得到的结果

　　通过如下代码我们可以看到更详细的层级信息51Testing软件测试网"i:x(We#l*v,_H

SELECT OBJECT_NAME(P.OBJECT_ID) AS 'Table' ,
        I.name AS 'Index' ,
        P.index_id AS 'IndexID' ,
        P.index_type_desc ,
        P.index_level ,
        P.page_count
FROM    sys.dm_db_index_physical_stats(DB_ID(),
                                       OBJECT_ID('Sales.SalesOrderDetail'), 2,
                                       NULL, 'DETAILED') P         JOIN
sys.indexes I ON I.OBJECT_ID = P.OBJECT_ID
                              AND I.index_id = P.index_id ;
　得到的结果如图3所示。

51Testing软件测试网kO8x$])Ze3N/|