本文關(guān)注以下方面(本文所有的討論基于SQL Server數(shù)據(jù)庫)：

• 索引的分類；
• 索引的結(jié)構(gòu)；
• 索引的存儲

一、索引定義分類

　　讓我們先來回答幾個問題：　　

• 什么是索引？
  • 索引是對數(shù)據(jù)庫表中一列或多列的值進行排序的一種結(jié)構(gòu)，使用索引可快速訪問數(shù)據(jù)庫表中的特定信息。
  • 舉個例子，索引就像我們查字典時用的按拼音或筆畫或偏旁部首
• 有哪些索引？
  • 從物理結(jié)構(gòu)上可分為兩種：聚集索引和非聚集索引 (此外還有空間索引、篩選索引、xml索引)
• 索引說明 (http://msdn.microsoft.com/zh-cn/library/ms190197(v=sql.105).aspx)
  • 每張表上最大的聚集索引數(shù)為1；
  • 每張表上最大的非聚集索引數(shù)為999；
  • 每個索引最多能包含的鍵列數(shù)為16；
  • 索引鍵記錄大小最多為900字節(jié)

二、索引數(shù)據(jù)結(jié)構(gòu)

　　在SQL Server數(shù)據(jù)庫中，索引的存儲是以B+樹（注意和二叉樹的區(qū)別）結(jié)構(gòu)來存儲的，又稱索引樹，其節(jié)點類型為如下兩種：

• 索引節(jié)點；
• 葉子節(jié)點

　　索引節(jié)點按照層級關(guān)系，有時又可以分為根節(jié)點和中間節(jié)點，其本質(zhì)是一樣的，都只包含下一層節(jié)點的入口值和入口指針；

　　葉子節(jié)點就不同了，它包含數(shù)據(jù)，這個數(shù)據(jù)可能是表中真實的數(shù)據(jù)行，也有可能是索引列值和行書簽，前者對應(yīng)于聚集索引，后者對應(yīng)于非聚集索引。

三、索引存儲結(jié)構(gòu)

　　在正式討論索引的存儲結(jié)構(gòu)之前，我們有必要先來了解一下SQL Server數(shù)據(jù)庫的存儲結(jié)構(gòu)。

　　SQL Server數(shù)據(jù)庫存儲（結(jié)構(gòu)）的最小單位是頁，大小為8K，共8 * 1024 = 8192Byte，不論是數(shù)據(jù)頁還是索引頁都是以此方式存放。實際上對于SQL Server數(shù)據(jù)庫而言，其頁（Page）類型有很多種，大概有如下十幾種（http://www.sqlnotes.info/2011/10/31/page-type/）：

• Type 1 – Data page.
  • Data records in heap
  • Clustered index leaf-level
  • Location can be random
• Type 2 – Index page
  • Non-clustered index
  • Non-leave-level clustered index
  • Location can be random

• Type 3 – Text Mixed Page
  • Small LOB value(s), multiple types and rows.
  • Location can be random
• Type 4 – Text Page
  • LOB value from a single column value
  • Location can be random
• Type 7 – Sort Page
  • Temporary page for sort Operation.
  • Usually tempdb, but can be in user database for online operations.
  • Location can be random
• Type 8 – GAM Page
  • Global Allocation Map, track allocation of extents.
  • One bit for each extent, if the bit is 1, means the extent is free, otherwise means the extent is allocated (not necessary full).
  • The first GAM page in each file is page 2
• Type 9 – SGAM Page
  • Shared Global Allocation Map, track allocation of shared extents
  • One bit for each extent, if the bit is 1, means the extent is allocated but has free space, otherwise means the extent is full
  • The first SGAM page in each file is page 3
• Type 10 – IAM Page
  • Index Allocation Map. Extent allocation in a GAM interval for an index or heap table.
  • Location can be random.
• Type 11 – PFS Page
  • Page Free Space. Byte map, keeps track of free space of pages
  • The first PFS is page 1 in each file.
• Type 13 – Boot Page
  • Information about the page
  • Only page 9 in file 1.
• Type 14 – Server Configuration Page (It may not be the official name)
  • Part of information returned from sp_configure.
  • It only exists in master database, file 1, page 10
  • SQL Server 2008 Only
• Type 15 – File Header Page
  • Information about the file.
  • It’s always page 0 every data page.
• Type 16 – Differential Changed map
  • Extents in GAM interval have changed since last full or differential backup
  • The first Differential Changed Page is page 6 in each file
• Type 17 – Bulk Change Map
  • Extents in GAM interval modified by bulk operations since last backup
  • The first Bulk Change Map page is page 7 in each file

　　表中所有數(shù)據(jù)頁的存放在磁盤上又有兩種組織方式：

• 堆表；
• 索引組織表

　　如果表中所有數(shù)據(jù)頁是以一種頁間無序、隨機存儲的方式，則稱這樣的表為堆表；

　　否則如果表中數(shù)據(jù)頁間按某種方式（如表中某個字段）有序地存儲與磁盤上，則稱為索引組織表。

四、聚集索引

　　下面我們將深入研究一下數(shù)據(jù)庫中的索引到底是如何存儲的以及如何被使用的。

　　為了測試驗證等，我們在數(shù)據(jù)庫PCT上新建一張測試表Employee，有兩個字段，其中EmployeeId為主鍵

USE PCTCREATE TABLE Employee (    EmployeeId    NVARCHAR(32) NOT NULL PRIMARY KEY,    EmployeeName NVARCHAR(40) NOT NULL,);

　　插入10W筆測試數(shù)據(jù)

SET NOCOUNT ONdeclare @i intset @i=1while @i<=100000begin INSERT INTO Employee VALUES(replace(newid(), '-', ''), 'Employee_' + CONVERT(varchar, @i) );set @i = @i+1end

　　通過DBCC IND命令來查看索引的情況

DBCC IND ([PCT], [DBO.Employee], -1)

　　結(jié)果如下

　　紅色標(biāo)記說明：

• PagePID：頁編號
• PageType：頁類型，第三部分已經(jīng)說明，1為數(shù)據(jù)頁（此處為聚集索引的葉節(jié)點），2為索引頁（此處為聚集索引的根或中間節(jié)點），10為IAM頁
• IndexLevel：標(biāo)明頁子在B樹中的位置，0為葉節(jié)點，1為中間節(jié)點，2為根節(jié)點
• NextPagePID和PrevPageID：用于標(biāo)識此頁的前一頁和后一頁，這表明每一層是一個雙向鏈表，為0則表明沒有相應(yīng)的頁

　　為了方便查找，我們也可以把上述結(jié)果存入表中，為此建表

CREATE TABLE DBCCIndResult (    PageFID NVARCHAR(200),    PagePID NVARCHAR(200),    IAMFID NVARCHAR(200),    IAMPID NVARCHAR(200),    ObjectID NVARCHAR(200),    IndexID NVARCHAR(200),    PartitionNumber NVARCHAR(200),    PartitionID NVARCHAR(200),    iam_chain_type NVARCHAR(200),    PageType NVARCHAR(200),    IndexLevel NVARCHAR(200),    NextPageFID NVARCHAR(200),    NextPagePID NVARCHAR(200),    PrevPageFID NVARCHAR(200),    PrevPagePID NVARCHAR(200))

　　插入數(shù)據(jù)

INSERT INTO DBCCIndResult EXEC ('DBCC IND(PCT,Employee,-1) ')

　　我們可以通過下面的語句來查看索引的深度

select * from sys.dm_db_index_physical_stats(db_id('PCT'),object_id('Employee'),null,null,null)

　　我們看到索引的深度為3，上面的IndexLevel分別有0，1，2也驗證了這一點。page_count為1944，但是我們上面查到的結(jié)果卻是1977，這是因為這里的語句沒有計算Index為1和2的頁（注意index_level列）

　　接下來我們看看B樹中各種節(jié)點存儲的到底是什么？

找到根節(jié)點283

select * from DBCCIndResult where pagetype = 2 and indexLevel = 2

查看頁里的數(shù)據(jù)

DBCC TRACEON (3604);GODBCC PAGE (PCT, 1, 283, 3);GO

　　從上圖，可以看出，此根節(jié)點共有31個兒子（中間節(jié)點），而且還存有主鍵值EmployeeId，那么這31個主鍵值是哪些記錄的主鍵值呢？我們繼續(xù)深入

以中間節(jié)點1863為例

DBCC TRACEON (3604);GODBCC PAGE (PCT, 1, 1863, 3);GO

　　這和根節(jié)點很類似，標(biāo)明了包含下一層的節(jié)點（共65個）和主鍵值，繼續(xù)深入

以葉節(jié)點807為例

DBCC TRACEON (3604);GODBCC PAGE (PCT, 1, 807, 3);GO

由于結(jié)果太多，我就不把所有的截圖都發(fā)出來了，但是從上面我們已經(jīng)看到了一些重要的東西

　　首先PAGE：(1:807)表明這是一個葉節(jié)點，同時也是一個數(shù)據(jù)頁，因為它存放了表里所有字段的數(shù)據(jù)（EmployeeId和EmployeeName），換句話說這兒的葉節(jié)點就是表Employee在數(shù)據(jù)庫中的存儲數(shù)據(jù)頁，也就是說聚集索引的葉節(jié)點其實就是表的數(shù)據(jù)存儲頁

　　其次我們看標(biāo)紅的EmployeeId，它就是我們在之前根節(jié)點283和中間節(jié)點1863存儲的主鍵值，而且它是位于數(shù)據(jù)存儲頁的第一個數(shù)據(jù)

　　至此我們總結(jié)如下：

• 聚集索引的根節(jié)點和中間節(jié)點是索引頁，都只包含下一層的入口指針和入口值（位于存儲位置的第一個主鍵值）；
• 聚集索引的葉節(jié)點就是數(shù)據(jù)頁。

　　為了更方便地查看葉節(jié)點的數(shù)據(jù)，我們將其存入表中

DBCC PAGE(PCT,1,807, 3) WITH TABLERESULTS

　　這種方式是以表的方式展示

　　但是這種方式也不便查找，我們索性新建表

CREATE TABLE DBCCPageResult(    ParentObject NVARCHAR(200),    Object NVARCHAR(200),    Field NVARCHAR(200),    Value NVARCHAR(200))

插入數(shù)據(jù)

INSERT INTO DBCCPageResult EXEC ('DBCC PAGE(PCT,1,807, 3) WITH TABLERESULTS')

查看EmployeeId數(shù)據(jù)

select * from DBCCPageResult where Field = 'EmployeeId'

　　注意Value，是按順序排好的，這也是聚集索引的意義了 - 把數(shù)據(jù)按順序存儲.

至此我們又可以得出：

• 聚集索引就是把數(shù)據(jù)按主鍵順序存儲；
• 因為一張表中的數(shù)據(jù)只能有一個物理順序，所以一張表只能有一個主鍵/聚集索引。

五、非聚集索引

　　在表Employee字段EmployeeName建立非聚集索引

CREATE NONCLUSTERED INDEX IX_TBL_Employee_EmployeeName     ON Employee(EmployeeName)          WITH FILLFACTOR= 30GO

　　再增加一列Pho