1.1.1 摘要 如果說要對數據庫進行優化，我們主要可以通過以下五種方法，對數據庫系統進行優化。 1. 計算機硬件調優 2. 應用程序調優 3. 數據庫索引優化 4. SQL語句優化 5....

1.1.1 摘要

如果說要對數據庫進行優化，我們主要可以通過以下五種方法，對數據庫系統進行優化。

1. 計算機硬件調優

2. 應用程序調優

3. 數據庫索引優化

4. SQL語句優化

5. 事務處理調優

在本篇博文中，我們將想大家講述數據庫中索引類型和使用場合，本文以SQL Server為例，對于其他技術平臺的朋友也是有參考價值的，只要替換相對應的代碼就行了！

索引使數據庫引擎執行速度更快，有針對性的數據檢索，而不是簡單地整表掃描（Full table scan）。

為了使用有效的索引，我們必須對索引的構成有所了解，而且我們知道在數據表中添加索引必然需要創建和維護索引表，所以我們要全局地衡量添加索引是否能提高數據庫系統的查詢性能。

本文目錄

• 介紹數據庫中的文件和文件組
• 頁和區
• 介紹索引的基本結構
• 介紹索引的兩個基本類型
• 聚集索引
• 非聚集索引
• 堆表的非聚集索引
• 聚集表的非聚集索引
• 索引的有效性

1.1.2 正文

在物理層面上，數據庫有數據文件組成，而這些數據文件可以組成文件組，然后存儲在磁盤上。每個文件包含許多區，每個區的大小為64K由八個物理上連續的頁組成（一個頁8K），我們知道頁是SQL Server數據庫中的數據存儲的基本單位。為數據庫中的數據文件（.mdf 或 .ndf）分配的磁盤空間可以從邏輯上劃分成頁（從0到n連續編號）。

頁中存儲的類型有：數據，索引和溢出。

文件和文件組

在SQL Server中，通過文件組這個邏輯對象對存放數據的文件進行管理。

圖1數據庫文件組織

在頂層是我們的數據庫，由于數據庫是由一個或多個文件組組成，而文件組是由一個或多個文件組成的??邏輯組，所以我們可以把文件組分散到不同的磁盤中，使用戶數據盡可能跨越多個設備，多個I/O 運轉，避免 I/O 競爭，從而均衡I/O負載，克服訪問瓶頸。

區和頁

如圖2所示，文件是由區組成的，而區由八個物理上連續的頁組成，由于區的大小為64K，所以每當增加一個區文件就增加64K。

圖2文件組成

頁中保存的數據類型有：表數據、索引數據、溢出數據、分配映射、頁空閑空間、索引分配等，具體如下圖所示：

表1頁中保存的數據類型

在數據頁上，數據行緊接著頁頭（標頭）按順序放置；頁頭包含標識值，如頁碼或對象數據的對象ID；數據行持有實際的數據；最后，頁的末尾是行偏移表，對于頁中的每一行，每個行偏移表都包含一個條目，每個條目記錄對應行的第一個字節與頁頭的距離，行偏移表中的條目的順序與頁中行的順序相反。

圖3數據頁

索引的基本結構

“索引（Index）提供查詢的速度”這是對索引的最基本的解釋，接下來我們將通過介紹索引的組成，讓大家對索引有更深入的理解。

索引是數據庫中的一個獨特的結構，由于它保存數據庫信息，那么我們就需要給它分配磁盤空間和維護索引表。創建索引并不會改變表中的數據，它只是創建了一個新的數據結構指向數據表；打個比方，平時我們使用字典查字時，首先我們要知道查詢單詞起始字母，然后翻到目錄頁，接著查找單詞具體在哪一頁，這時我們目錄就是索引表，而目錄項就是索引了。

當然，索引比字典目錄更為復雜，因為數據庫必須處理插入，刪除和更新等操作，這些操作將導致索引發生變化。

葉節點

