Ho Chi Minh City University of Technology Faculty of Computer Science and Engineering Chapter 2: Disk Storage and Basic File Structures Database Management Systems (CO3021) Computer Science Program Dr. Võ Thị Ngọc Châu (chauvtn@hcmut.vn) Semester 1 – 2020-2021 Course outline Chapter 1. Overall Introduction to Database Management Systems Chapter 2. Disk Storage and Basic File Structures Chapter 3.
Indexing Structures for Files Chapter 4. Query Processing and Optimization Chapter 5. Introduction to Transaction Processing Concepts and Theory Chapter 6. Concurrency Control Techniques Chapter 7.
Database Recovery Techniques 2 References [1] R. Navathe, Fundamentals of Database Systems- 6th Edition, Pearson- Addison Wesley, 2011. Navathe, Fundamentals of Database Systems- 7th Edition, Pearson, 2016. Widom, Database System Implementation, Prentice-Hall, 2000.
Widom, Database Systems: The Complete Book, Prentice-Hall, 2002 [4] A. Sudarshan, Database System Concepts –3rd Edition, McGraw-Hill, 1999. Other File Structures 2. Today’s Storage Technologies 2.
Physical Storage in Today’s DBMSs 4 2. Disk Storage Databases A collection of data and their relationships Computerized Stored physically on computer storage media Primary storage Secondary storage Tertiary storage (Third-level storage) The DBMS software can then retrieve, update, and process the data as needed. 5 Computer Organization - Hardware Computer Architecture ALU = Arithmetic/logic gate unit: performing 6 arithmetic and logic operations on data 2. Disk Storage Memory hierarchy and storage devices The highest-speed memory is the most expensive and is therefore available with the least capacity.
The lowest-speed memory is offline tape storage, which is essentially available in indefinite (without clear limits) storage capacity. Primary storage level Secondary and tertiary storage level - Register - Magnetic disk - Cache (static RAM) - Mass storage (CD-ROM, DVD) - DRAM (dynamic RAM) - Tape 7 2. Disk Storage Types of storage with capacity, access time, max bandwidth (transfer speed), and commodity cost Table 16. Navathe, Fundamentals of Database Systems- 7th Edition, Pearson, 2016.
Disk Storage Storage organization of databases Databases typically store large amounts of data that must persist over long periods of time. Persistent data (not transient data which persists for only a limited time during program execution) Most databases are stored permanently (or persistently) on magnetic disk secondary storage. Database size No permanent loss of stored data with nonvolatile storage Storage cost 9 2. Disk Storage Magnetic disks Disks are covered with magnetic material.
The most basic unit of data on the disk is a single bit of information. By magnetizing an area on a disk in certain ways, one can make that area represent a bit value of either 0 (zero) or 1 (one). To code information, bits are grouped into bytes (or characters): 1 byte = 8 bits, normally. The capacity of a disk is the number of bytes it can store.
Whatever their capacity, all disks are made of magnetic material shaped as a thin circular disk. Disk Storage (a) A single-sided disk with read/write hardware. (b) A disk pack with read/write hardware. Disk Storage Different sector organizations on disk.
(a) Sectors subtending a fixed angle. (b) Sectors maintaining a uniform recording density. Disk Storage Magnetic disks A disk is single-sided if it stores information on one of its surfaces only and double-sided if both surfaces are used. To increase storage capacity, disks are assembled into a disk pack.
Information is stored on a disk surface in concentric circles of small width, each having a distinct diameter. Each circle is called a track. In disk packs, tracks with the same diameter on the various surfaces are called a cylinder. Disk Storage Magnetic disks A track is divided into smaller blocks or sectors.
The division of a track into sectors is hard-coded on the disk surface and cannot be changed. One type of sector organization calls a portion of a track that subtends a fixed angle at the center a sector. The division of a track into equal-sized disk blocks (or pages) is set by the operating system during disk formatting (or initialization). Block size is fixed during initialization and cannot be changed dynamically: from 512 bytes to 8,192 bytes.
Disk Storage Magnetic disks A disk with hard-coded sectors often has the sectors subdivided or combined into blocks during initialization. Not all disks have their tracks divided into sectors. Blocks are separated by fixed-size interblock gaps, which include specially coded control information written during disk initialization. This information is used to determine which block on the track follows each interblock gap.
Disk Storage Magnetic disks Transfer of data between main memory and disk takes place in units of disk blocks. A disk is a random access addressable device. The hardware address of a block = a combination of a cylinder number, track number (surface number within the cylinder on which the track is located), and block number (within the track) For a read command, the disk block is copied into the buffer; whereas for a write command, the contents of the buffer are copied into the disk block. Disk Storage Magnetic disks The device that holds the disks is referred to as a hard disk drive.
A disk or disk pack is mounted in the disk drive, which includes a motor that rotates the disks. Disk packs with multiple surfaces are controlled by several read/write heads—one for each surface. Disk units with an actuator are called movable-head disks. Disk units have fixed read/write heads, with as many heads as there are tracks.
A read/write head includes an electronic component attached to a mechanical arm. All arms are connected to an actuator attached to another electrical motor, which moves the read/write heads together and positions them precisely over the cylinder of tracks specified in a block address. Once the read/write head is positioned on the right track and the block specified in the block address moves under the read/write head, the electronic component of the read/write head is activated to transfer the data. Disk Storage Magnetic disks A disk controller, typically embedded in the disk drive, controls the disk drive and interfaces it to the computer system.
The controller accepts high-level I/O commands and takes appropriate action to position the arm and causes the read/write action to take place. Locating data on disk is a major bottleneck in database applications. Minimizing the number of block transfers is needed to locate and transfer the required data from disk to main memory. Disk Storage Disk parameters Block size: B bytes Interblock gap size: G bytes Disk speed: p rpm (revolutions per minute) Seek time: s msec Rotational delay: rd msec Block transfer time: btt msec Rewrite time: Trw msec Transfer rate: tr bytes/msec Bulk transfer rate: btr bytes/msec 19 2.
Disk Storage Disk parameters Rotational delay: waiting time for the beginning of the required block to rotate into position under the read/write head once the read/write head is at the correct track rd = (1/2)*(1/p) min = (60*1,000)*(1/2)*(1/p) msec = 30,000/p msec 20 2. Disk Storage Disk parameters Block transfer time: time to transfer the data in the block once the read/write head is at the beginning of the required block btt = B/tr msec If only useful bytes are considered, block transfer time is estimated with bulk transfer rate. btt = B/btr msec 21 2. Disk Storage Disk parameters Rewrite time: time for one disk revolution.
This is useful in cases when we read a block from the disk into a main memory buffer, update the buffer, and then write the buffer back to the same disk block on which it was stored. In many cases, the time required to update the buffer in main memory is less than the time required for one disk revolution. If we know that the buffer is ready for rewriting, the system can keep the disk heads on the same track, and during the next disk revolution the updated buffer is rewritten back to the disk block. Trw = 2*rd msec = 60,000/p msec 22 2.
Disk Storage Disk parameters Transfer rate: the number of data bytes transferred in a time unit (msec) 23 2. Disk Storage Disk parameters Bulk transfer rate: the rate of transferring useful bytes in the data blocks btr = (B/(B+G))*tr bytes/msec 24 2. Disk Storage The average time needed to find and transfer one block, given its address, is estimated by: (s + rd + btt) msec The average time needed to find and transfer any k blocks, given the address of each block, is: k*(s + rd + btt) msec The average time needed to find and transfer consecutively k noncontiguous blocks on the same cylinder, given the address of each block, is: (s + k*(rd + btt)) msec The average time needed to find and transfer consecutively k contiguous blocks on the same track or cylinder, given the address of the first block, is: (s + rd + k*btt) msec The estimated time to read k contiguous blocks consecutively stored on the same cylinder, when the bulk transfer rate is used to transfer the useful data, is: (s + rd + k*(B/btr)) msec 25 2. Disk Storage Making data access more efficient on disk Buffering of data Proper organization of data on disk Reading data ahead of request Proper scheduling of I/O requests Use of log disks to temporarily hold writes Use of flash memory for recovery purposes 26 2.
Disk storage Making data access more efficient on disk Buffering of data Buffer: a part of main memory that is available to receive blocks or pages of data from disk Buffer manager: a software component of a DBMS that responds to requests for data and decides what buffer to use and what pages to replace in the buffer to accommodate the newly requested blocks (1) to maximize the probability that the requested page is found in main memory (2) in case of reading a new disk block from disk, to find a page to replace that will cause the least harm in the sense that it will not be required shortly again Double buffering: a technique for more efficiency 27 2. Disk Storage Making data access more efficient on disk Double buffering: a technique for more efficiency, using two buffers Double buffering: use of two buffers, A and B, for reading from disk Figure 16. Disk Storage Making data access more efficient on disk Double buffering: a technique for more efficiency, using two buffers performing the I/O operation between the disk and main memory into one buffer area concurrently processing the data from another buffer continuous reading or writing of data on consecutive disk blocks, which eliminates the seek time and rotational delay for all but the first block transfer data is kept ready for processing, thus reducing the waiting time in the programs. Disk storage Making data access more efficient on disk Buffering of data To enable its operation, the buffer manager keeps two types of information on hand about each block (page) pin-count: the number of used times dirty-bit: 1 if updated; otherwise, 0 Buffer replacement strategies Least recently used (LRU) Clock policy: a round-robin variant of the LRU policy First-in-first-out (FIFO) Most recently used (MRU) 30 2.
File Operations Placing file records on disk Data in a database is regarded as a set of records organized into a set of files.