本文關注以下方面(本文所有的討論基于SQL Server數據庫)：

• 索引的分類；
• 索引的結構；
• 索引的存儲

一、索引定義分類

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

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

二、索引數據結構

　　在SQL Server數據庫中，索引的存儲是以B+樹（注意和二叉樹的區別）結構來存儲的，又稱索引樹，其節點類型為如下兩種：

• 索引節點；
• 葉子節點

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

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

三、索引存儲結構

　　在正式討論索引的存儲結構之前，我們有必要先來了解一下SQL Server數據庫的存儲結構。

　　SQL Server數據庫存儲（結構）的最小單位是頁，大小為8K，共8 * 1024 = 8192Byte，不論是數據頁還是索引頁都是以此方式存放。實際上對于SQL Server數據庫而言，其頁（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

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

• 堆表；
• 索引組織表

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

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

四、聚集索引

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

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

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

　　插入10W筆測試數據

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)

　　結果如下

　　紅色標記說明：

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

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

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))

　　插入數據

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，但是我們上面查到的結果卻是1977，這是因為這里的語句沒有計算Index為1和2的頁（注意index_level列）

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

找到根節點283

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

查看頁里的數據

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

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

以中間節點1863為例

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

　　這和根節點很類似，標明了包含下一層的節點（共65個）和主鍵值，繼續深入

以葉節點807為例

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

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

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

　　其次我們看標紅的EmployeeId，它就是我們在之前根節點283和中間節點1863存儲的主鍵值，而且它是位于數據存儲頁的第一個數據

　　至此我們總結如下：

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

　　為了更方便地查看葉節點的數據，我們將其存入表中

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

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

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

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

插入數據

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

查看EmployeeId數據

select * from DBCCPageResult where Field = 'EmployeeId'

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

至此我們又可以得出：

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

五、非聚集索引

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

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

　　再增加一列Pho