作者： Morven.Huang
资料来源： www.cn blogs.com /莫文汉
一、引言
因为对数据库索引的兴趣从未使我们的讨论淡出，所以数据库索引是什么样的？ 聚合索引和非聚合索引的区别是什么？
本文希望对大家有一定的帮助。 虽然存疑之处不少，但我衷心希望大家不要吝惜指导和指正，共同进步。
二、B -树
在一般的数据库系统中，用于索引的数据结构大多是B-Tree或B-Tree。
例如，MsSql使用B树，而Oracle和Sysbase使用B树。 所以，首先，简单介绍一下B-Tree。
B-Tree与Binary Tree (二叉树，最多有两个子树)不同，一棵树m层的B-Tree满足以下条件。
每个节点最多有m个孩子；除了根节点和害羞的溪流外，其他每个节点至少有M/2个孩子； 根节点至少有两个孩子(树只包含一个节点的情况除外)。 害羞的溪流都在同一层，害羞的溪流不包含关键字信息； 有k个关键词的非害羞溪流中正好包括K 1个孩子； 另外，对于一个节点，其内部的关键字按照从小到大的顺序进行排序。
以下是b-tree(m=4)的样本。
每个节点主要包括关键字数组Key[]，指针数组(对)儿子的) son )。
在B-Tree内，对顺序检索(数组长度短时)或使用换行检索方法key ) )数组进行检索，如果发现关键字k，则返回该节点的地址和key ) )内的k的位置；
否则，可以判断出k在某个Key[i]和Key[i 1]之间。 从Son[i]指向的子节点继续搜索，直到在某个节点上成功搜索为止。 或者直到发现害羞的溪流，然后如果害羞的溪流中的搜索还没有成功，搜索过程就会失败。
下面是如何使用以下图像以b-tree(m=4，从1到6的顺序插入。
从这张图可以看出，插入关键字4后，由于原节点已满，所以要进行分裂，按照几乎一半的原则进行分裂，取出中间的关键字2，进行等级提升(这里是根节点)。
其他类推就是这样一个大致的过程。
三、数据库索引
1 .什么是索引
在数据库中，索引的含义与日常意义上的“索引”一词没有太大不同。 请在小时候查一下词典。 这是一个数据库对象，用于加速对数据库表的数据访问。
索引可以避免所有表扫描。 大多数查询只能扫描少数索引页和数据页，而不是扫描所有数据页。 对于非聚集索引，某些查询可以不访问数据页。 聚合索引可以防止数据插入操作集中在表的最后一个数据页上。 在某些情况下，也可以使用索引来避免排序操作。 当然，众所周知，索引会加快查询，但大多数数据更新都需要同时更新索引，因此也会降低数据库系统的数据更新性能。
2 .保存索引
索引记录中包含的基本信息包括键值，即在定义索引时指定的所有字段的值，以及指向数据页或其他索引页的逻辑指针。
当yqdxrk为空表编制索引时，数据库系统会分配空索引页，直到插入数据为止。 这个网页在这个时候既是根节点，也是害羞的溪流。
如果为每个yqdxrk在表中插入一行数据，则数据库系统会在此根节点中插入一行索引记录。 根节点满后，数据库系统大致会按以下步骤分裂
在创建两个儿子节点并将原始根节点的数据几乎分割为一半，并将指向两个儿子节点的指针分别写入新的两个儿子节点的常规情况下，索引记录必须包含索引字段值(以及4-9字节的指针)
索引页可以存储更多的索引记录。 这意味着在索引中进行搜索时，I/O有很大的优势。 了解这一点有助于从本质上了解使用索引的好处。
3 .索引的类型
a )收集索引，按索引顺序存储表数据。 对于聚合索引，叶节点存储实际的数据行，没有单独的数据页。
b )未统计的索引。 表数据的存储顺序与索引的顺序无关。 对于非聚集索引，害羞溪流包含索引字段值和指向数据页数据行的逻辑指针，其层次紧邻数据页，其行数与数据表行的数据量匹配。
由于实际数据可能只有一个物理顺序，因此一个表中只能创建一个聚集索引。
如果表中没有聚合索引，则将其称为堆(Heap )。 这些表中的数据行没有特定顺序，而是将添加所有新行的表的最后位置。
4 .收集索引
在集合索引中，害羞的溪流
也即数据结点，所有数据行的存储顺序与索引的存储顺序一致。1）聚集索引与查询操作
如上图，我们在名字字段上建立聚集索引，当需要在根据此字段查找特定的记录时，数据库系统会根据特定的系统表查找的此索引的根，然后根据指针查找下一个，直到找到。
例如我们要查询“Green”，由于它介于[Bennet,Karsen]，据此我们找到了索引页1007，在该页中“Green”介于[Greane, Hunter]间，据此我们找到害羞的溪流1133（也即数据结点），并最终在此页中找以了目标数据行。
此次查询的IO包括3个索引页的查询（其中最后一次实际上是在数据页中查询）。
这里的查找可能是从磁盘读取(Physical Read)或是从缓存中读取(Logical Read)，如果此表访问频率较高，那么索引树中较高层的索引很可能在缓存中被找到。所以真正的IO可能小于上面的情况。
2）聚集索引与插入操作
最简单的情况下，插入操作根据索引找到对应的数据页，然后通过挪动已有的记录为新数据腾出空间，最后插入数据。
如果数据页已满，则需要拆分数据页（页拆分是一种耗费资源的操作，一般数据库系统中会有相应的机制要尽量减少页拆分的次数，通常是通过为每页预留空间来实现）：
在该使用的数据段（extent）上分配新的数据页，如果数据段已满，则需要分配新段。调整索引指针，这需要将相应的索引页读入内存并加锁。大约有一半的数据行被归入新的数据页中。如果表还有非聚集索引，则需要更新这些索引指向新的数据页。特殊情况：
如果新插入的一条记录包含很大的数据，可能会分配两个新数据页，其中之一用来存储新记录，另一存储从原页中拆分出来的数据。通常数据库系统中会将重复的数据记录存储于相同的页中。类似于自增列为聚集索引的，数据库系统可能并不拆分数据页，页只是简单的新添数据页。3）聚集索引与删除操作
删除行将导致其下方的数据行向上移动以填充删除记录造成的空白。
如果删除的行是该数据页中的最后一行，那么该数据页将被回收，相应的索引页中的记录将被删除。
如果回收的数据页位于跟该表的其它数据页相同的段上，那么它可能在随后的时间内被利用。
如果该数据页是该段的唯一一个数据页，则该段也被回收。
对于数据的删除操作，可能导致索引页中仅有一条记录，这时，该记录可能会被移至邻近的索引页中，原索引页将被回收，即所谓的“索引合并”。
5．非聚集索引
非聚集索引与聚集索引相比：
叶子结点并非数据结点叶子结点为每一真正的数据行存储一个“键-指针”对叶子结点中还存储了一个指针偏移量，根据页指针及指针偏移量可以定位到具体的数据行。类似的，在除害羞的溪流外的其它索引结点，存储的也是类似的内容，只不过它是指向下一级的索引页的。聚集索引是一种稀疏索引，数据页上一级的索引页存储的是页指针，而不是行指针。
而对于非聚集索引，则是密集索引，在数据页的上一级索引页它为每一个数据行存储一条索引记录。
对于根与中间级的索引记录，它的结构包括：
索引字段值RowId（即对应数据页的页指针+指针偏移量）。在高层的索引页中包含RowId是为了当索引允许重复值时，当更改数据时精确定位数据行。下一级索引页的指针对于叶子层的索引对象，它的结构包括：
索引字段值RowId1）非聚集索引与查询操作
针对上图，如果我们同样查找“Green”，那么一次查询操作将包含以下IO：3个索引页的读取+1个数据页的读取。
同样，由于缓存的关系，真实的IO实际可能要小于上面列出的。
2）非聚集索引与插入操作
如果一张表包含一个非聚集索引但没有聚集索引，则新的数据将被插入到最末一个数据页中，然后非聚集索引将被更新。
如果也包含聚集索引，该聚集索引将被用于查找新行将要处于什么位置，随后，聚集索引、以及非聚集索引将被更新。
3）非聚集索引与删除操作
如果在删除命令的Where子句中包含的列上，建有非聚集索引，那么该非聚集索引将被用于查找数据行的位置，数据删除之后，位于索引叶子上的对应记录也将被删除。
如果该表上有其它非聚集索引，则它们叶子结点上的相应数据也要删除。
如果删除的数据是该数所页中的唯一一条，则该页也被回收，同时需要更新各个索引树上的指针。
由于没有自动的合并功能，如果应用程序中有频繁的随机删除操作，最后可能导致表包含多个数据页，但每个页中只有少量数据。
6．索引覆盖
索引覆盖是这样一种索引策略：当某一查询中包含的所需字段皆包含于一个索引中，此时索引将大大提高查询性能。
包含多个字段的索引，称为复合索引。索引最多可以包含31个字段，索引记录最大长度为600B。
如果你在若干个字段上创建了一个复合的非聚集索引，且你的查询中所需Select字段及Where,Order By,Group By,Having子句中所涉及的字段都包含在索引中，则只搜索索引页即可满足查询，而不需要访问数据页。
由于非聚集索引的害羞的溪流包含所有数据行中的索引列值，使用这些结点即可返回真正的数据，这种情况称之为“索引覆盖”。
在索引覆盖的情况下，包含两种索引扫描：
1）匹配索引扫描
此类索引扫描可以让我们省去访问数据页的步骤，当查询仅返回一行数据时，性能提高是有限的，但在范围查询的情况下，性能提高将随结果集数量的增长而增长。
针对此类扫描，索引必须包含查询中涉及的的所有字段，另外，还需要满足：Where子句中包含索引中的“引导列”（Leading Column），例如一个复合索引包含A,B,C,D四列，则A为“引导列”。
如果Where子句中所包含列是BCD或者BD等情况，则只能使用非匹配索引扫描。
2）非配置索引扫描
正如上述，如果Where子句中不包含索引的导引列，那么将使用非配置索引扫描。
这最终导致扫描索引树上的所有叶子结点，当然，它的性能通常仍强于扫描所有的数据页。
[参考]
[1] http://manuals.sybase.com/onlinebooks/group-asarc/asg1200e/aseperf/@Generic__BookTextView/3358[2] http://publib.boulder.ibm.com/infocenter/idshelp/v10/index.jsp?topic=/com.ibm.adref.doc/adref235.htm