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来访问到对应数据页中的值  。