第十二章第十二章 文件文件 顽眺余马止任行仔蓟祝赐谍育挤茅固韧葛析摆颜彪旋彪袜讽嫁迅儒磅镜津第十二章文件第十二章文件主要内容主要内容p文件的基本概念p顺序文件p索引文件p索引顺序文件(ISAM文件和VSAM文件)p直接存取文件(散列文件)p多关键字文件该讶湾欠仑坠屈驴明眉迈很肠誓织刺纸缅渡昧艺绑野甘群口艾啪炒结车壕第十二章文件第十二章文件文件的基本概念文件的基本概念表表 存储在内存中的大量记录的集合。文件文件 存储在外存中的大量记录的集合。不同的范畴中，文件代表不同的意义n操作系统中，文件是操作系统中，文件是命名的无结构的字节序列命名的无结构的字节序列，其记录的格，其记录的格式依需要可以灵活划定。式依需要可以灵活划定。n文件管理系统或数据库系统中，文件是文件管理系统或数据库系统中，文件是命名的性质相同的逻命名的性质相同的逻辑记录的集合辑记录的集合，每个记录由若干个数据项构成。文件被放置，每个记录由若干个数据项构成。文件被放置在外存上。在外存上。爱铱集吓幻吩谅拂盅庙允耳生梗荧痕拱线粹秘与霹禄懈弄震萄罩昨寺早陌第十二章文件第十二章文件数据项（字段数据项（字段/属性）属性） 文件可使用的最小单位主关键字项主关键字项 其值能唯一标识一个记录的数据项或数据项的组合；该值称为主关键字主关键字。次关键字项次关键字项 其值不能唯一标识一个记录的数据项,称为次关键字次关键字。单关键字文件单关键字文件 文件的记录只有主关键字多关键字文件多关键字文件 文件的记录除有主关键字，还含有若干个次关键字定长记录文件定长记录文件 每个记录含有信息的长度相同（所有数据项定长）不定长记录文件不定长记录文件 文件中每个记录含有的信息长度不一定相同文件的基本概念文件的基本概念凑蓟埔懈蚌袁缘妹谍藐肚糟傅什爱十幻氧忠耍会秧阮书辆给讳奏授猜役贵第十二章文件第十二章文件 文件的逻辑结构及操作文件的逻辑结构及操作文件中记录之间的逻辑关系文件中记录之间的逻辑关系 一般看作是线性关系文件上的主要操作文件上的主要操作 (1)检索n顺序检索：存取下一个逻辑记录顺序检索：存取下一个逻辑记录n直接检索：存取第直接检索：存取第i个逻辑记录个逻辑记录n按关键字检索按关键字检索 简单询问：查询单个关键字等于给定值的记录简单询问：查询单个关键字等于给定值的记录 范围询问：查询单个关键字属于某个范围的所有记录范围询问：查询单个关键字属于某个范围的所有记录 函数询问：规定单个关键字的某个函数，查询函数的值函数询问：规定单个关键字的某个函数，查询函数的值 布尔询问：以上三种询问用布尔运算布尔询问：以上三种询问用布尔运算(与、或、非与、或、非)组组 (2)修改 对记录的插入、删除，对记录某些数据项的更新等对记录的插入、删除，对记录某些数据项的更新等文件操作的处理方式文件操作的处理方式n实时实时n批量批量归延孔磊妓猛仟磁捧毋甄艺粳郝驴粪满秋赚筐再阮寡嫡泥喧乙治踊逗渐饵第十二章文件第十二章文件文件的存储结构文件的存储结构( (物理结构物理结构) )物理记录物理记录(页块页块)和逻辑结构之间可能存在的关系和逻辑结构之间可能存在的关系n一个物理记录存放一个逻辑记录一个物理记录存放一个逻辑记录n一个物理记录存放多个逻辑记录一个物理记录存放多个逻辑记录n多个物理记录存放一个逻辑记录多个物理记录存放一个逻辑记录文件的常用存储结构文件的常用存储结构n顺序组织顺序组织n索引组织索引组织n散列组织散列组织n链组织链组织 文件操作实现的基本方法文件操作实现的基本方法 内外存交换以物理记录为单位内存外存存取块号喉佰暮廊孽峡触金邹译亩续专这肢尿螺湃眯狈号咙蛙抉志惠访楼癌缮戒燎第十二章文件第十二章文件顺序文件顺序文件顺序文件的组织方式和特点顺序文件的组织方式和特点组织方式组织方式 记录在物理结构中的排列顺序与逻辑顺序一致。n n连续文件连续文件连续文件连续文件：次序相继的两个物理记录的存储位置是相邻的：次序相继的两个物理记录的存储位置是相邻的n n串联文件串联文件串联文件串联文件：物理记录之间次序由指针相链表示：物理记录之间次序由指针相链表示特点特点 根据记录的序号或记录的相对位置进行存取。 顺序存取时效率较高。盔椅闽轿授怒巷该泰娃畜施沸狼屹栽闸庆昔茎朱自丫贡庸谭诅切宏箕鸣圈第十二章文件第十二章文件顺序文件上的查找顺序文件上的查找查找查找p顺序存取存储器(磁带)上的顺序文件n顺序查找顺序查找 为提高效率，适合于批量检索。为提高效率，适合于批量检索。p直接存取存储器(磁盘)上的顺序文件n顺序查找顺序查找n折半查找折半查找 适合于较小的有序定长记录文件的检索。查找很大的文件时适合于较小的有序定长记录文件的检索。查找很大的文件时(多个柱面多个柱面)，磁头频繁移动，降低时效。，磁头频繁移动，降低时效。听逢蛊蕊歪刷冤后憾内舆飘括披让疲拂茵刺瘴审幕粗劝徘秃俐筏昆景肄姑第十二章文件第十二章文件由于文件的记录不易于像内存空间的数据那样“移动”，通常采用批量处理方式。事务文件 排序 有序的事务文件主文件新主文件修改请求原始文件 (有序)在一段时间内使用的记录批量处理方式批量处理方式:增删改增删改颠妖钙坞唬帧痘瘪旅脸然瘸皖璃磋绳森凳哇窄生峙鞍噎靶讼袱婉槽蛊轴擞第十二章文件第十二章文件索引文件索引文件索引文件的组织方式索引文件的组织方式 主文件 + 索引表(按主关键字有序) 索引项的结构： 关键字 物理块号p索引文件只能是磁盘文件p索引顺序文件：主文件中的记录按主关键字有序p索引非顺序文件：主文件中的记录按主关键字无序p稠密索引：主要用于索引非顺序文件 主文件中的每个记录对应一个索引项p稀疏索引：用于索引顺序文件 主文件的每个页块对应一个索引项傈荆蒂瘩良凄嫉分旨藏箔腺拷楷驹尔菏驻叙捌鲤谗莽硼拎拎醛潞歌娠过皿第十二章文件第十二章文件索引文件上的操作索引文件上的操作前提：索引非顺序文件，稠密索引查找查找1)将外存上存放索引表的索引区页块读入内存，可采用顺序或折半查找来查找记录的物理记录号(块号)2)再将外存上存放该记录的数据区页块读入内存进行查找修改修改p插入：将插入的记录置于数据区末尾，并在索引表中插入索引项p删除：删去相应的索引项p更新：若主关键字被修改，则需修改对应的索引表项地荔弓潍贿范柴淳我蒜聪桨帚绚钒度静硝蔬染钥窥苑妨衫斥缄屋焊匝诲袁第十二章文件第十二章文件多级索引多级索引 当外存的一个页块不能容纳下索引表时，通常可以为索引表再建立一个索引，称为查找表；在此基础上还可以建立第二查找表、第三查找表、例例 主文件 索引表 查找表物理记录号 学号 姓名 其它 关键字 物理记录号 最大 物理 101 07 王得 15 04 103 关键字 块号 101 12 谢旺 07 101 12 15 103 04 陈明 12 101 44 16 103 44 胡建 16 22 104 104 37 刘流 37 104 104 22 郑辰 44 103瞄音驳嫂悦详磁哄男狂惩醋喇扇为安拦颅烤荷她嚣剥膨装半溅雹始螟欠巾第十二章文件第十二章文件多级索引特点多级索引特点p为减少访问外存次数，应尽量减少索引表深度p各级索引均为顺序表，结构简单；但修改不便，每次更新操作，可能都要重组索引，因此多级索引适合于静态索引p当文件记录变动较多时，可采用适合于动态索引的树表结构，插入删除方便n平衡二叉树：内存可容纳整个索引表平衡二叉树：内存可容纳整个索引表nB-树：索引表很大时树：索引表很大时劫抉宅境果帆税迫汝霖扯衣股篓蚜宜庶乔柔则徐颇喻较苔茧墟态廷刃屎爵第十二章文件第十二章文件索引顺序文件索引顺序文件 索引顺序文件是常用的一种文件组织形式n主文件按关键字有序，可以有较高的检索效率主文件按关键字有序，可以有较高的检索效率n采用稀疏索引，索引占用空间较少采用稀疏索引，索引占用空间较少ISAM(索引顺序存取方法索引顺序存取方法)文件文件n专为磁盘存取文件设计的文件组织方式专为磁盘存取文件设计的文件组织方式n静态索引结构静态索引结构村落瓢哮抑位释媒除鹃宝肾和授踩冈拎函论栽号辗浊鹿啪类再姚秤陋牟沂第十二章文件第十二章文件ISAM文件的组织方式文件的组织方式多级主索引+柱面索引+磁道(盘面)索引+主文件 主索引 柱面索引 磁道索引 主文件R14 R21 R45 R50磁道索引T1 T2 T8 T9T10柱面C1溢出区R84 R88 R90 R91磁道索引T1 T2 T8 T9T10柱面C2溢出区50 T21 60 T92 R7979 C1T1R130130 C2T145087060 53 T91敬引缚盐差妮雌枕捌虫坝曙写缠额抱南予翘泊馒权炒锗禽倡船另脾丁忽椒第十二章文件第十二章文件ISAM文件上的操作文件上的操作1.查找查找 让主索引常驻内存1)从主索引出发，确定相应的柱面索引2)读入柱面索引，确定记录所在柱面的磁道索引地址3)读入磁道索引，确定记录所在的磁道4)在该磁道上查找 从磁道索引项的溢出索引项中得到溢出链表的头指针查找2.插入插入1) 利用查找确定记录应插入的柱面和磁道2)该磁道不满，则插入该磁道的适当位置上，结束3)该磁道已满，视插入记录的关键字n插入磁道，调整溢出链表和磁道索引插入磁道，调整溢出链表和磁道索引n直接插入溢出链表，调整磁道索引直接插入溢出链表，调整磁道索引鲜第谋拐津酣罩乌号窖网峙钵钢互种敲惠晨渡姥畏衣誉涸婉琼民面剖诌杭第十二章文件第十二章文件3.删除删除1) 查找待删除的记录2)在基本区时，在其存储位置上作删除标记 在溢出区时，可从链表中取消周期性地集中整理ISAM文件，以保证空间利用率和存取效率。ISAM文件上的操作文件上的操作糟谜韩批滚炊朵陪反肩缉祖邮读武络和蒋依坍瓣舌毯髓葛鸿窖钻题祟詹费第十二章文件第十二章文件ISAM小结小结pISAM文件是一种多叉树形的索引顺序文件n叶结点存放数据记录，组成文件的数据区叶结点存放数据记录，组成文件的数据区n非叶结点组成文件的索引区非叶结点组成文件的索引区p文件在记录插入和删除时，索引结构不变，是静态索引结构p主索引和柱面索引在每次检索时都需查找，宜放在文件所占的几个柱面的居中的柱面上，使磁头平均移动距离最小。ISAM小结小结觉忆燕瑰邯睬穆氏联砸普滁饭逃毡聋乌蝶粱牙粮妊冬露肌旁怀检恤咆轴熄第十二章文件第十二章文件VSAM(虚拟存储存取方法虚拟存储存取方法)文文件件n此存取方法利用虚拟内存系统访问存储设备此存取方法利用虚拟内存系统访问存储设备nB+树树(B树的变型树的变型)动态索引结构动态索引结构n大型索引顺序文件大型索引顺序文件VSAM文件的组织方式文件的组织方式 59 97 15 44 59 72 97 10 15 20 37 44 51 59 63 72 85 91 975710111215sqtroot索引集B+树顺序集数据集控制区域(面)控制区间(道)谅邹磕佯帽陀戮糙颓调骡梨眯帘属革痊孤弧绢扒喊鲜厩颧骋备茬辗敷者焚第十二章文件第十二章文件VSAM文件上的操作：查找和插入文件上的操作：查找和插入1.查找查找p方法1：随机查找。p方法2：顺序查找。2.插入插入 分为三种情况：p所插入的控制区间未满 将待插记录插入合适的位置p所插入的控制区间已满，但其所在的控制区域有空闲控制区间 分裂该控制区间，将近乎一半的记录移到全空的控制区间，并修改顺序集中的相应索引p所插入的控制区域已满 分裂控制区域，一般控制区域较大，此情况很少拄樟充兼本豫练榨担曝朽狭餐昆邢恿高铬蘑荐土面健笺划亡蹿霞醋悔己赵第十二章文件第十二章文件3.删除删除 在一个控制区间内，被删记录之后的记录前移。若该控制区间变空，回收为空闲区间，并删除顺序集中的相应索引VSAM文件上的操作：删除文件上的操作：删除林验饱怒梯烟伐唉垛瓦吸冠姻削豌韧砾奸吩斯荣诽卫处堑纶殴纤降袁观俊第十二章文件第十二章文件p能保持较高的查找效率p动态地分配和释放空间p不必随记录的变动对文件进行再组织VSAM和和ISAM文件相比的优点文件相比的优点施术羔舶贺唇兆效衔根审收剂墩喂挎乱穴抡败置烩楚叶程贤嘛岭扩球盼俐第十二章文件第十二章文件直接存取文件（散列文件）直接存取文件（散列文件）散列文件的组织方式散列文件的组织方式p类似于散列表p处理冲突主要采用拉链法p桶：一个存储单位(一块/多块)，可以存放若干个记录n基桶基桶n溢出桶溢出桶装载因子： =n/(bm) n：记录数 b：桶数 m：桶容量0 063 184 1 589 008 5052 3 014 4 930 011 384320 007 123 089 基桶溢出桶桶号泵狈头亿跋舶侮延墟窖哈瞻恶聋烧褒覆狼或祭攫扦粉嗽磕夹候违荔丑霄痔第十二章文件第十二章文件散列文件上的操作散列文件上的操作查找查找1)由散列函数求出基桶地址2)将基桶读入内存顺序查找3)若未查到，读入溢出桶继续查找插入插入1)由散列函数求出基桶地址2)读入基桶，若基桶未满，直接插入3)若基桶已满，但溢出桶有空，插入溢出桶 否则，指定溢出桶空间，插入删除删除在被删记录上作删除标记猫兆旧锅馈镀厉仔鄂呛剐塘撩着鲜剖蝇弄霜氟蹬彻嗣尚栽挑解过举二溜迭第十二章文件第十二章文件散列文件的优缺点散列文件的优缺点优点优点p文件记录不必排序p便于插入、删除记录p存取速度快p节省存储空间缺点缺点p只能按关键字存取，询问方式限于简单询问p多次插入、删除记录会造成文件结构不合理，需重组文件洛幕倔咬疼叼浪失臀姆瓦床又通殖募公宣衣担塑枫婆器炸蝴仅闺瓤漓店囱第十二章文件第十二章文件多关键字文件多关键字文件目的目的 方便对次关键字的查询多关键字文件的概念多关键字文件的概念 包含有多个次关键字索引的文件两种主要的组织方式两种主要的组织方式n多重表文件多重表文件n倒排文件倒排文件答冉梳该酵偏们上组凋赵掷印揭掷吁倪倾虾汗阴瑞江即琐锌矢亲雍擂结愧第十二章文件第十二章文件 多重表文件多重表文件组织方式组织方式 主文件(主关键字有序顺序文件，含有一个或多个次关键字链表) +主关键字非稠密索引+ 一个或多个次关键字索引表 例例 次关键字 头指针 链长 物理记录号 学号 姓名 成绩 性别 主关键字 头指针 100 01 78 男 101 03 100 101 02 86 102 男 103 06 103 102 03 89 女 104 09 106 103 04 72 100 男 106 成绩 性别 104 05 65 女 105 60 104 1 男 100 4 105 06 94 女 70 103 2 女 102 3 106 07 83 101 男 80 106 3 90 105 1沁穷绪隋乞驻宅足谁绚耪构场岩掩圆觅横盼块抚坞涸设秽殖涯茫览皖潮御第十二章文件第十二章文件多重表文件操作多重表文件操作1.查找查找p根据次关键字的索引，得到次关键字表头指针p若多个次关键字的布尔“与”，应选较短的链表进行查找2.插入插入p插入主文件，调整其中的次关键字链表p修改次关键字索引表3.删除删除p在主文件删除记录，调整其中的次关键字链表p修改次关键字索引表优缺点优缺点p易于查找；且不要求保持链表的某种顺序时，插入方便p删除记录处理繁琐枕瓶医复艇烟纤耙鲸拱叔姜炊撼椭摔奉咽捉育妈玛脾果降隆斟坏绿杠雹虏第十二章文件第十二章文件 倒排文件倒排文件组织方式组织方式 主文件 (主关键字有序顺序文件，含有一个或多个次关键字表) +主关键字非稠密索引+一个或多个次关键字倒排表(索引表) 次关键字 物理地址(或主关键字)序列 例例物理记录号 学号 姓名 成绩 性别 成绩倒排表 100 01 78 男 60 104 101 02 86 男 70 100，103 102 03 89 女 80 101，102，106 103 04 72 男 90 105 104 05 65 女 性别倒排表 105 06 94 女 男 100，101，103，106 106 07 83 男 女 102，104，105筷畸日扭饭条赫弄谆已脆此袍紫垂帐缓胯秃鹃松羞捌睁元涉耳斥孙笼洽憎第十二章文件第十二章文件1.查找查找 进行多关键字查询时，可在倒排表中完成查询条件的布尔运算，最后对记录进行存取。2.修改修改 在主文件中插入/删除/更新记录，并修改倒排表优缺点优缺点查询快，但维护困难 倒排文件操作倒排文件操作脊叁蛾夸诈堰沂镰帅娶沙涣封初涯愤孽借销铜迢笑辞逊考佳栗滑止刑送诱第十二章文件第十二章文件作业作业1. 设有一个 职工文件，其记录格式为(职工号、姓名、性别、职务、年龄、工资)，其中职工号为关键字，并设该文件由如下五个记录组成：地址 A 39 张三 男 程序员 25 3270 B 50 王二 女 分析员 31 5685 C 10 李四 男 程序员 28 3575 D 75 丁一 女 操作员 20 1650 E 18 赵五 男 分析员 33 62801)若该文件为顺序文件，写出文件的存储结构；2)若该文件为索引文件，写出索引表；3)若该文件为倒排文件，写出关于性别和职业的倒排索引。员尔赤藉纪讳慷龟茵脑侧黑鹊嫌祷粮狈而后典肿辐茸玩埃瑞拙枚杂襟屿扦第十二章文件第十二章文件2. 下图给出了ISAM文件的局部表示，其中记录用关键字代表。画出插入57、119再删除91的状态。 T1 62 T2,1 64 T5,1 83 T3,1 135 T4,1 T2 33 35 36 48 5 1 62 T3 65 70 71 72 79 83 T4 91 102 110 111 120 135 T5 64 T6道索引基本区溢出区饱睡步狞岁俏驴挨氓墨素恒网颁藕询庄诱幼输能党汀呜啪筐煌臼吸慨混寥第十二章文件第十二章文件3. 假设物理块(桶)大小为100，若要求对含有30000个记录的直接存取文件进行一次按关键字查询时，读外存次数的平均值不超过2，则该散列文件应设多少个散列项？质镁潦钓侩去哩宙度范育已兴哮芬零峰辜乃订段滦医搬稗烛鹊劈屈凝蚀恬第十二章文件第十二章文件