细说SQLServer索引原理

表默认只有一个分区（sql server的分区表技术，可以将表进行水平拆分，这样就会产生多个分区）。 分区里面就是存储的数据，有两种存储形式：堆或B+树，具体结构下面细说。

一、页

页是数据存储的最小单位。 页类型分为：数据页、索引页、Log_mixed_page、Lob_tree_page、IAM页面

一个数据页可以存储8K（8192字节，减去96字节的头）大小的数据。数据页里面就是数据行，数据行不能跨页。

疑问：那一行数据可以超过8K吗，超过8K不就跨页了吗？

sql server 2000会有这个限制。sql server 2005 突破了每行8K的限制 但是sql server列的大小，仍不能超过8K（比如你不能定义varchar(9000) 或者 nvarchar(5000)）；

如果一行数据超出了8K，那么超出8K的字段会存到溢出页上，原数据行上有个指针指向到溢出页。

有人可能会说 varchar(max)、nvarchar(max)、text、image这种类型，其实不然，这种类型是LOB类型。

LOB(large object)是一种用于存储大对象的数据类型，每个LOB可以有2GB。LOB列可以跨多页，并且页不一定是连续的。

区(又叫扩展区)

区(又叫扩展区)是页的集合，一个区包括了8个页，区大小是64K。 注意：这里的区，不是表分区。每个表默认只有一个表分区。

二、堆结构

堆是一个没有聚集索引的表。表中的数据不按任何字段排序。 用"索引分配映射(IAM)"页将堆的页面联系在一起。如下图所示：

堆结构

堆内的数据页和行没有任何特定的顺序；页面也不链接在一起，数据页之间唯一的逻辑连接是记录在IAM页内的信息， 页面与页面之间没有什么紧密的联系；用IAM页查找数据页集合中的每一页。 从数据存储管理上来讲，用堆去管理一个超大的表格是比较吃力的，经常使用的表格上都建立聚集索引。

可以通过扫描 IAM 页对堆进行表扫描或串行读操作来找到容纳该堆的页的扩展盘区。 因为 IAM 按扩展盘区在数据文件内存在的顺序表示它们，所以这意味着串行堆扫描连续沿每个文件进行。 使用 IAM 页设置扫描顺序还意味着堆中的行一般不按照插入的顺序返回。

三、索引

MSSQL的索引存储结构是B+树，这是一种平衡多叉树。

1.B树和B+树的区别

树状图1

B树的索引节点里面除了键值和指针之外，还有行数据。

树状图2

B+树的索引节点里面，只有键值和指针。b+树的叶节点是个双向链表，范围查找非常快速。

2.为什么B+树更适合做索引？

2.1因为页容量是固定的，所以B+树能容纳更多的索引值，那么索引深度就相对较浅，查找性能会更好。

2.2b+树叶级节点之间，是个双向链表，范围查找很快。

B+树结构：

当一个表上加了聚集索引后，其结构即成了一个B+树，数据记录成了B+树的一部分。 数据的物理顺序按索引字段的顺序来排列，因为物理排列顺序肯定是只有一种的，所以表上只能添加一个聚集索引。

聚集索引

下图是一个单字段聚集索引的存储结构图(假设是在Name上加的聚集索引)

聚集索引

聚集索引是以B树结构存储的。根节点和中间节点都是索引页，叶子节点是数据页。

当表加了聚集索引的话，数据就不是按堆存储了，而是按B树结构存储的，数据记录成了B树的一部分，是B树的叶子节点。

索引页里面包含的是索引行，索引行由索引键值和指针构成，指针指向的是下一级索引的页ID。如果下一级是数据页，则指向的就是数据页ID（不是数据行的ID）。

数据页里面包含的就是数据行，如果数据行大小超过8060字节，那么超出的部分会存到溢出页，此行数据会有一个指针指向溢出页。

上面的图有一个缺陷（页之间的关联没有标明），相同层级的索引页之间是相互关联的，是个双向链表，每个索引页都有指针指向上下一页。

数据页也是一个双向链表，都会指上一页和下一页。数据在物理上不一定是连续的，但是在逻辑上一定是连续的。所以范围查询的时候是很快的。

数据是有序的，按照聚集索引字段的顺序来排列，所以一个表只能有一个聚集索引。如上图所示最右边的数据记录很明显可以看出是按照Name升序来排列的。

B+树的查找方式：如上图数据所示，假设要查找Name=Greene的记录

 从根节点开始查找：

    >= ‘Bennet’ 且 < ‘Karsen’ 的数据  -->  进入索引页1007  （Greene的记录应该再查找此页）

    >= ‘Karsen’ 且 < ‘Smith’ 的数据    -->  进入索引页1009

    >= ‘Smith’ 且 <  xxxxxxx 的数据   -->  进入索引页1062

 再从中间节点索引页1007查找：

    >= ‘Bennet’ 且 < ‘Greane’ 的数据  -->  进入数据页1132

    >= ‘Greane’ 且 < ‘Hunter’ 的数据  -->  进入数据页1133  （Greene的记录应该再查找此页）

    >= ‘Hunter’ 且 < xxxxxxxx 的数据  -->  进入数据页1127

 最后从数据页1133中取得Name=Greene的这行记录复制代码

3.根节点的索引键值是如何决定的？

3.1根节点里面的存储索引键值是如何决定的？为什么是zhangsan，而不是lisi或者其他？

取每个数据页的第一条的索引键值，向上形成索引页。

再用最底层的每个索引页的第一条向上形成索引页，这样依次向上推，直到根节点。这样根节点的索引键值就出来了

