02. File Structures - cs.kangwon.ac.kr

1 1 (Advanced Data Structures )(Advanced Data Structures )File StructuresFile Structures20062006 Page 2 Advanced Data Structuresby Yang-Sae MoonFile Structures File Structures (Ch. 1 in ) (Ch. 2 in ) (Ch. 3 in ) (Ch. 4 in ) , concept (O/S Device Dependent )File Structures2 Page 3 Advanced Data Structuresby Yang-Sae Moon (Information) (Data)File Structures (data) (processing) (information)(Computer)(in disk, tape, ..)DII = P(D)P Object = Variables(Attributes or Data) +Methods(Processing Mechanism)Page 4 Advanced Data Structuresby Yang-Sae Moon (1/2)(1/2) (field), (attribute), (item) ( : , ) (object, entity) (table) attribute (record type) ( ) ( : = {.)}

2 }) (record instance) (record) ( : { , 2005012345, , ..}) record occurrence File Structures3 Page 5 Advanced Data Structuresby Yang-Sae Moon (2/2)(2/2) (file) ( ) (set of records) ( : , , , , ) ( ) ? (main memory) .. , . (independency) . ( .)File StructuresPage 6 Advanced Data Structuresby Yang-Sae Moon (1/3)(1/3) (master file) (transaction file) (work file) (program file) : (report file), (text file) (mater file) : , , , , ( ) (permanent) ( : )File Structures4 Page 7 Advanced Data Structuresby Yang-Sae Moon (transaction file) (update) (insert) (delete) (modify, replace) ?

3 ( : , ) (All done or not done)File Structures (2/3)(2/3)Page 8 Advanced Data Structuresby Yang-Sae Moon (work file) ( ) ( ) (temporary file) , : Merge Sort : (program file) (C, Java), , (SQL ) File Structures (3/3)(3/3)5 Page 9 Advanced Data Structuresby Yang-Sae Moon (input file): , (read) (output file): , (write) (input & output file): , File Structuresprograminput fileoutput fileinput & output filePage 10 Advanced Data Structuresby Yang-Sae Moon fopen(.)

4 , O_CREAT) write(..), fprintf(..), .. (update) (insert) (delete) read(..), fscanf(..), .. unlink(..) fopen(..), fclose(..), open(..), close(..), .. File Structures6 Page 11 Advanced Data Structuresby Yang-Sae Moon (1/4)(1/4) (main memory)- - (random access) (secondary storage) ( )- - (volatility) (activity) (frequency of use) (response time) (file size) File StructuresPage 12 Advanced Data Structuresby Yang-Sae Moon (2/4)(2/4) (volatility) - ( )- ( ) - - ( ) (activity)

5 Update , ( ) File Structures7 Page 13 Advanced Data Structuresby Yang-Sae Moon (3/4)(3/4) (frequency of use) - ( )- ( / ) - (sequential access)- (random access) (response time) strict (real-time) , File StructuresPage 14 Advanced Data Structuresby Yang-Sae Moon (4/4)(4/4) (file size) (trivial) ( , ) (free space ) - vs.

6 - vs. File Structures8 Page 15 Advanced Data Structuresby Yang-Sae MoonFile Structures File Structures (Ch. 1 in ) (Ch. 2 in ) (Ch. 3 in ) (Ch. 4 in )File StructuresPage 16 Advanced Data Structuresby Yang-Sae Moon (storage device) (medium) + (device) : physical disk + disk controller (storage media) (physical disk) (volatile) vs. (nonvolatile) disk vs. memory (access device or access mechanism) (read) (write) ( ) : disk controller(driver), tape driverFile Structures9 Page 17 Advanced Data Structuresby Yang-Sae Moon (memory & storage)(memory & storage)1 (primary storage) (main memory)- ( ) - / (cache memory)- , CPU Chipset - , Primary(L1 Cache), Secondary(L2 Cache) 2 (secondary storage) (magnetic disk)- ( ) - - ( ) CPU (optical disk), (magnetic tape) File StructuresPage 18 Advanced Data Structuresby Yang-Sae Moon (1/3)(1/3) (cache memory) SRAM(Static Random Access Memory)

7 CPU Chipset KB ~ MB (main memory) ( , ) DRAM(Dynamic Random Access Memory) , ( ) MB ~ GB File Structures10 Page 19 Advanced Data Structuresby Yang-Sae Moon (2/3)(2/3) (flash memory) , (nonvolatile) , MP3 Player, PDA / MB ~ GB (magnetic disk) ( ) ( ) , GB ~ TB (disk array )File StructuresPage 20 Advanced Data Structuresby Yang-Sae Moon (3/3)(3/3) (optical disk) , , CD-ROM, CD-R, CD-RW, DVD(digital video disk), DVD-ROM (magnetic tape) ( ) , File Structures11 Page 21 Advanced Data Structuresby Yang-Sae Moon File Structures Page 22 Advanced Data Structuresby Yang-Sae Moon (Hard Disk) (1/2)(Hard Disk) (1/2)File Structures (hard disk): 1995 IBM 5MB (flexible disk): floppy disk, diskette (~ MB) (gap).

8 (track): (gap) ( ) (sector): (block ) : (disk pack) , tracksectorgapcylinder12 Page 23 Advanced Data Structuresby Yang-Sae Moon (Hard Disk) (2/2)(Hard Disk) (2/2)File Structures , 1) ( ) ( ),2) ( ),3) . Seek time(= s): ( ) Rotational latency( = r): , Transfer time(= t): ( ) Transfer rate: (MBps) ( ) seek time rotational time (clustering, locality.

9 Page 24 Advanced Data Structuresby Yang-Sae Moon (Floppy Disk)(Floppy Disk)File Structures (flexible) 1970 IBM : 5 inch, 3 inch : 360 rpm ( , 5400 ~ 10K rpm in hard disks) ( ): ( 1K ) ?: CD-ROM USB Driver ( K )13 Page 25 Advanced Data Structuresby Yang-Sae Moon (Blocking) (1/5)(Blocking) (1/5)File Structures (block) ( ) = b x B-b = number of blocks in a track-B = block size ( ) : 512 bytes, 1024 bytes, 2048 bytes : 4096 bytes, 8192 bytes, more .. , ( , 8KB , 1 byte 8KB ,1 byte 8KB.)

10 Page 26 Advanced Data Structuresby Yang-Sae Moon (Blocking) (2/5)(Blocking) (2/5)File Structures (blocking) I/O , ( ) ( , ) (blocking factor) Bf = B/R -B = (block size)-R = (fixed or variable) I/O (bulk read & write) ,fragmentation (for fixed length records) (spanning) : , : , 14 Page 27 Advanced Data Structuresby Yang-Sae Moon (Blocking) (3/5)(Blocking) (3/5)File StructuresR1R2R3R4R5R6R7R8R1R3R4R2R4R6R5 R6R9R7R10R11R12R13R1R3R2R4R5R6R7R8R9R10R 9 1 2 1 2 1 2 Page 28 Advanced Data Structuresby Yang-Sae Moon (Blocking) (4/5)(Blocking) (4/5)File Structures : (n = nx R or (n-1) x R).