《数据结构讲义》PPT课件.ppt

《《数据结构讲义》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构讲义》PPT课件.ppt（20页珍藏版）》请在三一办公上搜索。

1、2023/7/30,1,数据结构（C语言版）严蔚敏吴伟民清华大学出版社,授课老师：李 纲 电子邮箱：,2023/7/30,2,第十二章文件,存储器的分类磁盘缓冲区和缓冲池文件概念、分类及操作,2023/7/30,3,存储器的分类,主存储器随机访问存储器(内存,RAM,Random Access Memory)高速缓存(cache)视频存储器(显存,video memory)辅助存储设备硬盘(包括移动硬盘)磁带,2023/7/30,4,内、外存的区别,存储空间内存(RAM,cache)存储空间较小外存存储容量大存储器价格(1996年初数据)内存价格最贵磁带价格最便宜磁盘价格介于二者之间，比内存价

2、格便宜得多,2023/7/30,5,内、外存的区别,信息存储的永久性(persistant)内存信息在电源关闭后立即消失辅助存储器的信息在电源关闭后不会消失信息访问的时间(1996年初数据)访问存储在磁盘上的一字节数据需要10至15微秒访问存储在内存上的一字节数据需时约70纳秒(十亿分之70秒)RAM与磁盘访问的时间差异在十万到一百万倍之间形象的比较：在内存访问中如果花费20秒能够完成，则进行相同数据量的访问在外存中则需要花费约两个月的时间对程序设计的启示：尽量减少磁盘访问的次数适当安排信息，使得从辅助存储器中访问数据时，尽可能少的访问次数甚至做到一次访问就得到需要的数据（合理组织文件的结构）

3、合理组织文件信息，使每次磁盘访问能得到更多的信息，减少将来访问的次数（磁盘缓存技术）,2023/7/30,6,第十二章文件,存储器的分类磁盘缓冲区和缓冲池文件概念、分类及操作,2023/7/30,7,文件的两种形式,程序员的文件视图(C+)存储在磁盘上的连续的字节这些字节可以结合起来形成记录此文件视图称为逻辑文件(logical file)目的是方便用户使用操作系统的文件视图通常不是一段连续的字节，而是成块地分布在整个磁盘中此文件视图称为物理文件(physical file)，代表数据的实际存储情况结构的组织要考虑高效访问（提高空间利用率并减少存取时间）,2023/7/30,8,文件的两种形式

4、,文件管理器（file manager,属于操作系统的一个部分）处理从逻辑文件得到的数据的请求，并将此请求映射到磁盘中数据的物理位置当向文件中相对于文件开始处的一个特定逻辑字节位置写入时，此位置也必须被文件管理器转换成磁盘中相应的物理位置了解磁盘的意义要想对文件的数据请求（访问和读、写）操作的大致时间开销有所了解，必须知道磁盘的物理结构和基本工作方式,2023/7/30,9,磁盘,磁盘的访问形式磁盘通常称为直接访问（direct access)存储设备硬盘读写的主要部件读/写磁头盘片主轴盘片硬盘读写数据的步骤移动读写磁头放到包含数据的磁道上，该移动称为一次搜索包含数据的扇区必须旋转到磁头的下面

5、（等待磁盘把需要的扇区转到读写磁头的下面花费的时间称为旋转延迟）数据的实际传输（磁盘的设计并不是在每次请求读取一个bit的数据而是读取整个扇区的数据。因此，扇区就是一次读写的最小数据的单位）,2023/7/30,10,磁盘文件组织原则及访问开销,最好将一个文件的所有扇区都放在一起搜索（一般是读写花费时间最多的部分）时间慢如果读出了文件的一部分很可能就要读出文件相邻的下一个部分（称为引用的局部性）访问开销访问磁盘中一个扇区时，其基本开销一般是搜索时间当随机访问一个磁盘扇区时，当前磁道和目标磁道的平均距离是磁盘中磁道总数的1/3，此开销是在随机的二个磁道间搜索时所有可能情况的平均距离搜索n个磁道距

