[学习笔记]数据库索引
参考资料：
《How does database indexing work?》
《Sql Server 2005 性能调校》
数据库中为什么需要索引
When data is stored on disk based storage devices, it is stored as blocks of data. These blocks are accessed in their entirety, making them the atomic disk access operation. Disk blocks are structured in much the same way as linked lists; both contain a section for data, a pointer to the location of the next node (or block), and both need not be stored contiguously.
Due to the fact that a number of records can only be sorted on one field, we can state that searching on a field that isn’t sorted requires a Linear Search which requires N/2 block accesses, where N is the number of blocks that the table spans. If that field is a non-key field (i.e. doesn’t contain unique entries) then the entire table space must be searched at N block accesses.
Whereas with a sorted field, a Binary Search may be used, this has log2 N block accesses. Also since the data is sorted given a non-key field, the rest of the table doesn’t need to be searched for duplicate values, once a higher value is found. Thus the performance increase is substantial.
Indexing is a way of sorting a number of records on multiple fields. Creating an index on a field in a table creates another data structure which holds the field value, and pointer to the record it relates to. This index structure is then sorted, allowing Binary Searches to be performed on it.
The downside to indexing is that these indexes require additional space on the disk, since the indexes are stored together in a MyISAM database, this file can quickly reach the size limits of the underlying file system if many fields within the same table are indexed.
索引的结构
大型的关系型数据库都会有各种索引功能，其构造就是提取数据表中一个以上的字段独立存放在数据表之外的另一个结构中，在SQLServer中是以 B+数 结构来生成索引，从而更方便地寻找数据。
关于B+树，可以参考《从B树、B+树、B*树谈到R 树》一文。
B+数中的结点分为两种，Leaf-Level和Non-Leaf-Level，Non-Leaf-Level存储的是其下层的一些基本信息和指针，经由一层一层的Nod-Leaf-Level结点导航到Leaf-Level结点，而Leaf-Level结点则按照某字段被索引的顺序包含了每行数据的一些内容，说是“一些”而非“全部”内容，是因为当该索引为“非聚集索引”时，该索引的Leaf-Level结点中只存储了键值和该键值所在的数据行的指针，而当该索引为聚集索引时，该索引的Leaf-Level结点中才存储了某些行的“所有数据内容”。当然一个Leaf-Level结点中可以存放不止一行数据表中的数据。
SqlServer用来做索引的键最好定义一下长度限制，在满足系统实际需求的情况下，键长度越小越好，键的长度小意味着一个分页能够存放更多的键值记录。
聚集索引与非聚集索引
集群索引指的是数据表本身就是索引的一部分，即数据表本身就是集群索引的Leaf-Level，整个数据表的摆放顺序是按照你选定的键值由小到大排序。
因为数据表表内实际摆放数据的方式只能遵循一种顺序，所以一个数据表只能有一个聚集索引。
当你要做如下语句时： SELECT＊FROM ＜tablename＞ WHERE <fieldname><condition>, 由于是以 * 来选择数据表中所有的字段，则该where条件中的filedname就适合用来建立聚集索引，这样该select语句执行时，就在该字段所建立起来的索引B+树中去找那些键值符合where条件叶结点，找到这些叶节点之后，直接将其读入内存、整理并返回结果就行。
聚集索引与主键没有什么关系，可能因为数据表内只有一个聚集索引，也只有一个主键，所以让人有所误会。我们在挑选主键时，要秉持着唯一、最小、不可NULL、容易获得、不常变更等条件，主键关乎着数据的正确性与完整性。而聚集索引则是从运行效率出发。举例来说，你的员工数据表内的主键可能是员工编号，但操作该数据表时，常常用来过滤与排序的字段是姓名，则聚集索引就应该建立在姓名字段上。若为数据表定义主键时，没有特别指定NONCLUSTERED，且数据表内尚未存在聚集索引，则sqlServer默认会依照主键来生成聚集索引。
非聚集索引则是完全独立于数据表之外的结构，其Leaf-Level结点中存放的数据有两种类型：bookmark或聚集索引的主键值，具体是哪一种就由数据表有没有建立聚集索引来决定。若数据表没有建立聚集索引，则称该数据表为heap，leaf-level放的是字段键值与之相数据表符合键值记录的row id，也就是文档编号、分页编号与页内记录编号所组合成的值。通过该row id在数据表内获取数据就称为书签查找。若数据表已建立了聚集索引，比如以WORDID来建立聚集索引，而用name所建立的非聚集索引结构去查询name=‘smith’的这一条记录，则会在name所建立的B+树中找到键值为smith的那个leaf-level结点，这个结点中存了smith对应的“聚集索引中的键值”，也即”88781”，于是再拿着得到的这个键值去聚集索引中(由WORKID字段所建立)找88781这个记录的具体内容。
在指定聚集索引时，数据域本身并不要求唯一，若指定为非唯一的聚集索引，SqlServer内部会自动为重复的键值建立4字节的唯一标示。
索引的目的是在大量数据中寻找少量数据，若是在大量数据中寻找大量数据，则扫描全表是更好的做法。当查询条件的选择性不高，也即当符合条件的记录占总记录数的比例很大时，通过非聚集索引查询是效率很低的。当符合查询条件的记录很多时，通过非聚集索引访问将导致分页读取异常频繁，就算两条记录在物理上是存储在同一个分页，但由于非聚集索引并不知道这一事实，所以该分页很可能会被重复读入内存两次，这么一来若符合条件的记录有n条，就需要向内存中读入n个数据表分页。所以不如做全表扫描更有效率。
聚集索引时非常重要的，若聚集索引的字段键值很大，则整个表的所有索引都将变得很没有效率，因为非聚集索引终究要通过聚集索引来拿到真正的数据。
在sql server中新增、修改和删除聚集索引时，可能导致数据表重新排列以及非聚集索引的重建，所以选择聚集索引时不可不慎。
SqlServer不需要在硬盘上的数据一定要实际地照聚集索引来排序，但在建立索引时，会尝试着在逻辑上排序的同时，也让实例数据尽可能地排序。在索引Leaf-Level节点中的每一个分页都有一个光标指向目前分页的前一个分页与后一个分页，形成双向连接串行。如果有如下语句：select * order by field1 ， 若已用field1建立了聚集索引，则此时顺着这个索引一次读出数据就行了，不需要再排序，若是用没有建立索引的字段来排序，则需要一次访问所有的数据，然后再进行排序，排序过程往往占据整个查询耗时的3/4以上
使用索引的注意事项
在建立索引时，可以要求键值是UNIQUE的，以保证该字段在整个数据表中不会有重复出现。唯一索引与定义数据表字段必须唯一的限制(CONSTRAINT)相似。其实sql server就是通过建立唯一索引来维护此种CONSTRAINT的。两者的差异只在于如何删除该CONSTRAINT，若是明确建立的唯一索引，则通过语句 DROP INDEX <index name> ON <table name> 来删除这儿唯一索引。若是通过CONSTRAINT限制来确保UNIQUE性，则使用ALTER TABLE <table name> DROP CONSTRAINT <UNIQUE CONSTRAINT NAME> 来删除对应字段的UNIQUE性。
一般来说，建立索引要看数据的使用方式，也就是哪些访问数据的sql语句常用，而这些语句是否是因为缺乏索引而没有效率，但绝不是替所有的sql语句都建立索引，因为这可能导致管理索引的开销过大。
TAG:
