sql索引原理
A. 資料庫索引的實現原理
資料庫索引的實現原理
一、概述資料庫索引，是資料庫管理系統中一個排序的數據結構，以協助快速查詢、更新資料庫表中數據。索引的實現通常使用B樹及其變種B+樹。在數據之外，資料庫系統還維護著滿足特定查找演算法的數據結構，這些數據結構以某種方式引用(指向)數據，這樣就可以在這些數據結構上實現高級查找演算法。這種數據結構，就是索引。其實說穿了，索引問題就是一個查找問題。二、索引的原理當我們的業務產生了大量的數據時，查找數據的效率問題也就隨之而來，所以我們可以通過為表設置索引，而為表設置索引要付出代價的：一是增加了資料庫的存儲空間，二是在插入和修改數據時要花費較多的時間(因為索引也要隨之變動)。
上圖展示了一種可能的索引方式。左邊是數據表，一共有兩列七條記錄，最左邊的是數據記錄的物理地址(注意邏輯上相鄰的記錄在磁碟上也並不是一定物理相鄰的)。為了加快Col2的查找，可以維護一個右邊所示的二叉查找樹，每個節點分別包含索引鍵值和一個指向對應數據記錄物理地址的指針，這樣就可以運用二叉查找在O(log2n)的復雜度內獲取到相應數據。索引是建立在資料庫表中的某些列的上面。在創建索引的時候，應該考慮在哪些列上可以創建索引，在哪些列上不能創建索引。一般來說，應該在這些列上創建索引：在經常需要搜索的列上，可以加快搜索的速度;在作為主鍵的列上，強制該列的唯一性和組織表中數據的排列結構;在經常用在連接的列上，這些列主要是一些外鍵，可以加快連接的速度;在經常需要根據范圍進行搜索的列上創建索引，因為索引已經排序，其指定的范圍是連續的;在經常需要排序的列上創建索引，因為索引已經排序，這樣查詢可以利用索引的排序，加快排序查詢時間;在經常使用在WHERE子句中的列上面創建索引，加快條件的判斷速度。創建索引可以大大提高系統的性能第一，通過創建唯一性索引，可以保證資料庫表中每一行數據的唯一性。第二，可以大大加快數據的檢索速度，這也是創建索引的最主要的原因。第三，可以加速表和表之間的連接，特別是在實現數據的參考完整性方面特別有意義。第四，在使用分組和排序子句進行數據檢索時，同樣可以顯著減少查詢中分組和排序的時間。第五，通過使用索引，可以在查詢的過程中，使用優化隱藏器，提高系統的性能。也許會有人要問：增加索引有如此多的優點，為什麼不對表中的每一個列創建一個索引呢?因為，增加索引也有許多不利的方面。創建索引的弊端第一，創建索引和維護索引要耗費時間，這種時間隨著數據量的增加而增加。第二，索引需要佔物理空間，除了數據表占數據空間之外，每一個索引還要佔一定的物理空間，如果要建立聚簇索引，那麼需要的空間就會更大。第三，當對表中的數據進行增加、刪除和修改的時候，索引也要動態的維護，這樣就降低了數據的維護速度。同樣，對於有些列不應該創建索引。一般來說，不應該創建索引的的這些列具有下列特點：第一，對於那些在查詢中很少使用或者參考的列不應該創建索引。這是因為，既然這些列很少使用到，因此有索引或者無索引，並不能提高查詢速度。相反，由於增加了索引，反而降低了系統的維護速度和增大了空間需求。第二，對於那些只有很少數據值的列也不應該增加索引。這是因為，由於這些列的取值很少，例如人事表的性別列，在查詢的結果中，結果集的數據行佔了表中數據行的很大比例，即需要在表中搜索的數據行的比例很大。增加索引，並不能明顯加快檢索速度。第三，對於那些定義為text, image和bit數據類型的列不應該增加索引。這是因為，這些列的數據量要麼相當大，要麼取值很少。第四，當修改性能遠遠大於檢索性能時，不應該創建索引。這是因為，修改性能和檢索性能是互相矛盾的。當增加索引時，會提高檢索性能，但是會降低修改性能。當減少索引時，會提高修改性能，降低檢索性能。因此，當修改性能遠遠大於檢索性能時，不應該創建索引。三、索引的類型根據資料庫的功能，可以在資料庫設計器中創建三種索引：唯一索引、主鍵索引和聚集索引。唯一索引唯一索引是不允許其中任何兩行具有相同索引值的索引。當現有數據中存在重復的鍵值時，大多數資料庫不允許將新創建的唯一索引與表一起保存。資料庫還可能防止添加將在表中創建重復鍵值的新數據。例如，如果在employee表中職員的姓(lname)上創建了唯一索引，則任何兩個員工都不能同姓。主鍵索引資料庫表經常有一列或列組合，其值唯一標識表中的每一行。該列稱為表的主鍵。在資料庫關系圖中為表定義主鍵將自動創建主鍵索引，主鍵索引是唯一索引的特定類型。該索引要求主鍵中的每個值都唯一。當在查詢中使用主鍵索引時，它還允許對數據的快速訪問。聚集索引在聚集索引中，表中行的物理順序與鍵值的邏輯(索引)順序相同。一個表只能包含一個聚集索引。如果某索引不是聚集索引，則表中行的物理順序與鍵值的邏輯順序不匹配。與非聚集索引相比，聚集索引通常提供更快的數據訪問速度。四、局部性原理與磁碟預讀由於存儲介質的特性，磁碟本身存取就比主存慢很多，再加上機械運動耗費，磁碟的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁碟I/O。為了達到這個目的，磁碟往往不是嚴格按需讀取，而是每次都會預讀，即使只需要一個位元組，磁碟也會從這個位置開始，順序向後讀取一定長度的數據放入內存。這樣做的理論依據是計算機科學中著名的局部性原理：當一個數據被用到時，其附近的數據也通常會馬上被使用。程序運行期間所需要的數據通常比較集中。由於磁碟順序讀取的效率很高(不需要尋道時間，只需很少的旋轉時間)，因此對於具有局部性的程序來說，預讀可以提高I/O效率。預讀的長度一般為頁(page)的整倍數。頁是計算機管理存儲器的邏輯塊，硬體及操作系統往往將主存和磁碟存儲區分割為連續的大小相等的塊，每個存儲塊稱為一頁(在許多操作系統中，頁得大小通常為4k)，主存和磁碟以頁為單位交換數據。當程序要讀取的數據不在主存中時，會觸發一個缺頁異常，此時系統會向磁碟發出讀盤信號，磁碟會找到數據的起始位置並向後連續讀取一頁或幾頁載入內存中，然後異常返回，程序繼續運行。五、B樹和B+樹數據結構1、B樹B樹中每個節點包含了鍵值和鍵值對於的數據對象存放地址指針，所以成功搜索一個對象可以不用到達樹的葉節點。成功搜索包括節點內搜索和沿某一路徑的搜索，成功搜索時間取決於關鍵碼所在的層次以及節點內關鍵碼的數量。在B樹中查找給定關鍵字的方法是：首先把根結點取來，在根結點所包含的關鍵字K1,…,kj查找給定的關鍵字(可用順序查找或二分查找法)，若找到等於給定值的關鍵字，則查找成功;否則，一定可以確定要查的關鍵字在某個Ki或Ki+1之間，於是取Pi所指的下一層索引節點塊繼續查找，直到找到，或指針Pi為空時查找失敗。2、B+樹B+樹非葉節點中存放的關鍵碼並不指示數據對象的地址指針，非也節點只是索引部分。所有的葉節點在同一層上，包含了全部關鍵碼和相應數據對象的存放地址指針，且葉節點按關鍵碼從小到大順序鏈接。如果實際數據對象按加入的順序存儲而不是按關鍵碼次數存儲的話，葉節點的索引必須是稠密索引，若實際數據存儲按關鍵碼次序存放的話，葉節點索引時稀疏索引。B+樹有2個頭指針，一個是樹的根節點，一個是最小關鍵碼的葉節點。所以 B+樹有兩種搜索方法：一種是按葉節點自己拉起的鏈表順序搜索。一種是從根節點開始搜索，和B樹類似，不過如果非葉節點的關鍵碼等於給定值，搜索並不停止，而是繼續沿右指針，一直查到葉節點上的關鍵碼。所以無論搜索是否成功，都將走完樹的所有層。B+ 樹中，數據對象的插入和刪除僅在葉節點上進行。這兩種處理索引的數據結構的不同之處：1、B樹中同一鍵值不會出現多次，並且它有可能出現在葉結點，也有可能出現在非葉結點中。而B+樹的鍵一定會出現在葉結點中，並且有可能在非葉結點中也有可能重復出現，以維持B+樹的平衡。2、因為B樹鍵位置不定，且在整個樹結構中只出現一次，雖然可以節省存儲空間，但使得在插入、刪除操作復雜度明顯增加。B+樹相比來說是一種較好的折中。3、B樹的查詢效率與鍵在樹中的位置有關，最大時間復雜度與B+樹相同(在葉結點的時候)，最小時間復雜度為1(在根結點的時候)。而B+樹的時候復雜度對某建成的樹是固定的。六、B/+Tree索引的性能分析到這里終於可以分析B-/+Tree索引的性能了。上文說過一般使用磁碟I/O次數評價索引結構的優劣。先從B-Tree分析，根據B-Tree的定義，可知檢索一次最多需要訪問h個節點。資料庫系統的設計者巧妙利用了磁碟預讀原理，將一個節點的大小設為等於一個頁，這樣每個節點只需要一次I/O就可以完全載入。為了達到這個目的，在實際實現B-Tree還需要使用如下技巧：每次新建節點時，直接申請一個頁的空間，這樣就保證一個節點物理上也存儲在一個頁里，加之計算機存儲分配都是按頁對齊的，就實現了一個node只需一次I/O。B-Tree中一次檢索最多需要h-1次I/O(根節點常駐內存)，漸進復雜度為O(h)=O(logdN)。一般實際應用中，出度d是非常大的數字，通常超過100，因此h非常小(通常不超過3)。而紅黑樹這種結構，h明顯要深的多。由於邏輯上很近的節點(父子)物理上可能很遠，無法利用局部性，所以紅黑樹的I/O漸進復雜度也為O(h)，效率明顯比B-Tree差很多。綜上所述，用B-Tree作為索引結構效率是非常高的。
B. 為了測試資料庫查詢的效率是否提升,經常使用索引來實現,請問什麼是索引 有什麼作用 原理是什麼
一、什麼是索引？
索引就像是書的目錄，是與表或者視圖關聯磁碟上的結構，可以加快從表中或者視圖中檢索行的速度。素銀中包含表或者視圖中的一行或者多列生成的鍵。這些鍵存儲在一個結構（BTree）中，使sql可以快速有效的查找與鍵值關聯的行。
二、有什麼用？即索引的優點
建立索引的行可以保證行的唯一性，生成唯一的word
建立索引可以有效的縮短數據的檢索時間
建立索引可以加快表與表之間的 連接
為用來排序或者是分組的欄位添加索引可以加快和排序順序
無索引，直接去讀表數據存放的磁碟快，督導數據緩沖區中再去查找需要的數據
有索引，先讀入索引表，通過索引表直接去找到需要數據的物理地址，並把數據讀入數據緩沖區中。
三、索引的原理
通過不斷地縮小想要獲取數據的范圍來篩選出最終想要的結果，同時把隨機的事件變成順序的事件，也就是說，有了這種索引機制，我們可以總是用同一種查找方式來鎖定數據。
C. sql非聚集索引的原理
非聚集索引可以建多個,形成B樹結構，葉級節點不包含數據頁，只包含索引行。如果表中只有非聚集索引，則每個索引行包含了非聚集索引鍵值以及行定位符（ROW ID,RID），他們指向具有該鍵值的數據行。RID由文件ID、頁編號和在頁中行的編號組成。當 INDID的值在2-250之間時，說明表中存在非聚集索引頁。SQL調用ROOT欄位的值指向非聚集索引B樹的ROOT，查找與被查詢最相近的值，根據這個值找到在非葉級節點中的頁號，在葉級節點相應的頁面中找到該值的RID，最後根據這個RID在Heap中定位所在的頁和行並返回到查詢端。
上篇文章的cityid上建立了非聚集索引，執行Select * From student Where cityid=』0101』時，查詢過程是：
1:在sysindexes表查詢INDID值為2,說明有非聚集索引；
2:從根出發，在非葉級節點中定位最接近0101的值(枝節點)，查到其位於葉級頁面的第n頁；
3:在葉級頁面的第n頁下搜尋0101的RID，其RID顯示為N∶i∶j，表示cityid欄位中名為0101的記錄位於堆的第i頁的第j行，N代表文件的ID值。
4:在堆的第 i頁第j行將該記錄返回給客戶端。
D. 資料庫索引原理
資料庫索引原理如下：
使用索引可快速訪問資料庫表中的特定信息。如果想按特定職員的姓來查找人員，則與在表中搜索所有的行相比，索引有助於更快地獲取信息。
索引的實現通常使用B樹及其變種B+樹。在數據之外，資料庫系統還維護著滿足特定查找演算法的數據結構，這些數據結構以某種方式引用（指向）數據，這樣就可以在這些數據結構上實現高級查找演算法。
(4)sql索引原理擴展閱讀：
對於有些列不應該創建索引。一般來說，不應該創建索引的的這些列具有下列特點：
1、查詢很少：
對於那些在查詢中很少使用或者參考的列不應該創建索引。這是因為，既然這些列很少使用到，因此有索引或者無索引，並不能提高查詢速度。相反，由於增加了索引，反而降低了系統的維護速度和增大了空間需求。
2、少數據值：
對於那些只有很少數據值的列也不應該增加索引。這是因為，由於這些列的取值很少，例如人事表的性別列，在查詢的結果中，結果集的數據行佔了表中數據行的很大比例，即需要在表中搜索的數據行的比例很大。增加索引，並不能明顯加快檢索速度。
3、定義類型：
對於那些定義為text, image和bit數據類型的列不應該增加索引。這是因為，這些列的數據量要麼相當大，要麼取值很少。
E. sql的索引到底是什麼能用代碼舉個例子演示下嗎
索引的作用是加快數據的檢索速度,能夠讓你更快速查找到對應的數據
create index 索引名 on 表名(列名),表示在此表中的某個列上創建一個索引,這樣在以後需要以此列作為查詢條件時速度將會快很多,所以一般我們都是將操作相對頻繁的列才會加上索引
F. 請各位老師舉例說明sql中索引的原理，以及添加索引和不添加索引的效率差
索引就相當於一本書的目錄，如果沒有目錄讓你去找一段內容，你得一頁頁翻過去，有了目錄你就可以查看目錄直接定位拉
G. 資料庫索引是什麼，有什麼用，怎麼用
1、資料庫索引是什麼，有什麼用
資料庫索引是對資料庫表中一列或多列的值進行排序的一種結構，使用索引可快速訪問資料庫表中的特定信息。如果想按特定職員的姓來查找他或她，則與在表中搜索所有的行相比，索引有助於更快地獲取信息。
索引的一個主要目的就是加快檢索表中數據的方法，亦即能協助信息搜索者盡快的找到符合限制條件的記錄ID的輔助數據結構。
2、資料庫索引的用法
當表中有大量記錄時，若要對表進行查詢，第一種搜索信息方式是全表搜索，是將所有記錄一一取出，和查詢條件進行一一對比，然後返回滿足條件的記錄，這樣做會消耗大量資料庫系統時間，並造成大量磁碟I/O操作；
第二種就是在表中建立索引，然後在索引中找到符合查詢條件的索引值，最後通過保存在索引中的ROWID（相當於頁碼）快速找到表中對應的記錄。
索引是一個單獨的、物理的資料庫結構，它是某個表中一列或若干列值的集合和相應的指向表中物理標識值的數據頁的邏輯指針清單。
(7)sql索引原理擴展閱讀：
一、索引的原理：
對要查詢的欄位建立索引其實就是把該欄位按照一定的方式排序；建立的索引只對該欄位有用，如果查詢的欄位改變，那麼這個索引也就無效了，比如圖書館的書是按照書名的第一個字母排序的，那麼你想要找作者叫張三的就不能用改索引了；還有就是如果索引太多會降低查詢的速度。
二、資料庫索引的特點：
1、避免進行資料庫全表的掃描，大多數情況，只需要掃描較少的索引頁和數據頁，而不是查詢所有數據頁。而且對於非聚集索引，有時不需要訪問數據頁即可得到數據。
2、聚集索引可以避免數據插入操作，集中於表的最後一個數據頁面。
3、在某些情況下，索引可以避免排序操作。
H. sql server 2005的索引的概述
資料庫中索引原理
實際上，您可以把索引理解為一種特殊的目錄。微軟的SQL SERVER提供了兩種索引：
聚集索引（clustered index，也稱聚類索引、簇集索引）和非聚集索引（nonclustered index，也稱非聚類索引、非簇集索引）。下面，我們
舉例來說明一下聚集索引和非聚集索引的區別：
其實，我們的漢語字典的正文本身就是一個聚集索引。比如，我們要查「安」字，就會很自然地翻開字典的前幾頁，因為「安」的拼音是「an
」，而按照拼音排序漢字的字典是以英文字母「a」開頭並以「z」結尾的，那麼「安」字就自然地排在字典的前部。如果您翻完了所有以「a」
開頭的部分仍然找不到這個字，那麼就說明您的字典中沒有這個字；同樣的，如果查「張」字，那您也會將您的字典翻到最後部分，因為「張
」的拼音是「zhang」。也就是說，字典的正文部分本身就是一個目錄，您不需要再去查其他目錄來找到您需要找的內容。
我們把這種正文內容本身就是一種按照一定規則排列的目錄稱為「聚集索引」。
如果您認識某個字，您可以快速地從自動中查到這個字。但您也可能會遇到您不認識的字，不知道它的發音，這時候，您就不能按照剛才的方
法找到您要查的字，而需要去根據「偏旁部首」查到您要找的字，然後根據這個字後的頁碼直接翻到某頁來找到您要找的字。但您結合「部首
目錄」和「檢字表」而查到的字的排序並不是真正的正文的排序方法，比如您查「張」字，我們可以看到在查部首之後的檢字表中「張」的頁
碼是672頁，檢字表中「張」的上面是「馳」字，但頁碼卻是63頁，「張」的下面是「弩」字，頁面是390頁。很顯然，這些字並不是真正的分
別位於「張」字的上下方，現在您看到的連續的「馳、張、弩」三字實際上就是他們在非聚集索引中的排序，是字典正文中的字在非聚集索引
中的映射。我們可以通過這種方式來找到您所需要的字，但它需要兩個過程，先找到目錄中的結果，然後再翻到您所需要的頁碼。
我們把這種目錄純粹是目錄，正文純粹是正文的排序方式稱為「非聚集索引」。
通過以上例子，我們可以理解到什麼是「聚集索引」和「非聚集索引」。
進一步引申一下，我們可以很容易的理解：每個表只能有一個聚集索引，因為目錄只能按照一種方法進行排序。
I. SQL SERVER 索引的工作原理
SQL 當一個新表被創建之時，系統將在磁碟中分配一段以8K為單位的連續空間，當欄位的值從內存寫入磁碟時，就在這一既定空間隨機保存，當一個8K用完的時候， SQLS指針會自動分配一個8K的空間。這里，每個8K空間被稱為一個數據頁（Page），又名頁面或數據頁面，並分配從0-7的頁號,每個文件的第0頁記錄引導信息，叫文件頭（File header）；每8個數據頁（64K）的組合形成擴展區（Extent），稱為擴展。全部數據頁的組合形成堆（Heap）。
SQLS 規定行不能跨越數據頁，所以，每行記錄的最大數據量只能為8K。這就是char和varchar這兩種字元串類型容量要限制在8K以內的原因，存儲超過 8K的數據應使用text類型，實際上，text類型的欄位值不能直接錄入和保存，它只是存儲一個指針，指向由若干8K的文本數據頁所組成的擴展區，真正的數據正是放在這些數據頁中。
頁面有空間頁面和數據頁面之分。當一個擴展區的8個數據頁中既包含了空間頁面又包括了數據或索引頁面時，稱為混合擴展（Mixed Extent）,每張表都以混合擴展開始；反之，稱為一致擴展專門保存數據及索引信息。表被創建之時，SQLS在混合擴展中為其分配至少一個數據頁面，隨著數據量的增長，SQLS可即時在混合擴展中分配出7個頁面，當數據超過8個頁面時，則從一致擴展中分配數據頁面。
空間頁面專門負責數據空間的分配和管理，包括：PFS頁面（Page free space）：記錄一個頁面是否已分配、位於混合擴展還是一致擴展以及頁面上還有多少可用空間等信息；GAM頁面（Global allocation map）和SGAM頁面(Secodary global allocation map)：用來記錄空閑的擴展或含有空閑頁面的混合擴展的位置。SQLS綜合利用這三種類型的頁面文件
在必要時為數據表創建新空間；數據頁或索引頁則專門保存數據及索引信息，SQLS使用4種類型的數據頁面來管理表或索引：它們是IAM頁、數據頁、文本/圖像頁和索引頁。
在WINDOWS 中，我們對文件執行的每一步操作，在磁碟上的物理位置只有系統（system）才知道；SQL SERVER沿襲了這種工作方式，在插入數據的過程中，不但每個欄位值在數據頁面中的保存位置是隨機的，而且每個數據頁面在「堆」中的排列位置也只有系統（system）才知道。這是為什麼呢？眾所周知，OS 之所以能管理DISK，是因為在系統啟動時首先載入了文件分配表：FAT（File Allocation Table），正是由它管理文件系統並記錄對文件的一切操作，系統才得以正常運行；同理，作為管理系統級的SQL
SERVER,也有這樣一張類似FAT的表存在，它就是索引分布映像頁：IAM（Index Allocation Map）。
IAM的存在，使SQLS對數據表的物理管理有了可能。
IAM 頁從混合擴展中分配，記錄了8個初始頁面的位置和該擴展區的位置，每個IAM頁面能管理512,000個數據頁面，如
果數據量太大，SQLS也可以增加更多的IAM頁，可以位於文件的任何位置。第一個IAM頁被稱為FirstIAM,其中記錄了以
後的IAM頁的位置。
數據頁和文本/圖像頁互反，前者保存非文本/圖像類型的數據，因為它們都不超過8K的容量，後者則只保存超過8K容
量的文本或圖像類型數據。而索引頁顧名思義，保存的是與索引結構相關的數據信息。了解頁面的問題有助我們下
一步准確理解SQLS維護索引的方式，如頁拆分、填充因子等。
二、索引的基本概念
什麼是索引呢?索引是一種特殊類型的資料庫對象，它與表有著密切的聯系。
索引是為檢索而存在的。如一些書籍的末尾就專門附有索引，指明了某個關鍵字在正文中的出現的頁碼位置，方便我們查找，但大多數的書籍只有目錄，目錄不是索引，只是書中內容的排序，並不提供真正的檢索功能。可見建立索引要單獨佔用空間；索引也並不是必須要建立的，它們只是為更好、更快的檢索和定位關鍵字而存在。
再進一步說，我們要在圖書館中查閱圖書，該怎麼辦呢？圖書館的前台有很多叫做索引卡片櫃的小櫃子，裡面分了若乾的類別供我們檢索圖書，比如你可以用書名的筆畫順序或者拼音順序作為查找的依據，你還可以從作者名的筆畫順序或拼音順序去查詢想要的圖書，反正有許多檢索方式，但有一點很明白，書庫中的書並沒有按照這些卡片櫃中的順序排列——雖然理論上可以這樣做，事實上，所有圖書的脊背上都人工的粘貼了一個特定的編號①，它們是以這個順序在排列。索引卡片中並沒有指明這本書擺放在書庫中的第幾個書架的第幾本，僅僅指明了這個特定的編號。管理員則根據這一編號將請求的圖書返回到讀者手中。這是很形象的例子，以下的講解將會反復用到它。
SQLS 在安裝完成之後，安裝程序會自動創建master、model、tempdb等幾個特殊的系統資料庫，其中master是SQLS的
主資料庫，用於保存和管理其它系統資料庫、用戶資料庫以及SQLS的系統信息，它在SQLS中的地位與WINDOWS下的注冊表相當。
master中有一個名為sysindexes的系統表，專門管理索引。SQLS查詢數據表的操作都必須用到它，毫無疑義，它是本文主角之一。查看一張表的索引屬性，可以在查詢分析器中使用以下命令：select * from sysindexes where id=object_id(『tablename』)；而要查看錶的索引所佔空間的大小，可以使用系統存儲過程命令：sp_spaceused tablename，其中參數tablename為被索引的表名。
三、平衡樹
如果你通過書後的索引知道了一個關鍵字所在的頁碼，你有可能通過隨機的翻尋，最終到達正確的頁碼。但更科學更快捷的方法是：首先把書翻到大概二分之一的位置，如果要找的頁碼比該頁的頁碼小，就把書向前翻到四分之一處，否則，就把書向後翻到四分之三的地方，依此類推，把書頁續分成更小的部分，直至正確的頁碼。這叫「兩分法」，微軟在官方教程MOC里另有一種說法：叫B樹（B-Tree，Balance Tree），即平衡樹。
一個表索引由若干頁面組成，這些頁面構成了一個樹形結構。B 樹由「根」（root）開始，稱為根級節點，它通過指向另外兩個頁，把一個表的記錄從邏輯上分成兩個部分：「枝」—--非葉級節點（Non-Leaf Level）；而非葉級節點又分別指向更小的部分：「葉」——葉級節點（Leaf Level）。根節點、非葉級節點和葉級節點都位於索引頁中，統稱為索引節點，屬於索引頁的范籌。這些「枝」、「葉」最終指向了具體的數據頁（Page）。在根級節點和葉級節點之間的葉又叫數據中間頁。
「根」（root）對應了sysindexes表的Root欄位，其中記載了非葉級節點的物理位置（即指針）；非葉級節點位於根
節點和葉節點之間，記載了指向葉級節點的指針；而葉級節點則最終指向數據頁。這就是「平衡樹」。
四、聚集索引和非聚集索引
從形式上而言，索引分為聚集索引（Clustered Indexes）和非聚集索引（NonClustered Indexes）。
聚集索引相當於書籍脊背上那個特定的編號。如果對一張表建立了聚集索引，其索引頁中就包含著建立索引的列的值（下稱索引鍵值），那麼表中的記錄將按照該索引鍵值進行排序。比如，我們如果在「姓名」這一欄位上建立了聚集索引，則表中的記錄將按照姓名進行排列；如果建立了聚集索引的列是數值類型的，那麼記錄將按照該鍵值的數值大小來進行排列。
非聚集索引用於指定數據的邏輯順序，也就是說，表中的數據並沒有按照索引鍵值指定的順序排列，而仍然按照插入記錄時的順序存放。其索引頁中包含著索引鍵值和它所指向該行記錄在數據頁中的物理位置，叫做行定位符（RID：Row ID）。好似書後面的的索引表，索引表中的順序與實際的頁碼順序也是不一致的。而且一本書也許有多個索引。比如主題索引和作者索引。
SQL Server在默認的情況下建立的索引是非聚集索引，由於非聚集索引不對表中的數據進行重組，而只是存儲索引鍵
值並用一個指針指向數據所在的頁面。一個表如果沒有聚集索引時,理論上可以建立249個非聚集索引。每個非聚集索引提供訪問數據的不同排序順序。