不論是 聚集索引，還是非聚集索引，都是用B+樹來實(shí)現(xiàn)的。我們?cè)诹私膺@兩種索引之前，需要先了解B+樹。

BTree,B-Tree,B+Tree,B*Tree都是什么

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

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

（1）所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點(diǎn)的鏈表中(稠密索引)，且鏈表中的關(guān)鍵字恰好是有序的;

（2）不可能在非葉子結(jié)點(diǎn)命中;

（3）非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引(稀疏索引)，葉子結(jié)點(diǎn)相當(dāng)于是存儲(chǔ)(關(guān)鍵字)數(shù)據(jù)的數(shù)據(jù)層;

B+ 樹中增加一個(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í)行下面語句的的過程：select * from table where firstName = 'Ota'

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

align="center"

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

select * from employee where lname = 'Green'

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

什么是 Bookmark Lookup
　　雖然SQL 2005 中已經(jīng)不在提 Bookmark Lookup 了(換湯不換藥)，但是我們的很多搜索都是用的這樣的搜索過程，如下：

　　先在非聚集中找，然后再在聚集索引中找。
 

這里舉一個(gè)例子，給我們演示 Bookmark Lookup 比 Table Scan 慢的情況，例子的腳本如下：

　　USE CREDIT
　　go
　　-- 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 HEAP
　　SELECT * INTO ChargeHeap FROM Charge
　　go
　　-- Create the CL Table
　　SELECT * INTO ChargeCL FROM Charge
　　go
　　CREATE 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 HEAP
　　CREATE INDEX ChargeHeap_NCInd ON ChargeHeap (Charge_no)
　　go
　　-- Create the NC index on the CL Table
　　CREATE 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 = 12345
　　go
　　SELECT * FROM ChargeCL WHERE Charge_no = 12345
　　go
　　-- What if our query is less selective?
　　-- 1000 is .0625% of our data... (1,600,000 million rows)
　　SELECT * FROM ChargeHeap WHERE Charge_no < 1000
　　go
　　SELECT * FROM ChargeCL WHERE Charge_no < 1000
　　go
　　-- What if our query is less selective?
　　-- 16000 is 1% of our data... (1,600,000 million rows)
　　SELECT * FROM ChargeHeap WHERE Charge_no < 16000
　　go
　　SELECT * FROM ChargeCL WHERE Charge_no < 16000
　　go
　　-------------------------------------------------------------------------------
　　-- (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 < 4000
　　go
　　SELECT * FROM ChargeCL WHERE Charge_no < 4000
　　go
　　-- What happens here: Table Scan or Bookmark lookup?
　　SELECT * FROM ChargeHeap WHERE Charge_no < 3000
　　go
　　SELECT * FROM ChargeCL WHERE Charge_no < 3000
　　go
　　-- 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 < 3500
　　go
　　SELECT * FROM ChargeCL WHERE Charge_no < 3500
　　go
　　-- And again:
　　SELECT * FROM ChargeHeap WHERE Charge_no < 3250
　　go
　　SELECT * FROM ChargeCL WHERE Charge_no < 3250
　　go
　　-- And again:
　　SELECT * FROM ChargeHeap WHERE Charge_no < 3375
　　go
　　SELECT * FROM ChargeCL WHERE Charge_no < 3375
　　go
　　-- 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 < 3383
　　go
　　SELECT * FROM ChargeHeap WHERE Charge_no < 3384
　　go
　　-- For the Clustered Table (in THIS case), the cut-off is: 0.21%
　　SELECT * FROM ChargeCL WHERE Charge_no < 3438
　　SELECT * FROM ChargeCL WHERE Charge_no < 3439
　　go

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