聚集索引的B树结构

在SQL Server里,有2种表是以存储为基础的。有聚集索引的表叫聚集表,没有聚集索引的表叫堆表。在上一篇文章,我们讨论了堆表的特性和存储结构。在这篇文章里,我们来看下聚集表。

有聚集索引的表叫聚集表。聚集索引保存了使用B树结构的聚集键,并只能以此顺序存储实际的数据。这也是SQL Server限制一个表只能有一个聚集索引,因为物理存储顺序只能有一个。我们来看看B树结构的逻辑呈现。下图是基于AdventureWorks2008R2数据库,表SalesOrderDetail创建的。

聚集索引的B树结构
1 USE IndexDB
2 GO
3 SELECT * INTO dbo.SalesOrderDetail FROM AdventureWorks2008R2.Sales.SalesOrderDetail
4 GO
5 CREATE UNIQUE CLUSTERED INDEX ix_SalesOrderDetail ON dbo.SalesOrderDetail(SalesOrderDetailID)
聚集索引的B树结构

创建一个帮助表,并通过DBCC IND将表信息导入方便进一步分析。

聚集索引的B树结构
 1 -- Create a helper table
 2 CREATE TABLE sp_table_pages
 3 (
 4   PageFID TINYINT, 
 5   PagePID INT,   
 6   IAMFID TINYINT, 
 7   IAMPID INT, 
 8   ObjectID INT,
 9   IndexID TINYINT,
10   PartitionNumber TINYINT,
11   PartitionID BIGINT,
12   iam_chain_type VARCHAR(30),    
13   PageType TINYINT, 
14   IndexLevel TINYINT,
15   NextPageFID TINYINT,
16   NextPagePID INT,
17   PrevPageFID INT,
18   PrevPagePID int, 
19   PRIMARY KEY (PageFID, PagePID)
20 )
21 GO
22 
23 -- Write everything in a table for further analysis
24 INSERT INTO sp_table_pages EXEC('DBCC IND(IndexDB,SalesOrderDetail,-1)')
25 GO
聚集索引的B树结构

提取跟节点/索引页,中间级/索引页,叶子节点/数据页信息。

聚集索引的B树结构
 1 SELECT * FROM dbo.sp_table_pages WHERE IndexLevel=2 --根节点/索引页
 2 DBCC TRACEON(3604)
 3 DBCC PAGE(IndexDB,1,90,3)
 4 
 5 SELECT * FROM dbo.sp_table_pages WHERE IndexLevel=1 --中间级/索引页
 6 DBCC TRACEON(3604)
 7 DBCC PAGE(IndexDB,1,1864,3)
 8 DBCC TRACEON(3604)
 9 DBCC PAGE(IndexDB,1,1832,3)
10 DBCC TRACEON(3604)
11 DBCC PAGE(IndexDB,1,1808,3)
12 DBCC TRACEON(3604)
13 DBCC PAGE(IndexDB,1,1896,3)
14 
15 SELECT * FROM dbo.sp_table_pages WHERE IndexLevel=0 --叶子节点/数据页
16 DBCC TRACEON(3604)
17 DBCC PAGE(IndexDB,1,1704,3)
18 DBCC TRACEON(3604)
19 DBCC PAGE(IndexDB,1,1720,3)
20 DBCC TRACEON(3604)
21 DBCC PAGE(IndexDB,1,1752,3)
22 DBCC TRACEON(3604)
23 DBCC PAGE(IndexDB,1,1784,3)
聚集索引的B树结构

根据上述信息进行聚集索引结构示例图绘制。

聚集索引的B树结构

这张表有121317条记录。SQL Server需要3层来存储这个数据。我们根据上图来分析下页。在最高层,你可以看到只有一个页,这个叫做根页(root page)。在所有的B树结构里,都只有一个根页作为树结构的访问入口点。根层始终是最高层。在我们实例里根页有第2层索引。在根层(root level)和中间级别(intermediate level)的页叫索引页。在索引页里,SQL Server保存着聚集键(clustering key)和B树下层的入口点(页面指针)。聚集键保存的子页id,最小值保存在下层页(子页)。在指定子页上的聚集键最大值可以通过下一记录找到。例如,在根层第一条记录(Salesorderdetailid =NULL,pageid=1864),Salesorderdetailid小于等于30226可以在1864号页找到。入口(Salesorderdetailid =30226,pageid=1832))表示,salesorderdetailid值在30226与60003之间的记录可以在1832号页找到,以此类推。在那层,上一页和下一页的值将做双向链接来连接这些页。在根层因为只有一个页,所以上一页和下一页的值为0。

