在談?wù)摂?shù)據(jù)庫性能優(yōu)化的時候，通常都會提到“索引”，但很多人其實并沒有真正理解索引，也沒有搞清楚索引為什么就能加快檢索速度，以至于在實踐中并不能很好的應(yīng)用索引。事實上，索引是一種廉價而且十分有效的優(yōu)化手段，設(shè)計優(yōu)良的索引對查詢性能提升確實能起到立竿見影的效果。

相信很多讀者，都了解和使用過索引，可能也看過或者聽過”新華字典“、”圖書館“之類比較通俗描述，但是對索引的存儲結(jié)構(gòu)和本質(zhì)任然還比較迷茫。

有數(shù)據(jù)結(jié)構(gòu)和算法基礎(chǔ)的讀者，應(yīng)該都學(xué)過或者寫過“順序查找，二分查找（折半）查找，二叉樹查找”這幾種很經(jīng)典的查找算法。其中，順序查找效率是最低的，其算法復(fù)雜度為O（n），而二分查找算法復(fù)雜度為O（logn）但要求數(shù)據(jù)是必須為有序的，通常在鏈表中使用廣泛。而二叉樹查找的復(fù)雜度僅為O（log2n），但要求數(shù)據(jù)結(jié)構(gòu)為“樹”。如圖所示：

在主流的關(guān)系型數(shù)據(jù)庫中，使用和支持最廣泛的要屬B-Tree索引。為了便于理解，且考慮到大部分讀者數(shù)據(jù)結(jié)構(gòu)知識有限，讀者可以把B-Tree（或者其變種B+Tree）理解為特殊的二叉樹。雖然這并不精確，但是相信讀者看了之后，已經(jīng)大致明白了為什么通過索引查找數(shù)據(jù)會比普通的表掃描會快很多。

sqlserver中的聚集索引

聚集索引的葉子節(jié)點（最底下的節(jié)點）直接包含了數(shù)據(jù)頁。

sqlserver中的非聚集索引

在有聚集索引的表中，非聚集索引的葉子節(jié)點，包含的是聚集索引的鍵值（可以理解為聚集索引的指針）。

在沒有聚集索引的堆表中，非聚集索引包含的是RID（可以理解為數(shù)據(jù)行的指針）。

在mysql中，通常也有“聚集索引”（針對InnoDB引擎）和“非聚集索引”（針對MyIsam引擎），“主鍵索引"和”二級索引“。

mysql InnoDB引擎中的索引結(jié)構(gòu)

在主鍵索引中，葉子節(jié)點包含了數(shù)據(jù)行（數(shù)據(jù)頁），二級索引的葉子界面，存放的是主鍵索引的鍵值（指向的主鍵索引）

mysql MyIsam引擎中的索引結(jié)構(gòu)

主鍵索引與二級索引結(jié)構(gòu)上沒有太大的區(qū)別，葉子節(jié)點都保存的數(shù)據(jù)行信息（例如row number等）可以直接指向并定位到數(shù)據(jù)行

相信讀者不難看出，B-Tree索引在sqlserver和mysql中的結(jié)構(gòu)、存儲方式、原理都是大致相同的。當(dāng)然，也有很多細(xì)節(jié)和內(nèi)部實現(xiàn)上的差異。

限于筆者水平和理解有限，文中全部文字和描述等全憑筆者記憶寫出，難免出現(xiàn)錯誤，敬請熱心的讀者及時批評和指正。

由于時間有限，大部分圖片筆者畫的比較粗糙，也請讀者諒解。

本文出自http://blog.csdn.net/dinglang_2009，轉(zhuǎn)載請注明出處。