在談論資料庫性能優化的時候，通常都會提到“索引”，但很多人其實沒有真正了解索引，并沒有搞清楚索引為什麼能加快檢索速度，以至于在實踐中并不能很好的應用索引。
事實上，索引可以說是最廉價而且十分有效一種優化手段，一般而言，設計優良的索引對查詢性能優化确實能起到立竿見影的效果。
相信很多讀者，都了解和使用過索引，可能也看過或者聽過”新華字典“、”圖書館“之類比較通俗描述，但是對索引的存儲結構和本質任然還比較迷茫。
有資料結構和算法基礎的讀者，應該都聽過或者實踐過“順序查找，二分查找（折半）查找，二叉樹查找”這幾種很常見的查找算法。其中，順序查找效率是最低的，其算法複雜度為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中的結構、存儲方式、原理都是大緻相同的。當然，也有很多細節和内部實作上的差異。
限于筆者水準和了解有限，文中全部文字和描述等全憑筆者記憶寫出，難免出現錯誤，敬請熱心的讀者及時批評和指正。
由于時間有限，大部分圖檔筆者畫的比較粗糙，也請讀者諒解。