假設我們磁盤上的數據是物理有序的，那么數據庫在進行插入，刪除和更新操作時，必然會導致數據發生變化，如果我們要保存數據的連續和有序，那么我們就需要移動數據的物理位置，這將增大磁盤的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查詢結果

通過上面的有聚集索引和沒有的對比，我們發現了查詢性能的差異，如果使用索引數據庫首先查找索引，而不是漫無目的的全表遍歷。

非聚集索引

在沒有聚集索引的情況下，表中的數據頁是通過堆(Heap)形式進行存儲，堆是不含聚集索引的表；SQL Server中的堆存儲是把新的數據行存儲到最后一個頁中。

非聚集索引是物理存儲不按照索引排序，非聚集索引的葉節點（Index leaf pages）包含著指向具體數據行的指針或聚集索引，數據頁之間沒有連接是相對獨立的頁。

假設我們有一個表T_Pet，它包含四個字段分別是：animal，name，sex和age，而且使用animal作為非索引列，具體SQL代碼如下：

-----------------------------------------------------------
---- Create T_Pet table in tempdb with NONCLUSTERED INDEX. 
-----------------------------------------------------------
USE tempdb

CREATE TABLE T_Pet
(
    animal    VARCHAR(20),
    [name]    VARCHAR(20),
    sex        CHAR(1),
    age        INT
)

CREATE UNIQUE  NONCLUSTERED INDEX T_PetonAnimal1_NonClterIdx ON T_Pet (animal)

圖10非聚集索引

接著我們要查詢表中animal = ‘Cat’的寵物信息，具體的SQL代碼如下：

SET STATISTICS PROFILE ON
SET STATISTICS TIME ON

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

SET STATISTICS PROFILE OFF
SET STATISTICS TIME OFF

如下圖所示，我們發現查詢計劃的最右邊有兩個步驟：RID和索引查找。由于這兩種查找方式相對于聚集索引查找要慢（Clustered Index Seek）。

 

圖11查詢計劃

首先SQL Server查找索引值，然后根據RID查找數據行，直到找到符合查詢條件的結果。

查詢執行時間：CPU 時間= 0 毫秒，占用時間= 1 毫秒

圖12查詢結果

堆表非聚集索引

由于堆是不含聚集索引的表，所以非聚集索引的葉節點將包含指向具體數據行的指針。

以前面的T_Pet表為例，假設T_Pet使用animal列作為非聚集索引，那么它的堆表非聚集索引結構如下圖所示：

圖13堆表非聚集索引

通過上圖，我們發現非聚集索引通過雙向鏈表連接，而且葉節點包含指向具體數據行的指針。

如果我們要查找animal = ‘Dog’的信息，首先我們遍歷第一層索引，然后數據庫判斷Dog屬于Cat范圍的索引，接著遍歷第二層索引，然后找到Dog索引獲取其中的保存的指針信息，根據指針信息獲取相應數據頁中的數據，接下來我們將通過具體的例子說明。

現在我們創建表employees，然后給該表添加堆表非聚集索引，具體SQL代碼如下：

USE tempdb

---- Creates a sample table.
CREATE TABLE employees (
    employee_id   NUMERIC       NOT NULL,
    first_name    VARCHAR(1000) NOT NULL,
    last_name     VARCHAR(900)  NOT NULL,
    date_of_birth DATETIME                   ,
    phone_number  VARCHAR(1000) NOT NULL,
    junk          CHAR(1000)             ,
    CONSTRAINT employees_pk PRIMARY KEY NONCLUSTERED (employee_id)
);
GO

現在我們查找employee_id = 29976的員工信息。

SELECT * 
FROM employees
WHERE employee_id = 29976

查詢計劃如下圖所示：

圖14查詢計劃

首先，查找索引值employee_id = ‘29976’的索引，然后根據RID查找符合條件的數據行；所以說，堆表索引的查詢效率不如聚集表，接下來我們將介紹聚集表的非聚集索引。

聚集表非聚集索引

當表上存在聚集索引時，任何非聚集索引的葉節點不再是包含指針值，而是包含聚集索引的索引值。