6、离的开销可用方程 f(n)=t*n+s（t是跨越一个磁道的时间，s是启动时间）举例：675MB的Maxtor磁盘驱动器，t=0.08ms,s=3ms，n=612该磁盘驱动器的搜索时间可计算为：0.08*612/3+319.3ms,2023/7/30,11,磁盘文件访问开销,磁道中的扇区访问时间等待要读取的扇区通过读写磁头下面所需的时间（旋转延迟）扇区经过磁头时间举例假定一个磁盘总共容量（名义上）有675MB，分布在15个盘片上，每个盘片上有45MB，每个盘片上有612个磁道，每个磁道包含150个扇区，每个扇区有512个字节。I/O磁头的启动时间是3ms,在一次搜索时磁头跨过1个磁道的时间是0.

7、08ms,假定操作系统维护的簇大小是8个扇区（4KB），每个磁道有18个扇区（其余的空间就丢弃了），旋转一次需要16.7ms。根据这一信息我们可以估计出磁盘访问的开销（平均访问时间,average access time）0.08*612/3+3+16.7/2+1/150*16.7 27.8ms,2023/7/30,12,第十二章文件,存储器的分类磁盘缓冲区和缓冲池文件概念、分类及操作,2023/7/30,13,缓冲区,使用缓冲区的原因读取一个bit的信息与读取一个扇区的数据，其所需时间相差不明显几乎所有磁盘驱动器都自动读取或写入整个扇区的信息缓冲区概念磁盘读取一个扇区的数据，就将信息存储在主

8、存中，称为缓冲或存信息经验规律：逻辑文件中大多数的磁盘请求都接近于前一次请求的位置。因此，下一次磁盘请求很可能直接在磁盘缓冲区中找到所需的数据，而不需对实际的磁盘数据进行访问,2023/7/30,14,缓冲池（buffer pool）,概念缓冲区的集合，采用类似线性链表的数据结构维护缓冲区目的是增加在主存中的信息量，从而不必直接对磁盘进行访问缓冲池的更新方法“最不频繁使用”方法（LFU）记录缓冲池中每个缓冲区的访问次数当缓冲池满，而新的信息要进入缓冲区时，被访问次数最少的缓冲区就被认为包含“最不重要的信息”而被新的信息替换由于过去引用多次（有较大的引用计数），但现在可能很少使用。因此，需要引入

9、时间机制，使超过某时间长度阈值的缓冲区信息被新信息替换，而不考虑其访问次数的多少“最近最少使用”方法（LRU）每访问一个缓冲区中的信息，就将此缓冲区放到链表的最前面当必须以新信息替换缓冲区中信息时，就使用链表最后面的缓冲区，其中“老”信息就丢弃了,2023/7/30,15,第十二章文件,存储器的分类磁盘缓冲区和缓冲池文件概念、分类及操作,2023/7/30,16,基本概念及分类,定义是由大量性质相同的记录组成的集合文件分类按记录的类型操作系统文件一维的连续的字符序列，数据无结构、无解释数据库文件带有结构的记录的集合，由一个或多个数据项组成是文件中可存取的数据的基本单位按文件中记录的长度记录信息

10、长度相同，称为定长记录记录信息长度不相等，称为不定长记录,2023/7/30,17,基本概念及分类,根据记录中关键字的多少单关键字文件多关键字文件文件的逻辑结构和物理结构逻辑结构（程序员的文件视图）物理结构（物理存储器中的文件视图）两者的对应关系一个物理记录存储一个逻辑记录一个物理记录包含多个逻辑记录多个物理记录表示一个逻辑记录,2023/7/30,18,文件的操作,操作类型检索顺序存取：存取当前逻辑记录的下一个逻辑记录直接存取：存取第i个逻辑记录修改插入一个记录删除一个记录更新一个记录操作方式实时操作适用于对文件中数据需要实时检索和更新的场合批处理操作适用于对文件中数据的请求不需立即回应的场合,2023/7/30,19,顺序文件及其操作,概念记录按其在文件中的逻辑顺序依次存储在存储设备中而建立的文件物理记录的顺序与逻辑记录顺序一致存储方式连续文件：次序相继的两个物理记录在存储器中的物理存储位置相邻串联文件：物理记录间的次序是由指针链接来表示逻辑上类似于线性表的顺序存储（连续文件）和链式存储（串联文件）,2023/7/30,20,顺序文件及其操作,顺序文件的操作特点存取第i个记录，必须依次访问它之前的i-1个记录插入的新记录只能加在文件的末尾如果需要对文件中的某个记录进行更新，必须将整个文件进行复制(因此适合对文件以批处理的方式进行批量修改，而不适合随机更新单个记录),