漫谈数据库索引

 

一、索引的概念和作用

    索引是对数据库表中一列或多列的值进行排序的一种结构，使用索引可快速访问数据库表中的特定信息。

    在数据库中，索引的含义与日常意义上的“索引”一词并无多大区别（想想小时候查字典），它是用于提高数据库表数据访问速度的数据库对象。

主键也是一种索引，典型的数据库（如mysql，oracle等）会在建立主键的同时对其建立索引。

 

从本质上了解索引的优势

    通常状况下，由于索引记录仅包含索引字段值（以及4-9字节的指针），索引实体比真实的数据行要小许多，索引页相较数据页来说要密集许多。一个索引页可以存储数量更多的索引记录，这意味着在索引中查找时在I/O上占很大的优势，同时索引采用B-树结构，也提高查询的效率，理解这一点有助于从本质上了解使用索引的优势。

    针对索引的I/O成本，我们可以算一算：如果表中的一条记录在磁盘上占用 1000字节的话，我们对其中10字节的一个字段建立索引，那么该记录对应的索引块的大小只有10字节。我们知道，SQL Server的最小空间分配单元是“页（Page）”，一个页在磁盘上占用8K空间，那么这一个页可以存储上述记录8条，但可以存储索引800条。现在我们要从一个有8000条记录的表中检索符合某个条件的记录，如果没有索引的话，我们可能需要遍历8000条×1000字节/8K字节=1000个页面才能够找到结果。如果在检索字段上有上述索引的话，那么我们可以在8000条×10字节/8K字节=10个页面中就检索到满足条件的索引块，然后根据索引块上 的指针逐一找到结果数据块，这样IO访问量要少的多。

    众所周知，虽然索引可以提高查询速度，但是索引是需要存储空间，而且对于update/insert/delete的每次执行，字段的索引都必须重新计算更新，因此不适用于经常更新的数据表。  

 

二、索引的实现

1.索引的存储

  一条索引记录中包含的基本信息包括：

  key：键值（即你定义索引时指定的所有字段的值）

  Pointer: 逻辑指针（指向数据页或者另一索引页）。

   

2. 索引的数据结构

我们常见的数据库系统，其索引使用的数据结构多是B-Tree或者B+Tree。例如，MsSql使用的是B+Tree，Oracle及Sysbase使用的是B-Tree，关于B-Tree的原理，敬请查看我的博文:http://kakajw.iteye.com/blog/1074364

 

一般数据库的最小空间分配单元是页（Page），因此索引和数据库记录都是以页的形式物理地保存在存储设备中。

 

数据页：保存数据记录的物理存储单元。

索引页：保存索引记录的物理存储单元。

 

索引分为聚簇索引和非聚簇索引 

 

3．聚簇索引

 在聚簇索引中，叶结点也即数据结点，所有数据行的存储顺序与索引的存储顺序一致。在一张表上只能创建一个聚簇索引，因为真实数据的物理顺序只可能是一种。如果一张表没有聚簇索引，那么它被称为“堆集”（HEAP），这样的表中的数据行没有特定的顺序，所有的新行将被添加的表的末尾位置。
对于聚簇索引，叶子结点即为真实的数据行所在的数据页，不再有另外单独的数据页。

 

1）聚簇索引与查询操作
如上图，我们在名字字段上建立聚簇索引，当需要在根据此字段查找特定的记录时，数据库系统会根据特定的系统表查找的此索引的根，然后根据指针查找下一个，直到找到。例如我们要查询“GREEN”，由于它介于[BENNET,KARSEN]，据此我们找到了索引页1007，在该页中“GREEN”介于[GREANE, HUNTER]间，据此我们找到叶结点1133（也即数据结点），并最终在此页中找以了目标数据行。
此次查询的IO包括3个索引页的查询（其中最后一次实际上是在数据页中查询）。这里的查找可能是从磁盘读取(PHYSICAL READ)或是从缓存中读取(LOGICAL READ)，如果此表访问频率较高，那么索引树中较高层的索引很可能在缓存中被找到。所以真正的IO可能小于上面的情况。
 
2）聚簇索引与插入操作
最简单的情况下，插入操作根据索引找到对应的数据页，然后通过挪动已有的记录为新数据腾出空间，最后插入数据。
如果数据页已满，则需要拆分数据页（页拆分是一种耗费资源的操作，一般数据库系统中会有相应的机制要尽量减少页拆分的次数，通常是通过为每页预留空间来实现）：
A）在该使用的数据段（EXTENT）上分配新的数据页，如果数据段已满，则需要分配新段。
B）调整索引指针，这需要将相应的索引页读入内存并加锁。
C）大约有一半的数据行被归入新的数据页中。
D）如果表还有非聚簇索引，则需要更新这些索引指向新的数据页。
特殊情况：
A）如果新插入的一条记录包含很大的数据，可能会分配两个新数据页，其中之一用来存储新记录，另一存储从原页中拆分出来的数据。
B）通常数据库系统中会将重复的数据记录存储于相同的页中。
C）类似于自增列为聚簇索引的，数据库系统可能并不拆分数据页，只是简单的新添数据页。
 