我们移到下一层来看,在这层有4个页。你可以在下一页和上一页里找到值,也是用来链接那层的页。这层被称为中间层(intermediate level)。中间层的个数和中间层的页数取决于表的大小和聚集键。一个大表可以有多个中间层,小表可能就没有中间层。这层的值可以和根层一样的方式读取。例如,这层的第1页的第一个入口(Salesorderdetailid =NULL,pageid=1704)表示,salesorderdetailid值小于等于72的可以在1704号页找到。

下一层是底层,称为叶子层(leaf level,index level 0)。在这层的页被称为叶子页(leaf pages)或数据页(data pages)。在这些页里,你可以找到Salesorderdetail表记录的全部数据(所有列)。换句话说,聚集索引的叶子层是实际数据存放的地方。

我们复制一张没有聚集索引的Salesorderdetail表。

1 SELECT * INTO dbo.SalesOrderDetailHeap FROM AdventureWorks2008R2.Sales.SalesOrderDetail
2 GO

我们来执行下列查询,2个查询都返回同样的结果,这里我们更关注的是IO部分。

聚集索引的B树结构
1 SET STATISTICS IO ON
2 GO
3 SELECT * FROM SalesOrderDetail WHERE SalesOrderDetailID =75
4 GO
5 SELECT * FROM SalesOrderDetailheap WHERE SalesOrderDetailID =75
聚集索引的B树结构

IO统计信息如下显示。有聚集索引的表,相比另一个表,逻辑读对它来说可以忽略不计的。
聚集索引的B树结构

我们来看看SQL如何使用聚集索引的3个逻辑读取来拿到记录的。首先我们需要找出聚集索引的根节点(root node),DBCC IND命令可以帮我们找到。

1 DBCC IND('IndexDB','SalesOrderDetail',1)

返回1501条记录,包含IAM页,一个索引页,和1499个数据页,部分结果显示如下。

聚集索引的B树结构

从输出结果,我们可以知道90页(page type 2)是根页,这个页是这个表的入口点(entry point)。我们用DBCC PAGE看下这个页。

1 DBCC traceon(3604)
2 GO
3 DBCC page('IndexDB',1,90,3) 

聚集索引的B树结构

SQL Server在子页保存聚集键的最小值,它的页号索引页里。例如,1864号页会有表salesorderdetailid列值小于等于30226的所有记录。同样,1832号页会有表salesorderdetailid列值在30226与60003之间的所有记录(30226可能在这2个页都有)。我们查找这条记录的salesorderdetailid值小于30226,所以这条记录的所有信息可以在子页1864找到。

我们用DBCC PAGE看下这个1864页。

1 DBCC traceon(3604)
2 GO
3 DBCC page('IndexDB',1,1864,3) 

输出结果包含410条记录,下面是部分结果显示。你可以参数1(最后一个参数)来运行DBCC PAGE命令来看页头。那样我们可以找到m_type=2的索引页。用我们刚才描述的方法,我们知道要找的记录(salesorderdetailid=75)可以在子页1705里找到。

聚集索引的B树结构

我们看下1704页的内容:

1 DBCC traceon(3604)
2 GO
3 DBCC page('IndexDB',1,1705,3)  with tableresults

聚集索引的B树结构

从页头部分,我们可以看到m_type是1,因此这个页是数据页,且是索引的叶子层。我们把如下输出结果一直往下翻。我们就有记录所有列的值,就是聚集索引叶子层,即实际的数据。
聚集索引的B树结构

SQL Server从聚集索引只读取3页(根页,中间层的1页,还有叶子节点的1页,即数据页)就找到了我们的记录。

我们用DBCC IND命令比较下2个表的区别(SalesOrderDetail,SalesOrderDetailHeap)

1 DBCC IND('IndexDB','SalesOrderDetail',1)
2 DBCC IND('IndexDB','SalesOrderDetailHeap',1)

SalesOrderDetailHeap表是堆表,只有1496个页;SalesOrderDetail表是聚集表,包含一个聚集索引,却有1501个页。这个多出的5页用来存储B树结构的中间级(intermediate)和根级(root)的索引页。我们当他是聚集索引的优点吧,多用5个页,却将逻辑读减少的只有3次。这个存储开销还是很划算的。 


本文转自Woodytu博客园博客,原文链接:http://www.cnblogs.com/woodytu/p/4498483.html,如需转载请自行联系原作者

上一篇:Hyper-V 3虚拟机快照之一 快照应用介绍


下一篇:编辑组策略 隐藏与限制Vista磁盘分区