SQL Server 索引内部结构:SQL Server 索引进阶 Level 10

作者David Durant,2012年1月20日

关于系列

本文属于Stairway系列:SQL Server索引进阶的一部分

索引是数据库设计的基础,并告诉开发人员使用数据库关于设计者的意图。不幸的是,当性能问题出现时,索引往往被添加为事后考虑。这里最后是一个简单的系列文章,应该使他们快速地使任何数据库专业人员“快速”

在之前的水平上,我们采取了合理的方法来指标,重点是他们能为我们做些什么。现在是时候采取物理方法,检查指标的内部结构;了解索引的内部特性导致了对索引开销的理解。只有通过了解指数结构,以及如何维持指数结构,才能了解和最大限度地减少指数创造,变动和消除的成本;和行插入,更新和删除。

因此,从这个层面开始,我们把重点放在包括指标成本和指标收益上。毕竟,最小化成本是最大化收益的一部分。并最大化您的指标的好处是这个阶梯是全部。

叶和非叶水平

任何指标的结构都由叶片和非叶片组成。尽管我们从来没有明确表示过,但以前的所有级别都集中在索引的叶级上。因此,聚集索引的叶级是表本身;每个叶级别条目是该表的一行。对于非聚集索引,每个行中包含一个条目的叶级别(除了已过滤的索引);每个条目由索引键列,可选的包含列和书签组成,这是聚集索引键列或RID(行ID)值。

索引条目也被称为索引行;无论是表行(聚簇索引叶级别条目),是指表行(非聚簇索引叶级别)还是指向较低级别(非叶级别)的页面。

非叶级别是在叶级上构建的结构,它使SQL Server能够:

  • 维护索引键序列中的索引条目。
  • 根据索引键值快速找到叶级别的行。

在1级中,我们使用电话簿作为比喻来帮助解释索引的好处。我们正在寻找“Meyer,Helen”的电话簿用户知道,入口将接近任何已排序的姓氏列表的中间,并直接跳到白页的中间以开始搜索。但是,SQL Server没有英文姓氏或其他数据的内在知识。也不会知道哪个页面是“中间”页面,除非它从头到尾遍历整个索引。所以SQL Server在索引中建立了一些额外的结构。

非叶级别

这个额外的结构称为索引的非叶级别或节点级别;并被认为是建立在叶级的顶部,而不管其页面的物理位置在哪里。它的目的是为SQL Server提供每个索引的单个页面入口点,以及从该页面到包含任何给定搜索关键字值的页面的简短遍历。

索引中的每个页面(无论其级别)都包含索引行或条目。在叶级页面中,正如我们一再看到的,每个条目都指向一个表行或者是表行。所以如果表中包含10亿行,索引的叶级将包含10亿条目。

在叶级以上的级别,即最低的非叶级;每个入口指向一个叶级页面。如果我们的10亿条目索引平均每页有100个条目,这对于其搜索关键字由几个数字,日期和代码列组成的索引是一个现实的数字;那么叶级将包含1,000,000,000 / 100 = 10,000,000个页面。反过来,最低的非叶级将包含10,000,000个条目,每个条目指向叶级页面,并且将跨越100,000个页面。

每个较高的非叶级别的页面的条目均指向下一级的页面。因此,我们下一个较高的非叶级将包含100,000个条目,并且大小为1,000页。以上级别将包含1,000个条目,并且大小为10页;上面那个只包含十个条目的条目就只有一个页面;这就是停止的地方。

位于索引顶部的独立页面称为根页面。位于根页面之下和叶级之上的索引的级别被称为中间级别。级别的编号从零开始,从叶级向上工作。因此,最低的中间级别总是等级1。

非叶级别条目仅包含索引键列和指向较低级别页面的指针。包含的列仅存在于叶级别条目中;它们不在非叶级别条目中进行。

除了根页面之外,索引中的每个页面都包含两个额外的指针。这些指针在索引序列中指向下一页和前一页,处于同一级别。生成的双向页面链使SQL Server能够以升序或降序扫描任何级别的页面。

一个简单的例子

下面的图1所示的简单图帮助说明了这种树状结构的索引。 此图表示使用以下SQL在理论Personnel.Employee表的LastName / FirstName列上创建的索引:

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

图表注释:

指向页面的指针由数据库文件编号和页码组成。 因此,指针值为5:4567指向数据库文件#5的第4567页。

大部分示例值都来自AdventureWorks数据库中的Person.Contact表。 为了说明的目的,还添加了其他一些内容。

卡尔·奥尔森是样本中最受欢迎的名字。 有很多Karl Olsens,他们的条目跨越了整个中级索引页面。

图1 - 索引的垂直切片

为了清晰起见,图表与以下方面的典型索引不同:

典型索引中每页的条目数量将大于图中所示的数量,因此,除根之外的每个级别的页面数量将大于所示的数量。尤其是,叶级将比我们的空间限制图中显示的要多得多。

实际索引的条目在页面上不排序。这是页面的条目偏移指针,提供顺序访问条目。 (有关偏移指针的更多信息,请参阅第4级 - 页面和范围。)

索引的物理顺序和逻辑顺序之间的相关性往往比图中所示的要高。索引的物理和逻辑顺序之间缺乏相关性被称为外部碎片,在第11级 - 碎片中讨论。

如前所述,一个指数可以有多个中间水平。

就好像我们的白页用户正在寻找海伦·迈耶,打开电话簿,发现第一页,只有第一页是粉红色的。在粉色页面的排序条目列表中,有一个表示“对于”费尔南德斯,塞尔达“和”奥尔森,卡尔“之间的名字见蓝色页面5:431。当我们的用户转到蓝页5:431时,该页面上的一个条目说:“Kumar,Kevin和Nara,Alison之间的名字见第5页:2006”。粉红色的页面对应于根,蓝色页面对应中间层次,白色页面是叶子。

