大话数据结构-8.5 线性索引查找 - 高飞网

8.5 线性索引查找

2016-12-31 00:34:26.0

    对于增长非常快的数据记录,如何快速查找需要的数据?使用索引。索引就是把一个关键字与它对应的记录相关联的过程。索引按照结构可以分为线性索引树形索引多级索引

   所谓线性索引,就是将索引项集合组织为线性结构,也称为索引表。这里介绍三种线性索引:稠密索引分块索引倒排索引。 

8.5.1 稠密索引

    稠密索引是指在线性索引中,将数据集中的每个记录对应一个索引项。

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

    索引项有序,也就意味着查找关键字时,可以用到折半、插值、斐波那契等有序查找算法,大大提高了效率。例如上图中,如果没有索引,按右侧的数据查,只能顺序查找,需要6次,而有索引,按照左侧的索引有序查找,用折半查找,只需两次。
    稿密索引的缺点:如果数据集非常大,比如上亿,意味着索引也有同样的规模,对于内存有限的计算机来说,可能就需要反复对访问磁盘,查找性能反而大大下降。

8.5.2 分块索引

    类似于图书的分门别类摆放,将书籍分块展示,块间是有序的,但块内是无序的。

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

  1. 块内无序,即每一块的记录不要求有序。
  2. 块间有序。

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

  1. 最大关键码,存储每一块中的最大关键字,这样的好处就是可以使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大;
  2. 存储了块中的记录个数,以便于循环使用;
  3. 用于指向块首数据元素的指针,便于开始对这一块中记录进行遍历。

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

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

    分块查找的平均查找长度:

    设n个记录的数据集被平均分成m块,每个块中有t条记录,即:n=m×t,或者说m=n÷t。再假设Lb为查找索引表中的平均查找长度,因最好与最差的等概率原则,所以Lb的平均长度为。Lw为块中查找记录的平均查找长度,同理哥知它的平均查找长度为

    这样分块索引查找的平均查找长度为:

    由此可见,平均长度不仅仅取决于数据集的总记录数n,还和每一个块的记录个数t相关。最佳的情况是分的块数m与块中的记录数t相同。此时意味着

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

8.5.3 倒排索引

    倒排索引的索引项的通用结构是:

  1. 次关键码,如英文单词
  2. 记录号表,如文章编号

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