sqlserver 索引的一些总结（2）

叶节点

假设我们磁盘上的数据是物理有序的，那么数据库在进行插入，删除和更新操作时，必然会导致数据发生变化，如果我们要保存数据的连续和有序，那么我们就需要移动数据的物理位置，这将增大磁盘的I/O，使得整个数据库运行非常缓慢；使用索引的主要目的是使数据逻辑有序，使数据独立于物理有序存储。

为了实现数据逻辑有序，索引使用双向链表的数据结构来保持数据逻辑顺序，如果要在两个节点中插入一个新的节点只需修改节点的前驱和后继，而且无需修改新节点的物理位置。

双向链表（Doubly linked list）也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

理论上说，从双向链表中删除一个元素操作的时间复杂度是O(1)，如果希望删除一个具体有给定关键字的元素，那么最坏的情况下的时间复杂度为O(n)。

在删除的过程中，我们只需要将要删除的节点的前节点和后节点相连，然后将要删除的节点的前节点和后节点置为null即可。
代码如下:


//伪代码
node.prev.next=node.next;
node.next.prev=node.prev;
node.prev=node.next=null;


图4索引的叶节点和相应的表数据

如上图4所示，索引叶节点包含索引值和相应的RID（ROWID），而且叶节点通过双向链表有序地连接起来；同时我们主要到数据表不同于索引叶节点，表中的数据无序存储，它们不全是存储在同一表块中，而且块之间不存在连接。

总的来说，索引保存着具体数据的物理地址值。

索引的类型

我们知道索引的类型有两种：聚集索引和非聚集索引。
聚集索引：物理存储按照索引排序。
非聚集索引：物理存储不按照索引排序。

聚集索引

聚集索引的数据页是物理有序地存储，数据页是聚集索引的叶节点，数据页之间通过双向链表的形式连接起来，而且实际的数据都存储在数据页中。当我们给表添加索引后，表中的数据将根据索引进行排序。
假设我们有一个表T_Pet，它包含四个字段分别是：animal，name，sex和age，而且使用animal作为索引列，具体SQL代码如下： 

代码如下:


-----------------------------------------------------------
---- Create T_Pet table in tempdb.
-----------------------------------------------------------
USE tempdb
CREATE TABLE T_Pet
(
animal VARCHAR(20),
[name] VARCHAR(20),
sex CHAR(1),
age INT
)
CREATE UNIQUE CLUSTERED INDEX T_PetonAnimal1_ClterIdx ON T_Pet (animal)


-----------------------------------------------------------
---- Insert data into data table.
-----------------------------------------------------------

代码如下:


DECLARE @i int
SET @i=0
WHILE(@i<1000000)
BEGIN
INSERT INTO T_Pet (
animal,
[name],
sex,
age
)
SELECT [dbo].random_string(11) animal,
[dbo].random_string(11) [name],
'F' sex,
cast(floor(rand()*5) as int) age
SET @i=@i+1
END
INSERT INTO T_Pet VALUES('Aardark', 'Hello', 'F', 1)
INSERT INTO T_Pet VALUES('Cat', 'Kitty', 'F', 2)
INSERT INTO T_Pet VALUES('Horse', 'Ma', 'F', 1)
INSERT INTO T_Pet VALUES('Turtles', 'SiSi', 'F', 4)
INSERT INTO T_Pet VALUES('Dog', 'Tomma', 'F', 2)
INSERT INTO T_Pet VALUES('Donkey', 'YoYo', 'F', 3)



图5聚集索引

如上图5所示，从左往右的第一和第二层是索引页，第三层是数据页（叶节点），数据页之间通过双向链表连接起来，而且数据页中的数据根据索引排序；假设，我们要查找名字（name）为Xnnbqba的动物Ifcey，这里我们以animal作为表的索引，所以数据库首先根据索引查找，当找到索引值animal = ‘Ifcey时，接着查找该索引的数据页（叶节点）获取具体数据。具体的查询语句如下：

代码如下:


SET STATISTICS PROFILE ON
SET STATISTICS TIME ON

SELECT animal, [name], sex, age
FROM T_Pet
WHERE animal = 'Ifcey'

SET STATISTICS PROFILE OFF
SET STATISTICS TIME OFF


当我们执行完SQL查询计划时，把鼠标指针放到“聚集索引查找”上，这时会出现如下图信息，我们可以查看到一个重要的信息Logical Operation——Clustered Index Seek，SQL查询是直接根据聚集索引获取记录，查询速度最快。

图6查询计划

从下图查询结果，我们发现查询步骤只有2步，首先通过Clustered Index Seek快速地找到索引Ifcey，接着查询索引的叶节点（数据页）获取数据。

查询执行时间：CPU 时间= 0 毫秒，占用时间= 1 毫秒。

图7查询结果

现在我们把表中的索引删除，重新执行查询计划，这时我们可以发现Logical Operation已经变为Table Scan，由于表中有100万行数据，这时查询速度就相当缓慢。

图8查询计划

从下图查询结果，我们发现查询步骤变成3步了，首先通过Table Scan查找animal = ‘Ifcey'，在执行查询的时候，SQL Server会自动分析SQL语句，而且它估计我们这次查询比较耗时，所以数据库进行并发操作加快查询的速度。

查询执行时间：CPU 时间= 329 毫秒，占用时间= 182 毫秒。

图9查询结果

通过上面的有聚集索引和没有的对比，我们发现了查询性能的差异，如果使用索引数据库首先查找索引，而不是漫无目的的全表遍历。