指数深度

根页面的位置与索引的其他信息一起存储在系统表中。每当SQL Server需要访问与索引键值相匹配的索引条目时,它都会从根页面开始,并在索引中的每个级别处理一个页面,直到到达包含该索引键的条目的叶级页面。在我们的十亿行表中的例子中,五个页面读取将SQL Server从根页面转移到叶级页面及其所需的条目;在我们的图解例子中,三个阅读就足够了。在聚集索引中,该叶级别条目将是实际的数据行;在非聚集索引中,此条目将包含聚簇索引键列或RID值。

索引的级数或深度取决于索引键的大小和条目数。在AdventureWorks数据库中,没有索引的深度大于三。在具有非常大的表格或非常宽的索引键列的数据库中,可能会出现6或更大的深度。

sys.dm_db_index_physical_stats函数提供有关索引的信息,包括索引类型,深度和大小。这是一个可以查询的表值函数。清单1中显示的示例返回SalesOrderDetailtable的所有索引的摘要信息。

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;

清单1:查询sys.dm_db_index_physical_stats函数结果如图2所示。

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

相反,清单2中显示的代码请求特定索引的详细信息,即SalesOrderDetail表的表的uniqueidentifier列上的非聚集索引。 它会为每个索引级返回一行,如图3所示。

清单2:查询sys.dm_db_index_physical_stats获取详细信息。

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:查询sys.dm_db_index_physical_stats获取详细信息的结果

从图3的结果可以看出:

  • 这个指数的叶级分布在407页。
  • 唯一的中间级别只需要两页。
  • 根级一如既往,只有一个页面。

索引的非叶部分的大小通常是叶级的大小的十分之一至二百分之一;取决于哪些列包括搜索关键字,书签的大小,以及哪些(如果有的话)被包括的列被指定。换句话说,相对而言,指数非常宽泛且很短。这与大多数索引示例图不同,比如图1中的索引示例图,索引图往往比较高而且很窄。

请记住,包含的列仅适用于非聚簇索引,它们只出现在叶级别条目中;它们从较高级别的条目中被省略,这就是为什么它们不添加到非叶级别的大小。

由于聚簇索引的叶级别是该表的数据行,因此只有聚簇索引的非叶子部分是附加信息,需要额外的存储空间。无论索引是否创建,数据行都会存在。因此,创建聚集索引可能需要时间并消耗资源;但是当创建完成时,数据库中消耗的空间很少。

结论

索引的结构使SQL Server能够快速访问特定索引键值的任何条目。 一旦找到该条目,SQL Server就可以:

  • 访问该条目的行。
  • 从该点开始以升序或降序的方式遍历索引。

这种索引树结构已经使用了很长时间,甚至比关系数据库还要长,并且随着时间的推移已经证明了它自己。


本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏测试开发架构之路

MySQL/Oracle视图的创建与使用

视图是一个虚拟的表,是一个表中的数据经过某种筛选后的显示方式,视图由一个预定义的查询select语句组成。

853
来自专栏程序猿DD

10分钟让你明白MySQL是如何利用索引的

一、前言 在MySQL中进行SQL优化的时候,经常会在一些情况下,对MySQL能否利用索引有一些迷惑。 譬如: MySQL 在遇到范围查询条件的时候就停止匹配了...

3469
来自专栏杨建荣的学习笔记

一条insert语句导致的性能问题分析(二)(r8笔记第43天)

今天对之前描述的问题一条insert语句导致的性能问题分析(一) 进行了进一步的补充。 有一条insert语句的主要性能瓶颈在于insert子句中的查询语句,查...

2905
来自专栏IT技术精选文摘

10分钟让你明白MySQL是如何利用索引的

一、前言 在MySQL中进行SQL优化的时候,经常会在一些情况下,对MySQL能否利用索引有一些迷惑。 譬如: MySQL 在遇到范围查询条件的时候就停止匹配了...

2097
来自专栏杨建荣的学习笔记

通过ORA错误反思sql语句规范(r4笔记第41天)

今天快下班的时候,有个开发的同事问我一个问题,说他在客户端执行一条sql语句,里面包含子查询,如果单独执行子查询,会报"invalid identifier"...

2263
来自专栏精讲JAVA

Java面试之数据库面试题

触发器是一中特殊的存储过程,主要是通过事件来触发而被执行的。它可以强化约束,来维护数据的完整性和一致性,可以跟踪数据库内的操作从而不允许未经许可的更新和变化。可...

864
来自专栏王小雷

SAS学习笔记之《SAS编程与数据挖掘商业案例》(5)SAS宏语言、SQL过程

SAS学习笔记之《SAS编程与数据挖掘商业案例》(5)SAS宏语言、SQL过程 1. 一个SAS程序可能包含一个或几个语言成分: DATA步或PROC步 全程语...

2388
来自专栏Java技术

MySQL 清除表空间碎片

(1)表的存储会出现碎片化,每当删除了一行内容,该段空间就会变为空白、被留空,而在一段时间内的大量删除操作,会使这种留空的空间变得比存储列表内容所使用的空间更大...

774
来自专栏互联网大杂烩

小米面试经历

他是看了我写了一篇这样的博客才问的,可惜我都忘了自己写了啥!吃亏了,博客太久了,都忘记看了。链接如下: http://blog.csdn.net/zpdrea...

762
来自专栏Java帮帮-微信公众号-技术文章全总结

【数据库】MySQL进阶七、limit用法& varchar类型排序

【数据库】MySQL进阶七、 limit用法与varchar排序 limit用法 limit是mysql的语法 select * from table limi...

3316

扫码关注云+社区