首页 > 其他 > 详细

13.线性索引查找---稠密索引、分块索引、倒排索引

时间:2020-07-01 20:53:58      阅读:30      评论:0      收藏:0      [点我收藏+]
/*
8.5 线性索引查找
前面几种比较高效的查找方法都是基于有序的基础之上的,但事实上,很多数据集可能增长非常快,
例如,某些微博网站或者一些服务器的日志信息记录。
数据结构的最终目的是提高数据的处理速度,索引是为了加快查找速度而设计的一种数据结构。
索引就是把一个关键字与它对应的记录相关联的过程,一个索引由若干个索引项构成,每个索引项
至少应包含关键字和其对应的记录再存储器中的位置等信息。索引技术是组织大型数据库以及磁盘文件的一种重要技术。

索引按照结构可以分为线性索引、树形索引和多级索引。我们这里就只介绍线性索引技术。所谓的线性索引
就是将索引项集合组织为线性结构,也成为索引表。我们重点介绍三种线性索引:稠密索引、分块索引和倒排索引。

8.5.1 稠密索引
    我母亲年纪大了,记忆力不好,经常在家里找不到东西,于是他想到了一个办法。她用一小本子记录了家里所有
小东西放置的位置,比如户口本放在右手床头柜下面抽屉中,针线放在电视柜中间的抽屉中,钞票放在衣柜...
总之,她老人家把这些小物品的放置位置都记录在了小本子上,并且每隔一段时间还按照本子整理一遍家中的物品,
用完都放回原处,这样她就几乎再没有找不到东西。
    从这件事就可以看出,家中的物品尽管是无序的,但是如果有一个小本子记录,寻找起来也是非常容易,
而这个小本子就是索引。
稠密索引是指在线性索引中,将数据集中的每个记录对应一个索引项,如下图:
稠密索引 原型图片

刚才的小例子和稠密索引还是略有不同,家里的东西毕竟少,小本子再多也就几十页,全部翻看完就几分钟时间,而
稠密索引要应对的可能是成千上万的数据,因此对于稠密索引这个索引表来说,索引项一定是按照关键码有序排列。
索引有序也就意味着,我们查找关键字时,可以用到折半、插值、斐波那契等有序查找算法,大大提高了效率。

8.5.2 分块索引
    回想下图书馆时如何藏书的。显然他不会时顺序摆放的,给我们一个稠密索引表去查,然后再找到书给你。
图书馆的图书分类摆放是一门非常完整的科学体系,而它最重要的一个特点就是分块。 
    稠密索引因为索引项于数据集的记录个数相同,所以空间代价很大。
    为了减少索引项的个数,我们可以对数据集进行分块,使其分块有序,然后再对每一块建立一个索引项,
从而减少索引项的个数。
    分块有序,是把数据集的记录分成若干块,并且这些块需要满足两个条件:
    1.块内无序,即每一块内的记录不要求有序。当然,你如果能够让块内有序对查找来说更理想,不过这就要付出
大量时间和空间的代价,因此通常我们不要求块内有序。
    2.块间有序,例如,要求第二块所有记录的关键字均要大于第一块中所有记录的关键字,第三块的所有记录的关键字
均要大于第二块的所有记录关键字.....因为只有块间有序,才有可能在查找时带来效率。

    定义分块索引的索引项结构分三个数据项:
    最大关键码,他存储每一块中最大关键字;
    存储块中的记录个数;
    用于指向块首数据元素的指针;

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

8.5.3 倒排索引
搜索引擎中就使用了倒排索引,无论你查什么样的信息,它都可以在极短时间内给你一些结果。

我们来看样例,现在有两篇极短的英?“?章”——其实只能算是句
?,我们暂认为它是?章,编号分别是1和2。
1.Books and friends should be few but good.(读书如交友,应求少?精。)
2.A good book is a good friend.(好书如挚友。)
假设我们忽略掉如“books”、“friends”中的复数“s”以及如“A”这样的??写差异。我们可以整理出这样?张单词表,如表8-5-1所?,并将单
词做了排序,也就是表格显?了每个不同的单词分别出现在哪篇?章中,?如“good”它在两篇?章中都有出现,?“is”只是在?章2中才有

英?单词 ?章编号
a 2
and 1
be 1
book 1,2
but 1
few 1
friend 1,2
good 1,2
is 2
should 1

有了这样?张单词表,我们要搜索?章,就?常?便了。如果你在搜索框中填写“book”关键字。系统就先在这张单词表中有序查
找“book”,找到后将它对应的?章编号1和2的?章地址(通常在搜索引擎中就是??的标题和链接)返回,并告诉你,查找到两条记录,
?时0.0001秒。由于单词表是有序的,查找效率很?,返回的?只是?章的编号,所以整体速度都?常快。
*/

 

13.线性索引查找---稠密索引、分块索引、倒排索引

原文:https://www.cnblogs.com/go-ahead-wsg/p/13221189.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!