以前面的T_Pet表為例，假設T_Pet使用animal列作為非聚集索引，那么它的索引表非聚集索引結構如下圖所示：

圖15索引表非聚集索引

通過上圖，我們發現非聚集索引通過雙向鏈表連接，而且葉節點包含索引表的索引值。

如果我們要查找animal = ‘Dog’的信息，首先我們遍歷第一層索引，然后數據庫判斷Dog屬于Cat范圍的索引，接著遍歷第二層索引，然后找到Dog索引獲取其中的保存的索引值，然后根據索引值獲取相應數據頁中的數據。

接下來我們修改之前的employees表，首先我們刪除之前的堆表非聚集索引，然后增加索引表的非聚集索引，具體SQL代碼如下：

ALTER TABLE employees
    DROP CONSTRAINT employees_pk

ALTER TABLE employees 
    ADD CONSTRAINT employees_pk PRIMARY KEY CLUSTERED (employee_id)
GO 

SELECT * FROM employees
WHERE employee_id=29976

圖16查詢計劃

索引的有效性

SQL Server每執行一個查詢，首先要檢查該查詢是否存在執行計劃，如果沒有，則要生成一個執行計劃，那么什么是執行計劃呢？簡單來說，它能幫助SQL Server制定一個最優的查詢計劃。（關于查詢計劃請參考這里）

下面我們將通過具體的例子說明SQL Server中索引的使用，首先我們定義一個表testIndex，它包含三個字段testIndex，bitValue和filler，具體的SQL代碼如下：

-----------------------------------------------------------
---- Index Usefulness sample
-----------------------------------------------------------

CREATE TABLE testIndex
(
    testIndex int identity(1,1) constraint PKtestIndex primary key,
    bitValue bit,
    filler char(2000) not null default (replicate('A',2000))
)

CREATE INDEX XtestIndex_bitValue on testIndex(bitValue)
GO

INSERT INTO testIndex(bitValue)
    VALUES (0)
GO 20000 --runs current batch 20000 times.

INSERT INTO testIndex(bitValue)
    VALUES (1)
GO 10 --puts 10 rows into table with value 1

接著我們查詢表中bitValue = 0的數據行，而且表中bitValue = 0的數據有2000行。

SELECT *
FROM   testIndex
WHERE  bitValue = 0



圖17查詢計劃

現在我們查詢bitValue = 1的數據行。

SELECT *
FROM   testIndex
WHERE  bitValue = 1

圖18查詢計劃

現在我們注意到對同一個表不同數據查詢，居然執行截然不同的查詢計劃，這究竟是什么原因導致的呢？

我們可以通過使用DBCC SHOW_STATISTICS查看到表中索引的詳細使用情況，具體SQL代碼如下：

UPDATE STATISTICS dbo.testIndex
DBCC SHOW_STATISTICS('dbo.testIndex', 'XtestIndex_bitValue')
WITH HISTOGRAM

   

圖19直方圖

通過上面的直方圖，我們知道SQL Server估計bitValue = 0數據行行有約19989行，而bitValue = 1估計約21；SQL Server優化器根據數據量估算值，采取不同的執行計劃，從而到達最優的查詢性能，由于bitValue = 0數據量大，SQL Server只能提供掃描聚集索引獲取相應數據行，而bitValue = 1實際數據行只有10行，SQL Server首先通過鍵查找bitValue = 1的數據行，然后嵌套循環聯接到聚集索引獲得余下數據行。

總結

實例代碼下載

系列博文導航

• Deadlock的一些總結
• SQL Transcation的一些總結
• SQL Join的一些總結

參考

• http://msdn.microsoft.com/zh-cn/library/ms180978(v=sql.90).aspx
• http://msdn.microsoft.com/zh-cn/library/ms190969.aspx
• http://msdn.microsoft.com/zh-cn/library/ms189051(v=sql.105).aspx
• http://www.amazon.com/Pro-Server-2005-Thomas-Rizzo/dp/1590594770