SQL Server 索引的底層實現概述
文章主要描述的是SQL Server 索引的底層實現，本文的關鍵字為聚集索引 非聚集索引 clustered index，你的表（Tables）中數據實際上都存儲在頁（pages）之中的除了BLOB類型的數據。如果某列的字段的類型為BLOB那么將有一個16字節的指針指向BLOB page。
頁是MS SQL Server中數據存儲的最小單位。每頁包含以行（row）為單位保存數據。一行只能存儲在一個頁中。每頁可以容納8KB的信息。因為這個原因，每行的最大值為8KB。一組相鄰的8個頁被稱為一個盤區（Extent）
堆文件和分配映射SQL Server 索引（Heap and the Index Allocation Map(IAM)）
堆文件在sysindexs表中只有一行記錄，并且其indid = 0. sysindexs.FIRSTIAM字段指向了IAM頁鏈表中一個IAM頁，IAM頁是用來管理SQL Server已經給堆文件分配的空間。MS SQL Server2000用IAM（Index Allocation Map）頁來在堆文件中導航（navigate）。
在堆文件中，數據頁（data page）和數據頁中數據沒有按照特定的順序存儲，也沒有鏈接在一起。數據頁之間唯一的邏輯鏈接是通過IAM頁中記錄來實現的。
SQL Server 索引索引結構（Index Structure）
所有的SQL Server 索引都是 B-Trees。在這種樹的頂端有一個根頁（root page），通過root page來訪問N個中級（intermediate level）頁，直到樹的底部、或葉級（leaf level）。可以通過樹中每個節點的指針從上向下掃描整個索引樹。
另外，每個索引級（index leves）（可能是intermediate leve or leaf level）都有一個頁鏈（page chain）。在一個索引中有許多intermediate level。索引樹的級數（樹的高度）與索引碼的寬度、索引類型、記錄行數和表中的頁數有關，并且索引樹的級數是影響索引性能的一個重要參數。
非聚集索引（Nonclustered Indexs）
一個非聚集索引與一本書的索引相似。數據存儲在一個地方，SQL Server 索引索引存儲在另外一個地方，可以通過索引中的指針來訪問存儲的數據。索引中的條目是按照索引碼的值按序存儲，但是表中的信息可以按照不同的順序存儲（如可以按照聚集索引存儲）。如果表中沒有創建聚集索引，那么表中的記錄就不能保證按照某種特定的順序。
與你用一本書的索引方式一樣，SQL Server2000也是先通過非聚集索引檢索到查找數據在表的位置，然后通過該位置來檢索數據。這使得非聚集索引非常適合精確匹配查詢（This makes nonclustered indexes the optimal choice for exact match queries）,因為索引條目中包含了你需要查找數據的位置信息。
如果當前的表是以聚集索引方式存儲，那么非聚集SQL Server 索引的位置信息就是聚集索引的索引碼（index key）；否則，位置信息就是row ID（RID)，每個RID由file number、page number和 slot number of row（每行記錄的槽號）。
比如，要在一個表中檢索某個employee ID（emp_id），該表已經有在emp_id列上創建了非聚集索引，SQL Server查找索引樹，找到一個索引條目包含你需要查找的emp_id,然后利用其中RID來訪問到對應數據頁中的值。
【編輯推薦】
