Title Date Modified Category
searching 2019-07-09 12:00 2019-07-09 12:00 algorithm

1.1. 线性索引查找

数据结构的最终目的是提高数据的处理速度,索引是为了加快查找速度而设计的一种数据结构。

索引就是把一个关键字与它对应的记录相关联的过程,一个索引由若干个索引项构成,每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。

索引技术是组织大型数据库以及磁盘文件的一种重要技术。

索引按照结构可以分为线性索引,树形索引和多级索引。

我们这里就只介绍线性索引技术。

所谓线性索引就是将索引项集合组织为线性结构,也称为索引表。

我们重点介绍三种线性索引:稠密索引,分块索引和倒排索引。

1.1.1. 稠密索引

稠密索引是指在线性索引中,将数据集中的每个记录对应一个索引项,如图8-5-2所示。

对于稠密索引这个索引表来说,索引项一定是按照关键码有序的排列。

索引项有序也就意味着,我们要查找关键字时,可以用到折半,插值,斐波那契等有序查找算法,大大提高了效率。

这显然是稠密索引优点,但是如果数据集非常大,比如上亿,那也就意味着索引也得同样的数据集长度规模,对于内存有限的计算机来说,可能就需要反复去访问磁盘,查找性能反而大大下降了。

1.1.2. 分块索引

稠密索引因为索引项与数据集的记录个数相同,所以空间代价很大。为了减少索引项个数,我们可以对数据集进行分块,使其分块有序,然后再对每一块建立一个索引项,从而减少索引项的个数。

分块有序,是把数据集的记录分成了若干块,并且这些块需要满足两个条件:

  • 块内无序,即每一块内的记录不要求有序。
  • 块间有序,例如第二块所有记录的关键字均要大于第一块中所有记录的关键字。

对于分块有序的数据集,将每块对应一个索引项,这种索引方法叫做分块索引。

如图8-5-4所示,我们定义的分块索引的索引项结构分三个数据项:

  • 最大关键码,
  • 存储了块中的记录个数,以便于循环时使用
  • 用于指向块首数据元素的指针。

在分块索引表中查找,就是分两步进行:

  1. 在分块索引表中查找关键字所在的块。由于分块索引表是块间有序的,因此很容易利用折半,插值等算法得到结果。
  2. 根据块首指针找到相应的块,并在块中顺序查找关键码。因为块中可以是无序的,因此只能顺序查找。

分析一下分块索引的平均查找长度。

可见,分块索引的效率比之顺序查找的O(n)是高了不少,不过显然它与折半查找的O(logn)相比还有不少的差距。因此在确定所在块的过程中,由于块间有序,所以可以应用折半,插值等手段来提高效率。

总的来说,分块索引在兼顾了对细分快不需要有序的情况下,大大增加了整体查找的速度,所以普遍被用于数据库表查找等技术的应用当中。

1.1.3. 倒排索引

在这里这张单词表就是索引表,索引项的通用结构是:

  • 次关键码,
  • 记录号表

其中记录号表存储具有相同次关键字的所有记录的记录号(可以是指向记录的指针或是该记录的主关键字)。这样的索引方法就是倒排索引(inverted index)。

results matching ""

    No results matching ""