3）聚簇索引与删除操作
删除行将导致其下方的数据行向上移动以填充删除记录造成的空白。
如果删除的行是该数据页中的最后一行，那么该数据页将被回收，相应的索引页中的记录将被删除。如果回收的数据页位于跟该表的其它数据页相同的段上，那么它可能在随后的时间内被利用。如果该数据页是该段的唯一一个数据页，则该段也被回收。
对于数据的删除操作，可能导致索引页中仅有一条记录，这时，该记录可能会被移至邻近的索引页中，原索引页将被回收，即所谓的“索引合并”。 

 

SQL Server 数据库的聚簇索引结构

 

 4．非聚簇索引
    非聚簇索引，表数据存储顺序与索引顺序无关。
    对于非聚簇索引，叶结点包含索引字段值及指向数据页的数据行的逻辑指针；叶子节点层紧邻数据页，其行数量与数据表行数据量一致。

    聚簇索引是一种稀疏索引，数据页上一级的索引页存储的是页指针，而不是行指针。而对于非聚簇索引，则是密集索引，在数据页的上一级索引页它为每一个数据行存储一条索引记录。
对于根与中间级的索引记录，它的结构包括：
A）索引字段值；
B）ROWID（即对应数据页的页指针，指针偏移量）。在高层的索引页中包含ROWID是为了当索引允许重复值时，当更改数据时精确定位数据行；

C）下一级索引页的指针；

对于叶子层的索引对象，它的结构包括：
A）索引字段值
B）ROWID

 

 

1）非聚簇索引与查询操作
针对上图，如果我们同样查找“GREEN”，那么一次查询操作将包含以下IO：3个索引页的读取+1个数据页的读取。同样，由于缓存的关系，真实的IO实际可能要小于上面列出的。
 
2）非聚簇索引与插入操作
如果一张表包含一个非聚簇索引但没有聚簇索引，则新的数据将被插入到最末一个数据页中，然后非聚簇索引将被更新。如果也包含聚簇索引，该聚簇索引将被用于查找新行将要处于什么位置，随后，聚簇索引、以及非聚簇索引将被更新。
 
3）非聚簇索引与删除操作
如果在删除命令的WHERE子句中包含的列上，建有非聚簇索引，那么该非聚簇索引将被用于查找数据行的位置，数据删除之后，位于索引叶子上的对应记录也将被删除。如果该表上有其它非聚簇索引，则它们叶子结点上的相应数据也要删除。
如果删除的数据是该数所页中的唯一一条，则该页也被回收，同时需要更新各个索引树上的指针。
    由于没有自动的合并功能，如果应用程序中有频繁的随机删除操作，最后可能导致表包含多个数据页，但每个页中只有少量数据。

 

SQL SERVER 数据库的非聚簇索引结构

 

5. 聚簇索引与非聚簇索引的本质区别
    聚簇索引的叶节点就是数据节点，而非聚簇索引的叶节点仍然是索引节点，并保留一个链接指向对应数据行。
    以SQL SERVER数据库为例（SQL SERVER的索引是二叉树结构），通过计算来分析它们的区别。
    假设有一8000条记录的表，表中每条记录在磁盘上占用1000字节，如果在一个10字节长的字段上建立非 聚簇索引主键，需要二叉树节点16000个（这16000个节点中有8000个叶节点，每个页节点都指向一个数据记录），这样数据将占用8000条 ×1000字节/8K字节=1000个页面；索引将占用16000个节点×10字节/8K字节=20个页面，共计1020个页面。
    同样一张表，如果我们在对应字段上建立聚簇索引主键，由于聚簇索引的页节点就是数据节点，所以索引节点仅有8000个，占用10个页面，数据仍然占有1000个页面。
下面我们看看在执行插入操作时，非聚簇索引的主键为什么比聚簇索引主键要快。主键约束要求主键不能出现重复，那么SQL SERVER是怎么知道不出现重复的呢？唯一的方法就是检索。对于非聚簇索引，只需要检索20个页面中的16000个节点就知道是否有重复，因为所有主键 键值在这16000个索引节点中都包含了。但对于聚簇索引，索引节点仅仅包含了8000个中间节点，至于会不会出现重复必须检索另外1000个页数据节点才知道，总的来看，相当于检索10+1000=1010个页面才知道是否有重复。所以聚簇索引主键的插入速度要比非聚簇索引主键的插入速度慢很多。
    让我们再来看看数据检索的效率，如果对上述两表进行检索，在使用索引的情况下，对于聚簇索引检索，我们可能会访问10个索引页面外加1000个数据页面得 到结果（实际情况要比这个好），而对于非聚簇索引，系统会从20个页面中找到符合条件的节点，再映射到1000个数据页面上（这也是最糟糕的情况），比较一下，一个访问了1010个页面而另一个访问了1020个页面，可见检索效率差异并不是很大。所以不管非聚簇索引也好还是聚簇索引也好，都适合排序，聚簇索引仅仅比非聚簇索引快一点。

 

6．索引覆盖

    索引覆盖是这样一种索引策略：当某一查询中包含的所需字段皆包含于一个索引中，此时索引将大大提高查询性能。

    包含多个字段的索引，称为复合索引。索引最多可以包含31个字段，索引记录最大长度为600B。如果你在若干个字段上创建了一个复合的非聚簇索引，且你的查询中所需Select字段及Where,Order By,Group By,Having子句中所涉及的字段都包含在索引中，则只搜索索引页即可满足查询，而不需要访问数据页。由于非聚簇索引的叶结点包含所有数据行中的索引列值，使用这些结点即可返回真正的数据，这种情况称之为“索引覆盖”。