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

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

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

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

sqlserver中的聚集索引

聚集索引的葉子節點（最底下的節點）直接包含了數據頁。

sqlserver中的非聚集索引

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

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

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

mysql InnoDB引擎中的索引結構

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

mysql MyIsam引擎中的索引結構

主鍵索引與二級索引結構上沒有太大的區別，葉子節點都保存的數據行信息（例如row number等）可以直接指向并定位到數據行

相信讀者不難看出，B-Tree索引在sqlserver和mysql中的結構、存儲方式、原理都是大致相同的。當然，也有很多細節和內部實現上的差異。

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

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

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