由于需要給同事培訓(xùn)數(shù)據(jù)庫(kù)的索引知識(shí)，就收集整理了這個(gè)系列的博客。發(fā)表在這里，也是對(duì)索引知識(shí)的一個(gè)總結(jié)回顧吧。通過(guò)總結(jié)，我發(fā)現(xiàn)自己以前很多很模糊的概念都清晰了很多。

不論是 聚集索引，還是非聚集索引，都是用B+樹(shù)來(lái)實(shí)現(xiàn)的。我們?cè)诹私膺@兩種索引之前，需要先了解B+樹(shù)。如果你對(duì)B樹(shù)不了解的話，建議參看以下幾篇文章：

BTree,B-Tree,B+Tree,B*Tree都是什么 
http://blog.csdn.net/manesking/archive/2007/02/09/1505979.aspx

B+ 樹(shù)的結(jié)構(gòu)圖:

B+ 樹(shù)的特點(diǎn):

• 所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點(diǎn)的鏈表中（稠密索引），且鏈表中的關(guān)鍵字恰好是有序的；
• 不可能在非葉子結(jié)點(diǎn)命中；
• 非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引（稀疏索引），葉子結(jié)點(diǎn)相當(dāng)于是存儲(chǔ)（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層；

B+ 樹(shù)中增加一個(gè)數(shù)據(jù)，或者刪除一個(gè)數(shù)據(jù)，需要分多種情況處理，比較復(fù)雜，這里就不詳述這個(gè)內(nèi)容了。

聚集索引（Clustered Index）

• 聚集索引的葉節(jié)點(diǎn)就是實(shí)際的數(shù)據(jù)頁(yè)
• 在數(shù)據(jù)頁(yè)中數(shù)據(jù)按照索引順序存儲(chǔ)
• 行的物理位置和行在索引中的位置是相同的
• 每個(gè)表只能有一個(gè)聚集索引
• 聚集索引的平均大小大約為表大小的5%左右

下面是兩副簡(jiǎn)單描述聚集索引的示意圖：

在聚集索引中執(zhí)行下面語(yǔ)句的的過(guò)程：

select * from table where firstName = 'Ota'

一個(gè)比較抽象點(diǎn)的聚集索引圖示：

非聚集索引 （Unclustered Index）

• 非聚集索引的頁(yè)，不是數(shù)據(jù)，而是指向數(shù)據(jù)頁(yè)的頁(yè)。
• 若未指定索引類(lèi)型，則默認(rèn)為非聚集索引
• 葉節(jié)點(diǎn)頁(yè)的次序和表的物理存儲(chǔ)次序不同
• 每個(gè)表最多可以有249個(gè)非聚集索引
• 在非聚集索引創(chuàng)建之前創(chuàng)建聚集索引（否則會(huì)引發(fā)索引重建）

在非聚集索引中執(zhí)行下面語(yǔ)句的的過(guò)程：

select * from employee where lname = 'Green'

一個(gè)比較抽象點(diǎn)的非聚集索引圖示：

什么是 Bookmark Lookup

雖然SQL 2005 中已經(jīng)不在提 Bookmark Lookup 了(換湯不換藥)，但是我們的很多搜索都是用的這樣的搜索過(guò)程，如下：
先在非聚集中找，然后再在聚集索引中找。

在 http://www.sqlskills.com/ 提供的一個(gè)例子中，就給我們演示了 Bookmark Lookup 比 Table Scan 慢的情況，例子的腳本如下：

