Chapter 5 Record Storage & Primary File OrganizationsStorageMemory Hierarchies & Storage DevicesPrimary Storage Level of MemorySecondary Storage Level of MemoryFigure 5.1Terms Used in the Hardware Description of Hard DrivesSlide 8Slide 9Figure 5.2Terms Used in Measuring Disk OperationsSlide 12Slide 13Computing TimesProblems for Disk OperationsParallelizing Disk Access Using RAIDRAID LevelsSlide 18Figure 5.4Fig 5.5Fig 5.6RecordsVariable Length Records in FilesFig 5.7Spanned Vs Unspanned RecordsFig 5.8File OperationsFile StructureSlide 29Heap (Pile) Files (Unordered)Ordered (Sorted Files) RecordsAdvantages of Ordered FilesDisadvantages of Ordered FilesHashing TechniquesInternal HashingInternal Hashing (con’t)Collision ResolutionCollision Resolution (con’t)Fig 5.10 Page 140Goals of the Hash FunctionExternal Hashing for Disk FilesTypes of External HashingStatic HashingFig 5.11 Page 143Fig 5.12 Page 144Extendible HashingFigure 5.13 Page 146Overflow (Bucket Splitting)Slide 49Slide 50Slide showing how buckets are split under Extendible Hashing.Shrinking Extendible Hashing FilesLinear HashingLinear Hashing (Con’t)Slide 55Slide 56Slide showing how to split using linear hashing.Chapter 5 1Chapter 5Record Storage & Primary File OrganizationsChapter 5 2Storage•The are two general types of storage media that is used with computers. They are :–Primary Storage - This includes all storage media that can be operated on directly by the CPU (RAM , L1 and L2 Cache Memory)–Secondary Storage - This includes Hard Drives, CD’s and tape.Chapter 5 3Memory Hierarchies & Storage Devices•The Memory Hierarchy is based upon speed of access. However, this speed comes with a price tag attached which varies inversely with the access time of memory. Like cars the faster the memory access is the more it costs.Chapter 5 4Primary Storage Level of Memory•The Primary Storage Level of Memory is generally made up of 3 Levels.–L1 Cache which is located on the CPU –L2 Cache which is located near the CPU–Main Memory which is the RAM figure that is often referred to in computer advertisementsChapter 5 5Secondary Storage Level of Memory•The Secondary Storage Level of Memory may be made up of 4 Levels.–Flash Memory or EEPROM–Hard Drives –CD ROM’s–TapeChapter 5 6Figure 5.1Chapter 5 7Terms Used in the Hardware Description of Hard Drives•Capacity - The number of bytes it can store.•Single-sided vs. Double-sided - States if the disk/platter is written on one or both sides.•Disk Pack - A collection of disks/platters that are assembled together into a pack.•Track - A Circle of a small width on a disk. A disk surface will have many tracks.Chapter 5 8Terms Used in the Hardware Description of Hard Drives•Sector - A segment or arc of a track.•Block - is the division of a track into equal sized portions by the operating system.•Interblock Gaps - These are fixed sized segments that separate the blocks.•Read/Write Head - Actual reads/writes the information to the disk.Chapter 5 9Terms Used in the Hardware Description of Hard Drives•Cylinder - Tracks with the same diameter that are located on the disk surface of a disk pack.Chapter 5 10Figure 5.2Chapter 5 11Terms Used in Measuring Disk Operations•Seek Time (s)- The time it takes to position the read/write head on the desired track. It will be given in all problems that it is needed for.•Rotational Delay (rd) - The average amount of time it takes the desired block to rotate into position under the read/write head. Rd=(1/2)*(1/p) min where p is rpm of the diskChapter 5 12Terms Used in Measuring Disk Operations•Transfer Rate (tr) - The rate at which information can be transferred to or from the disk. tr =(track size)/(1/p min)•Block Transfer Time (btt) - The time it takes to transfer the data once the read/write head has been positioned. btt = B/tr msec where B is the block size in bytes.Chapter 5 13Terms Used in Measuring Disk Operations•Bulk Transfer Rate (btr) - The rate at which multiple blocks can be written/read to contiguous blocks. Where G is the Interblock Gap btr = (B/(B+G)) * tr bytes/msec•Rewrite Time (Trw) - Time it takes after a block is read to write that same block back to the disk or the time for one revolution.Chapter 5 14Computing Times•Given :–Seek Time (s) = 10 msec–Rotational speed = 3600 rpm–Track size = 50 KB–Block size (B) = 512 bytes–Interblock Gap = 128 bytesChapter 5 15Problems for Disk Operations•Compute the average time it takes to transfer 1 block on this system.•Compute the average time it takes to transfer 20 non-contiguous blocks that are located on the same track.•Compute the average time it takes to transfer 20 contiguous blocks.Chapter 5 16Parallelizing Disk Access Using RAID•RAID - Stands for Redundant Arrays of Inexpensive Disks or Redundant Arrays of Independent Disks.•RAIDs are used to provide increased reliability, increased performance or both.Chapter 5 17RAID Levels•Level 0 - has no redundancy and the best write performance but its read performance is not as good as level 1.•Level 1 - uses mirrored disks which provide redundancy and improved read performance.•Level 2 - provides redundancy using Hamming CodesChapter 5 18RAID Levels•Level 3 - uses a single parity disk.•Level 4 and 5 - use block-level data striping with level 5 distributing the data across all the disks.•Level 6 - uses the P + Q redundancy scheme making use of the Reed-Soloman codes to protect against the failure of 2 Disks.Chapter 5 19Figure 5.4Chapter 5 20Fig 5.5Chapter 5 21Fig 5.6Chapter 5 22Records•Records is the term used to refer to a number of related values or items. Each value or item is stored in a field of a specific data type.•Records may be of either fixed or variable lengths.Chapter 5 23Variable Length Records in Files•There are several reasons a record with the same record type may be of variable length.–Variable length fields–Repeating fields•For efficiency reasons different record types may be clustered in a file.Chapter 5 24Fig 5.7Chapter 5 25Spanned Vs Unspanned Records•When the records in a file is stored on a disk they may be placed in blocks of a fixed size. This will rarely match the record size. So a decision must be made when the record size is smaller than the block size and the block size is not a multiple of the record size whether to store the record all in one block and have unused space or in two different blocks.Chapter 5 26Fig