CSC 675 Review 3 - Introduction to System Implementation Techniques

Question 1

Explain in your own words how data (bits) are stored on standard magnetic disk hardware.

Answer 1

The most basic unit of data on the disk is a single bit of information. A magnetic orientation in one direction on the disk could represent a “1”, an orientation in the opposite direction could represent a “0”.

Question 2

What is the minimum unit of data transfer to/from the disk?

Answer 2

The sector is the smallest unit that can be transferred to/from the disk, disk blocks are the smallest unit of transfer requested by the operating system.

Question 3

Why is it usually more efficient to transfer a larger amount of data to/from the disk?

Answer 3

One large request requires less processing requests. Less disk I/O.

Question 4

What are the major components of the time required to access a sector for data stored on disk?

Answer 4

• seek time, the r/w heads are moved to the proper cylinder, mechanical movement is slow and inaccurate
• the proper track is selected, fast electronic switch

• latency time,
- the head monitors the track until the proper sector rotates under the head, disks usually rotate 3600 rpm and about half a track will need to be scanned on average

• transfer time
- the data is transferred, typically very fast compared with seek time

Question 5

Describe two ways in which the sector access time can be reduced (without modifying the disk hardware).

Answer 5

1. Reduce the seek/latency for each I/O operation by maximizing sequentiality in data placement.
   • Hard to realize in a multi-user environment!
2. Reduce the total number of disk I/O
   • This may or may not require less I/O time in single user mode, but will probably require less I/O time in multi-user mode (when the disk is shared and every disk I/O operation is effectively random).

Question 6

Why is sequential disk I/O much faster than random disk I/O?

Answer 6

Sequential disk I/O is faster than random disk I/O because it requires less processing between transfers. The parts of the hard drive have to move around less to find the needed data.

Question 7

What is a file?

Answer 7

ordered sequence of file blocks

Question 8

What are two standard techniques for associating disk blocks into files?

Answer 8

(1) sequential: file blocks are stored in contiguous disk blocks.
(2) indexed: file blocks are indexed and stored in random disk blocks.

Question 9

Discuss the advantages and disadvantages of using sequential allocation for file blocks.

Answer 9

Fast sequential read/ write, difficult to allocate and deallocate disk space efficiently.

Question 10

Discuss the advantages and disadvantages of using indexed allocation for file blocks.

Answer 10

Slow read/write access, easy to allocate and deallocate disk space.

Question 11

Under what circumstances will sequential file I/O correspond to sequential disk I/O?

Answer 11

Sequential access within a file may or
may not correspond to sequential
access on the disk!!
–  Most mainframe operating systems and high-end
unix systems support high performance access.!
–  Most low-end unix systems and PC based
systems do not!
–  Most special purpose file systems implemented for use with DBS support sequential access.!

Question 12

Why is it important to store type information with records?

Answer 12

?

Question 13

What are some standard ways of storing type information.

Answer 13

Type information can be stored in a
variety of ways:

once per record set,

once per record (named record type),

once per field (named field type).

Question 14

What is blocking factor?

Answer 14

number of records per block

Question 15

How can blocking factor be used with the number of tuples in the file to calculate the file size?

Answer 15

records / blocking factor

Question 16

What is the record at a time interface?

Answer 16

Records have an order defined by the underlying file organization.

Interface provides means to filter

• current
• find
• findNext
• Delete

Question 17

How is it used by the DBS?

Answer 17

Basic file organization

Question 18

What is a storage structure?

Answer 18

a way to organize records on disk

Question 19

What is an access method?

Answer 19

organize information on the disk & retrieve individual records when requested by the run-time environment

Question 20

How are storage structures and access methods related?

Answer 20

access methods use storage structures to organize information

Question 21

What are the advantages and disadvantages of using an unordered file?

Answer 21

low insertion costs, high random & key sequential access costs.

Question 22

What are the advantages and disadvantages of using an ordered file?

Answer 22

high insertion costs, moderate random, low key sequential costs!

Question 23

What are the advantages and disadvantages of using a static hash file?

Answer 23

moderate insertion costs, low random, high key sequential costs

Question 24

What are the advantages and disadvantages of using a dynamic hash file?

Answer 24

index by high order

bits, no overflow blocks, exponential directory growth

Question 25

What are the advantages and disadvantages of using a B+ tree index?

Answer 25

moderate insertion, random & key sequential costs.

Question 26

What is the difference between a primary index and a clustering index?

Answer 26

primary index - built on primary key

physically ordered on non-key field

Question 27

What is a secondary index?

Answer 27

Secondary Index: Indexing field

Key field: dense index. Index ordered,
block pointers in index.

Non-key field: dense index, repeating field for duplicates, indirect index level (index points to block of pointers with same values).

Question 28

How does a secondary index differ from a primary index?

Answer 28

?

Question 29

Why is it possible to have any number of secondary indexes on a file, but at most one primary index?

Answer 29

?

Question 30

What is a B tree?

Answer 30

a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children.

Question 31

How are random and key sequential access performed using a B-tree?

Answer 31

Random access: partial root-leaf traversal

Sequential access: extended in-order
traversal

Question 32

what is a B+ tree?

Answer 32

make tree shorter by storing records in leaves and index entries only in internal nodes. This introduces some redundancy, but increases performance, especially for key sequential access.

Question 33

How are random and key sequential access performed using a B+ tree?

Answer 33

Random access: root-leaf traversal

Sequential access: scan data blocks
sequence set pointers

Question 34

Describe the structure of an index node in a B+ tree. How is the number of entries per B+ tree index node determined?

Answer 34

2d key + record value slots, 2d+1 pointer slots (order = 2d+1, or d)

Question 35

How is the number of entries per B+ tree index node determined?

Answer 35

?

Question 36

What are some of the different strategies for implementing record pointers( i.e. for secondary index construction)?

Answer 36

Offset in file

RID: record ID (block number + slot number)

TID: tuple ID (unique system generated value stored with each tuple)

Primary Key (unique attribute data value stored with each tuple)

Question 37

What are the advantages for each?

Answer 37

access time vs. Data Independence