USE CREDITgo-- These samples use the Credit database. You can download and restore the-- credit database from here:-- http://www.sqlskills.com/resources/conferences/CreditBackup80.zip-- NOTE: This is a SQL Server 2000 backup and MANY examples will work on -- SQL Server 2000 in addition to SQL Server 2005.--------------------------------------------------------------------------------- (1) Create two tables which are copies of charge:--------------------------------------------------------------------------------- Create the HEAPSELECT * INTO ChargeHeap FROM Chargego-- Create the CL TableSELECT * INTO ChargeCL FROM ChargegoCREATE CLUSTERED INDEX ChargeCL_CLInd ON ChargeCL (member_no, charge_no)go--------------------------------------------------------------------------------- (2) Add the same non-clustered indexes to BOTH of these tables:--------------------------------------------------------------------------------- Create the NC index on the HEAPCREATE INDEX ChargeHeap_NCInd ON ChargeHeap (Charge_no)go-- Create the NC index on the CL TableCREATE INDEX ChargeCL_NCInd ON ChargeCL (Charge_no)go--------------------------------------------------------------------------------- (3) Begin to query these tables and see what kind of access and I/O returns--------------------------------------------------------------------------------- Get ready for a bit of analysis:SET STATISTICS IO ON-- Turn Graphical Showplan ON (Ctrl+K)-- First, a point query (also, see how a bookmark lookup looks in 2005)SELECT * FROM ChargeHeap WHERE Charge_no = 12345goSELECT * FROM ChargeCL WHERE Charge_no = 12345go-- What if our query is less selective?-- 1000 is .0625% of our data... (1,600,000 million rows)SELECT * FROM ChargeHeap WHERE Charge_no < 1000goSELECT * FROM ChargeCL WHERE Charge_no < 1000go-- What if our query is less selective?-- 16000 is 1% of our data... (1,600,000 million rows)SELECT * FROM ChargeHeap WHERE Charge_no < 16000goSELECT * FROM ChargeCL WHERE Charge_no < 16000go--------------------------------------------------------------------------------- (4) What's the EXACT percentage where the bookmark lookup isn't worth it?--------------------------------------------------------------------------------- What happens here: Table Scan or Bookmark lookup?SELECT * FROM ChargeHeap WHERE Charge_no < 4000goSELECT * FROM ChargeCL WHERE Charge_no < 4000go-- What happens here: Table Scan or Bookmark lookup?SELECT * FROM ChargeHeap WHERE Charge_no < 3000goSELECT * FROM ChargeCL WHERE Charge_no < 3000go-- And - you can narrow it down by trying the middle ground:-- What happens here: Table Scan or Bookmark lookup?SELECT * FROM ChargeHeap WHERE Charge_no < 3500goSELECT * FROM ChargeCL WHERE Charge_no < 3500go-- And again:SELECT * FROM ChargeHeap WHERE Charge_no < 3250goSELECT * FROM ChargeCL WHERE Charge_no < 3250go-- And again:SELECT * FROM ChargeHeap WHERE Charge_no < 3375goSELECT * FROM ChargeCL WHERE Charge_no < 3375go-- Don't worry, I won't make you go through it all :)-- For the Heap Table (in THIS case), the cutoff is: 0.21%SELECT * FROM ChargeHeap  WHERE Charge_no < 3383goSELECT * FROM ChargeHeap WHERE Charge_no < 3384go-- For the Clustered Table (in THIS case), the cut-off is: 0.21%SELECT * FROM ChargeCL WHERE Charge_no < 3438SELECT * FROM ChargeCL WHERE Charge_no < 3439go

這個(gè)例子也就是 吳家震 在Teched 2007 上的那個(gè)演示例子。

小結(jié)：

這篇博客只是簡(jiǎn)單的用幾個(gè)圖表來(lái)介紹索引的實(shí)現(xiàn)方法：B+數(shù)， 聚集索引，非聚集索引，Bookmark Lookup 的信息而已。

參考資料：

表組織和索引組織
http://technet.microsoft.com/zh-cn/library/ms189051.aspx 
http://technet.microsoft.com/en-us/library/ms189051.aspx

How Indexes Work
http://manuals.sybase.com/onlinebooks/group-asarc/asg1200e/aseperf/@Generic__BookTextView/3358

Bookmark Lookup
http://blogs.msdn.com/craigfr/archive/2006/06/30/652639.aspx

Logical and Physical Operators Reference
http://msdn2.microsoft.com/en-us/library/ms191158.aspx