0002 2 2 1 1 1 00011122333444555666 7 7 7Sector #Track #013Surface #...2 2S-2S-1R/W Heads0 1 2 3 4 5 6 7 8 9 10 11 13 14 15 12 16 17 18198-15 are onsurface 1(on the bottom of the disk) Logical View of Disk as Linear Collection of Blocks0 1 2(track #, surface #, sector #) to(0,0,0) (0,0,1) (0,0,2) Linear block # mappingAll of cylinder 0 All of cylinder 1track # surface # sector #Bits of linear block # : . . .1. Disk-access time = (seek time) + (rotational delay) + (date transfer time). How is each component of the disk-accesstime effected by increasing the disk's RPMs (revolutions per minute)?b) If we want fast access to a collection of sectors, where can we place them to minimize seek time and rotationaldelay?Data Structures (810:052) Lecture 22 Name:_________________Lecture 22 Page 1User Program - HLL programming language make system calls to OS to: 1. open file - establish a link between file variable and file for either reading, writing, or both2. access file - read or write one piece of data at a time (e.g., char., record, etc.)3. close file - flush changes to disk Operating System - manage and control access secondary storage through its file system which containsinformation about every file: location on disk, ownership and security/protectionOS maintains free disk space "list"OS views disk as linear sequence of blocks (block 0, block 1, etc.), but assumes closeness in block # means close with respect to access time.Secondary Storage - accepts R/W requests from OS for block# and maps block# to internals physical address Device(e.g., (track #, surface #, sector #) - more complex than above picture!)OS buffers some blocks in memory to improve efficiencyKinds of File Access:  serial/sequential files - open at the beginning and read sequentially from beginning to end linearly random-access files - “seek" to any position by specifying a byte-offset from the beginning of the file, record #, etc. random-access of a record by keyImplementation of Files on Disk- how are blocks allocated?2. non-contiguous - scattered across linear address space of OS and disklinked-list of blocks on disk File system meta-datafor file. . .a) What types of file access are supported efficiently?b) How easy is it for the file to grow in size? 3. contiguous - sequential collection of blocks from OS linear view of diskFile system meta-datafor file10 1412 1611 1513 181710a) What types of file access are supported efficiently?b) How easy is it for the file to grow in size?Data Structures (810:052) Lecture 22 Name:_________________Lecture 22 Page 24. file descriptor blocks - list of blocks hold the address of the physical location of data blocksFile system meta-datafor file2nd data 1st data 3rd data 0th data block inblock inblock inblock infilefilefilefilefile descriptorblock(s)pointerto nextfile descriptorblocka) What types of file access are supported efficiently?b) How easy is it for the file to grow in size?5. To implement "random-access of a record by key" in a file how might we use hashing?6. To implement "random-access of a record by key" in a file why would an AVL tree not work well?Data Structures (810:052) Lecture 22 Name:_________________Lecture 22 Page 37. A B+ Tree is a multi-way tree (typically in the order of 100s children per node) used primarily as a file-indexstructure to allow fast search (as well as insertions and deletions) for a target key on disk. Two types of pages (B+ tree"nodes") exist:  Data pages - which always appear as leaves on the same level of a B+ tree (usually a doubly-linked list too) Index pages - the root and other interior nodes above the data page leaves. Index nodes contain some minimum andmaximum number of keys and pointers bases on the B+ tree's branching factor (b) and fill factor. A 50% fill factorwould be the minimum for any B+ tree. All index pages must have ≤ # child ≤ b, except the root which must«b/2»have at least two children.Consider an B+ tree example with b = 5. 80 40 8 40 65 80 90 120 130 90 65 25 60 70 88 95 125 171 120 72 130a) How would to find 88?b) Where would you insert 50, 100, 105, 110, 180, 200, 210?8. For a B+ tree with a branch factor 201, what would be the worst case height of the tree if the number of keys was1,000,000,000,000?Data Structures (810:052) Lecture 22 Name:_________________Lecture 22 Page