PS：即第一条记录肯定是在根节点里面的，下面的DBCC分析也佐证了这点。

4.索引的层数如何决定的？

假设某表里1亿行数据，并且这1亿行数据刚好构成了1000万个数据页，

聚集索引字段是个Int型字段(Int类型为4字节)，一个索引页只能存储8K（8060字节）数据的：

那么数据页上层需要 4000万字节/8060字节=4963个索引页。 （因为索引指向是索引页的ID，所以数据页上层的索引只需要4000万字节）

再上一层(4963*4)/8060 = 3个索引页

再上一层1个索引页即可，至此就是根节点了。

索引的层数（即索引深度）是由索引键的大小和数量决定的。

5.组合聚集索引的结构

在索引行里会有多个索引键的值，如下图所示。下图截取自DBCC分析的内容

组合索引

5.1非聚集索引

非聚集索引和聚集索引的区别是：叶级不再是数据页，即数据不再是索引结构的一部分。

非聚集索引的叶级存储的内容是什么呢？ 可以分为两种情况来讨论：堆表上的非聚集索引、聚集表(即有聚集索引的表)上的非聚集索引 其叶级内容是不一样的。

堆上的非聚集索引

非聚集索引1

如上图所示，堆表上的非聚集索引叶级节点里，行存储的是索引键值和RID（行ID，即数据页面里面的数据行的ID）。 这种RID由索引指向的特定行的区段、页以及行偏移量构成。即叶级不是实际的数据，使用叶级也仅仅比使用聚集索引多一个步骤。 因为RID具有行的位置的全部信息，所以可以直接到达数据。差了一个步骤，实际上差别的系统开销是很大的。 因为叶级节点里只存了索引键值和RID，这意味着每个页能够包含的行比聚集索引单个页节点包含的行更多。 根据行ID，可以加载此行所在的数据页来读取数据。sql server 读取数据是以页为单位的，即使只读取一行，也要加载整个数据页

5.2B+树上的非聚集索引

非聚集索引2

如上图所示，叶级节点里存储的是，非聚集索引的键值 和 聚集索引的键值。 根据非聚集索引查询时，先根据非聚集索引的键值来一步一步定位到叶级节点里的索引行，在根据此行内的聚集索引键值，去到索引键值里面查找（也是从根节点一步一步开始查）。

注意，如果表没有聚集索引，建立了非聚集索引，那么非聚集索引使用的是行号，如果此时你又添加了聚集索引，那么所有的非聚集索引引用的RID都要改为聚集索引键。这对性能的消耗是非常大的，因此最好先建立聚集索引，在建立非聚集索引。

聚集表上的非聚集索引，叶级节点为什么不再使用RID来定位记录，而要使用聚集索引的键值来定位？

如果使用RID定位的话，如果数据页发生了页拆分，那么新拆分出来的半页数据，索引里面原来对应这个半页数据行的RID，全部要更新为新的RID。

这个过程的效率是十分低下的，因为这半页数据行的非聚集索引，一般都不是在一起的，都是分散在个索引页里面的，查找起来效率很低。 而存储聚集索引键值的话，即使聚集索引发生了数据页拆分，对非聚集索引也没有影响。

5.3优缺点

缺点：查找效率相对低下，因为非聚集索引查找完后，还得根据聚集索引查一轮。

优点：真正的数据定位是使用的聚集索引键值，而不是RID。这样发生数据页拆分时，也不用影响非聚集索引。

常见问题分析

使用索引字段查询为什么会提供效率？

因为不再是表扫描，而是使用索引查找，呈几何式提高效率

索引会使得，增、删、改的效率降低吗？具体是如何影响的？

5.4新增

对新增操作来说，效率确实会降低，因为实实在在是多了一步更新索引的操作。新增操作带来的效率影响，更多是在页拆分操作上面。

对聚集索引来说：如果聚集索引键值不是有序递增的，数据可能会在数据页的中间插入，这样会导致数据页拆分（也可能会级联向上导致各级索引页的拆分）。页拆分会导致内部碎片和外部碎片，如果外部碎片过多，范围查找时会导致顺序IO变为了随机IO(磁盘悬臂来回移动读取数据)，效率很低下。

页拆分以及向上的级联反应，确实是比较低效的，所以聚集索引字段的趋势有序是十分必要的。

对非聚集索引来说：只要聚集索引是有序的，那么数据页拆分是比较少的。但是新增的数据依然有可能导致索引页的拆分， 这种可能性无法避免，因为不可能把非聚集索引键值也设计为趋势有序递增的。

页拆分详见后面，后面再写

5.5修改

如果修改了索引字段的值，才会导致索引更新。如果没有修改索引字段的话，效率我理解应该是不会降低的

5.6删除

删除了数据，需要更新索引，从而降低效率。

PS: 对修改和删除操作来说，虽然更新索引对效率有一定影响，但是要UPDATE或DELETE一行的前提是必须找到一行，因此索引实际上对于有复杂WHERE条件的UPDATE或DELETE也有帮助的。在使用索引定位一行的有效性通常能弥补更新索引所带来的额外开销，除非索引设计不合理。

索引查询为什么有最左原则

索引查找是从最左侧的字段开始匹配的。如果一个组合索引，查询时只使用中间和后面的字段，那么是无法使用到索引的

聚集索引和非聚集索引的性能区别

非聚集索引相对于聚集索引来说，效率是较低的。 因为聚集索引在物理上是有序连贯的，范围查找时，只要找到了数据的起点，查找起来是很快速的。

非聚集索引的数据是无序的，不连贯的。范围查找时，只能根据索引一条一条去获取。但是比起无索引的全表扫描，效率还是要高很多很多。