[科普中国]-算法索引

简介

在数学和计算机科学之中，算法（Algorithm）为一个计算的具体步骤，常用于计算、数据处理和自动推理。在实际应用中，为了方便应用人员对有关算法调用，通常将有关算法封装在一个程序包中。算法索引是指程序包中的有关算法进行聚族和排序，将有关算法放在一起，方便调用、分类比较。

聚簇索引聚簇索引也称为聚集索引，聚类索引，簇集索引，是一种对磁盘上实际数据重新组织以按指定的一个或多个列的值排序。聚簇索引类似于电话簿，后者按姓氏排列数据。由于聚簇索引规定数据在表中的物理存储顺序，因此一个表只能包含一个聚簇索引。但该索引可以包含多个列（组合索引），就像电话簿按姓氏和名字进行组织一样。汉语字典也是聚簇索引的典型应用，在汉语字典里，索引项是字母+声调，字典正文也是按照先字母再声调的顺序排列。聚簇索引对于那些经常要搜索范围值的列特别有效。使用聚簇索引找到包含第一个值的行后，便可以确保包含后续索引值的行在物理相邻。例如，如果应用程序执行的一个查询经常检索某一日期范围内的记录，则使用聚集索引可以迅速找到包含开始日期的行，然后检索表中所有相邻的行，直到到达结束日期。这样有助于提高此类查询的性能。同样，如果对从表中检索的数据进行排序时经常要用到某一列，则可以将该表在该列上聚簇（物理排序），避免每次查询该列时都进行排序，从而节省成本。

程序包程序包是一组相互关联的程序汇集而成的集合。①计算机制造商为方便用户使用而提供的程序系统。一般包括操作系统、汇编程序、编译程序、诊断程序、交叉汇编程序及由各种子程序和应用程序组成的程序库。②由相互有关的一组计算机程序组成的程序集合，用以执行某些特定的功能，能为多个计算机用户所使用1。

优缺点优点通过建立索引可以极大地提高在数据库中获取所需信息的速度，同时还能提高服务器处理相关搜索请求的效率，从这个方面来看它具有以下优点 ：

在设计数据库时，通过创建一个惟一的索引，能够在索引和信息之间形成一对一的映射式的对应关系，增加数据的惟一性特点。

能提高数据的搜索及检索速度，符合数据库建立的初衷。

能够加快表与表之间的连接速度，这对于提高数据的参考完整性方面具有重要作用2。

在信息检索过程中，若使用分组及排序子句进行时，通过建立索引能有效的减少检索过程中所需的分组及排序时间，提高检索效率。

建立索引之后，在信息查询过程中可以使用优化隐藏器，这对于提高整个信息检索系统的性能具有重要意义。

缺点虽然索引的建立在提高检索效率方面具有诸多积极的作用，但还是存在下列缺点 ：

在数据库建立过程中，需花费较多的时间去建立并维护索引，特别是随着数据总量的增加，所花费的时间将不断递增。

在数据库中创建的索引需要占用一定的物理存储空间，这其中就包括数据表所占的数据空间以及所创建的每一个索引所占用的物理空间，如果有必要建立起聚簇索引，所占用的空间还将进一步的增加

在对表中的数据进行修改时，例如对其进行增加、删除或者是修改操作时，索引还需要进行动态的维护，这给数据库的维护速度带来了一定的麻烦。

排序

又称分类，是根据项目中所含信息关键字码或字段的有关规则，对信息项目进行排列整理。按存贮信息项目的环境，分内排序和外排序两大类.当信息项目放至内存中一次完成排序的称内排序;当信息项目数量大，要将项目分成几部分，逐个进行内排序，再合并以完成最终排序任务的，称外排序.排序的种类很多，比较有代表性的排序方法有：

①交换排序：思路是按规则比较两相邻信息项的排序关键字值，如为逆序则两项交换，否则比较下一对，直至全部信息项排好序为止，属于交换排序类的有起冒排序;快速排序;模拟递归排序。

②插入排序：思路是将信息项目以合适的位置一个一个地插入到已排好序的文件中，直至全部项目插完为止.属于插入排序的有：直接插入排序;二分插入排序;希尔排序。

③选择排序：思路是选择信息项目中关键字最小的项放到已排序文件的最后，反复作这件事，直至全部排好序为止。属于这类排序方法的有：简单选择排序;树形选择排序；堆排序。

④归并排序：思路是将两个或两个以上的已排好序的若干项目加以归并，每次归并都使包含的项目增多，直至全部排好序。

⑤ 基数排序：它是借助于多关键字排序的思想对单逻辑关键字进行排序的方法。

排序算法的效率与数据的类型、规模和计算机系统的特性有关.在给定应用环境的情况下。可从算法的时间开销(数据的比较次数和移动次数等)、空间开销(执行算法所需的存贮空间)和程序设计的难易程度来评价算法的优劣。