[科普中国]-检索和排序处理器

简介

检索和排序处理器是一种特殊的处理器，专门用于处理检索和排序操作。在实际应用中，有些领域对于处理器有特殊的要求，即处理器专门用于处理哪一类问题，如图形处理器，检索和排序处理器也是其中一种。检索和排序处理器在处理检索和排序操作比通用处理器要快很多，主要是在设计上对进行排序和检索操作进行了优化，即硬件加速。

硬件加速硬件加速是指在计算机中通过把计算量非常大的工作分配给专门的硬件来处理以减轻中央处理器的工作量之技术。中央处理器的结构使得它能够在短时间内完成各种各样不同的指令。它能够处理什么指令主要由软件限制。但是由于中央处理器的结构有些重复任务无法非常有效和迅速地被处理。由于软件的原因处理器优化的可能性有限。通过使用专门为这样的重复任务设计的特殊硬件元件（芯片或者处理器）可以解决这个问题。这些特殊硬件元件不必像中央处理器那样灵活，因此它们的硬件设计就已经顾及了优化处理这些特殊问题的需要，这样一来中央处理器有时间去处理其它任务。有些任务能够通过把它们分解为上千小任务非常有效地被解决。比如对一定的频率带做傅里叶变换或者渲染一小块图像。这些小任务可以互相之间不相关地平行计算。通过大量平行计算，即适用大量平行运行的小处理器来处理这些特殊任务总的计算速度可以大大提高。在许多情况下计算速度随平行处理器的数量线性提高。

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

排序的种类很多，比较有代表性的排序方法有：

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

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

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

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

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

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

检索检索是指从已储存的信息库中索取、找出所需要的信息的过程，有时也称索引。索引是为了加速对表中数据行的检索而创建的一种分散的存储结构。索引是针对表而建立的，它是由数据页面以外的索引页面组成的，每个索引页面中的行都会含有逻辑指针，以便加速检索物理数据2。索引的作用相当于图书的目录，可以根据目录中的页码快速找到所需的内容。索引提供指向存储在表的指定列中的数据值的指针，然后根据您指定的排序顺序对这些指针排序。数据库使用索引以找到特定值，然后顺指针找到包含该值的行。这样可以使对应于表的SQL语句执行得更快，可快速访问数据库表中的特定信息。在数据库系统中建立索引主要有以下作用：

（1）快速取数据；

（2）保证数据记录的唯一性；

（3）实现表与表之间的参照完整性；

（4）在使用ORDER by、group by子句进行数据检索时，利用索引可以减少排序和分组的时间。