文档章节

分块查找(Blocking Search)

 野渡书生
发布于 2016/04/28 21:12
字数 1091
阅读 56
收藏 2

1、定义

    分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法

2、基本思想

    分块查找的基本思想是:

    (1)首先查找索引表

    索引表是有序表,可采用二分查找或顺序查找,以确定待查的结点在哪一块。

    (2)然后在已确定的块中进行顺序查找

    由于块内无序,只能用顺序查找

3、 存储结构

    二分查找表由"分块有序"的线性表和索引表组成。

    (1)"分块有序"的线性表

    表R[1..n]均分为b块,前b-1块中结点个数为,第b块的结点数小于等于s;每一块中的关键字不一定有序,但前一块中的最大关键字必须小于后一块中的最小关键字,即表是"分块有序"的。

    (2)索引表

    抽取各块中的最大关键字及其起始位置构成一个索引表ID[l..b],即:ID[i](1≤i≤b)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的,所以索引表是一个递增有序表。

    【例】下图就是满足上述要求的存储结构,其中R只有18个结点,被分成3块,每块中有6个结点,第一块中最大关键字22小于第二块中最小关键字24,第二块中最大关键字48小于第三块中最小关键字49。

        

4、分块查找示例 

    【例】对于上例的存储结构:

    (1)查找关键字等于给定值K=24的结点

    因为索引表小,不妨用顺序查找方法查找索引表。即首先将K依次和索引表中各关键字比较,直到找到第1个关键宇大小等于K的结点,由于K<48,所以关键字为24的结点若存在的话,则必定在第二块中;然后,由ID[2].addr找到第二块的起始地址7,从该地址开始在R[7..12]中进行顺序查找,直到R[11].key=K为止。

    (2)查找关键字等于给定值K=30的结点

    先确定第二块,然后在该块中查找。因该块中查找不成功,故说明表中不存在关键字为30的结点。

5、算法分析

(1)平均查找长度ASL

    分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长度之和。

    ①  以二分查找来确定块,分块查找成功时的平均查找长度

      ASLblk=ASLbn+ASLsq≈lg(b+1)-1+(s+1)/2≈lg(n/s+1)+s/2

    ②  以顺序查找确定块,分块查找成功时的平均查找长度

      ASL'blk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s)

    注意:

    当 s= 时ASL'blk取极小值   +1 ,即当采用顺序查找确定块时,应将各块中的结点数选定为  

    【例】若表中有10000个结点,则应把它分成100个块,每块中含100个结点。用顺序查找确定块,分块查找平均需要做100次比较,而顺序查找平均需做5000次比较,二分查找最多需14次比较。

    注意:

    分块查找算法的效率介于顺序查找和二分查找之间。

(2)块的大小

    在实际应用中,分块查找不一定要将线性表分成大小相等的若干块,可根据表的特征进行分块。

    【例】一个学校的学生登记表,可按系号或班号分块。

(3) 结点的存储结构

    各块可放在不同的向量中,也可将每一块存放在一个单链表中

(4)分块查找的优点

    ①  在表中插入或删除一个记录时,只要找到该记录所属的块,就在该块内进行插入和删除运算。

    ②  因块内记录的存放是任意的,所以插入或删除比较容易,无须移动大量记录

(5)分块查找的缺点

    分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的运算


© 著作权归作者所有

粉丝 9
博文 217
码字总数 158821
作品 0
南京
私信 提问
加载中

评论(1)

回归当初
回归当初
算法之搜索(Java版)-持续更新补充

一、顺序查找 顺序查找对序列本身没有要求(比如不需要是已经排序好的),也不仅限于数字、字符,也可以用于前缀,对象信息的关键信息的匹配(比如查找指定id的相应信息)。 衡量查找性能的一...

kissjz
2018/08/06
0
0
实战Linux Bluetooth编程(九) SDP层编程

先前的章节谈过SDP协议。但没有具体讲如何编程。 BlueZ提供的SDP API,常见的如下: 1. sdpsessiont *sdp_create(int sk, uint32_t flags) 参数1:sk: socket 参数2:SDP flags. 取值如下: ...

sflfqx
2013/03/12
199
0
常用查找算法及实现

一、顺序查找 线性查找是在一个已知无(或有序)序队列中找出与给定关键字相同的数的具体位置。原理是 让关键字与队列中的数从最后一个开始逐个比较,直到找出与给定关键字相同的数为止,它的...

thanatos_y
2016/08/01
336
0
Google App Engine 1.8.1 发布

Google 宣布 Google App Engine 1.8.1 版本发布,包含了 bug 修复和一些显著的改动。 值得关注的内容有: The Search API is now a preview release. Applications that incorporate the Sea...

oschina
2013/06/20
1K
1
java 查找算法

1、顺序查找 public class OrderSearch { /**顺序查找平均时间复杂度 O(n) * @param searchKey 要查找的值 * @param array 数组(从这个数组中查找) * @return 查找结果(数组的下标位置)...

一贱书生
2016/11/08
18
0

没有更多内容

加载失败,请刷新页面

加载更多

Kafka 原理和实战

本文首发于 vivo互联网技术 微信公众号 https://mp.weixin.qq.com/s/bV8AhqAjQp4a_iXRfobkCQ 作者简介:郑志彬,毕业于华南理工大学计算机科学与技术(双语班)。先后从事过电子商务、开放平...

vivo互联网技术
今天
17
0
java数据类型

基本类型: 整型:Byte,short,int,long 浮点型:float,double 字符型:char 布尔型:boolean 引用类型: 类类型: 接口类型: 数组类型: Byte 1字节 八位 -128 -------- 127 short 2字节...

audience_1
今天
9
0
太全了|万字详解Docker架构原理、功能及使用

一、简介 1、了解Docker的前生LXC LXC为Linux Container的简写。可以提供轻量级的虚拟化,以便隔离进程和资源,而且不需要提供指令解释机制以及全虚拟化的其他复杂性。相当于C++中的NameSpa...

Java技术剑
今天
21
0
Wifiphisher —— 非常非常非常流氓的 WIFI 网络钓鱼框架

编者注:这是一个非常流氓的 WIFI 网络钓鱼工具,甚至可能是非法的工具(取决于你的使用场景)。在没有事先获得许可的情况下使用 Wifiphisher 攻击基础网络设施将被视为非法活动。使用时请遵...

红薯
今天
90
1
MongoDB 4 on CentOS 7安装指南

本教程为CentOS x86_64 7.x操作系统下,MongoDB Community x86_64 4.2(GA)安装指南。 安装方式一:yum repo在线安装 [此方式较为简单,官方推荐] Step1:新建MongDB社区版Yum镜像源。 # vim ...

王焱君
今天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部