Topic 3 - Files and Indexing (Drives, RAID, Indices)

What are the Primary/Secondary/Tertiary types in the Storage Pyramid in order (fastest to slowest)?

Primary: CPU registers → Cache Memory → Main Memory

Secondary: Solid State Drives, Hard Disk Drives

Tertiary Storage: Tapes/Optical Disk Libraries

What section of storage in the Storage Pyramid is volatile, and what are the types in order from (fastest to slowest)?

The Primary Storage types are all volatile
CPU Registers → Cache Memory → Main Memory

What are the 4 main physical components of a Hard Drive?

1. Platters (hold data)

2. Axle (Spins the platters)

3. R/W Heads (R/W data)

4. R/W Arm (Moves the heads over the platters)

What is a sector/block?

The basic unit of transfer of information

Explain the 3 sources of delay (use names) for R/W operations on a HDD

1. Seek Time - Physical movement of the R/W heads takes time

2. Rotational Latency - Must wait for the block (on the platter) to rotate to where the head is positioned

3. Transfer Time - R/W data from/to the platter surface

What is disk mirroring?

Disk mirroring is the technique of writing the same data to two drives, s.t. the user has effectively two identical drives.

What are the advantages/disadvantages to RAID 1?

Advantages:

• System survives if one of the drives fails

• Opens the possibility for reading from both drives simultaneously

Disadvantages:

• Expense of 2x the # of drives

What level is RAID 0?

Striping

What is RAID 1?

Mirroring

What is disk striping?

Disk striping is a technique where logical units of data (like a file) are distributed across several disks

What are the advantages / disadvantages of RAID 0?

Advantages:

• Increases performance (since read/writes can be parallelized)

Disadvantages:

• Increased probability/chance of the system failing due to one of the drives failing (if one goes out, the whole system is unrecoverable)

• Lack of data replication

What are the four kinds of parity schemes in RAID?

even, odd, mark, none

Describe how the parity scheme works in RAID 4.

In RAID 4, a single drive stores all parity information across the other drives in use. If one of the drives fails, the data can be reconstructed using the parity drive and the information of the other surviving drives.

What is the minimum amount of physical disks required for parity schemes in RAID 4 / RAID 5, and explain why this is

Parity schemes require at least 3 drives to rebuild data if 1 drive fails. This is because using only 2 disks means the parity disk essentially becomes a mirrored disk.

In the minimum case of 3 drives, if 1 of any of drives dies, the system survives (either by rebuilding the data using the parity drive, or if the parity drive dies, rebuilding the parity drive using a new drive)

What is the difference between RAID 4 and RAID 5?

RAID 4 and RAID 5 both use a parity scheme to survive drive failures

4 stores all parity data on a single disk
5 distributes/stripes the parity data across all disks

Events A and B are independent if?

p(A intersect B) = p(A) * p(B)

What does RAID stand for? What did the “I” originally stand for?

Redundant Array of Independent Disks

Originally meant “Inexpensive”

Which RAID levels are standardized?

RAID levels 0-6

What is RAID 6? Min. # of disks? Main performance diff. to RAID 5? How many drives can fail concurrently and system survive?

Distributed “Double Parity” scheme, requires 4 disks.

Essentially the same as RAID 5, except 2 parity schemes are used, which allows for 2 drives to fail.

Compared to RAID 5, RAID 6 has slower write performance

What is the technology behind SSD storage called?

NAND-based non-volatile RAM

What are the advantages/disadvantages to SSDs?

Advantages

• No mechanical parts

• Excellent read performance

• Smaller physical size

Disadvantages

• Write speed is slow than read speed

• # of erasures per cell is limited (cells eventually die)

• More expensive than HDDs (per unit storage)

What is the definition of Blocking Factor (bf)?

The number of whole records that can be stored in a single block

What is Internal Fragmentation?

Unallocatable storage within an allocation unit (such as a block)

Give a brief informal description of how to calculate the byte amount of Internal Fragmentation in a block

Calculate blocking factor/bf (# of records that can fit in a block)

Find out how many bytes this is, and subtract it from the block size = Remainder is IF size in bytes

What are the two ways of locating records within a block? Explain both.

1. Fixed-Length Records

• a) Packed/Contiguous Allocation (use qty to index)

• b) Unpacked Allocation (use bitmap field to index)

2. Variable-Length Records

• Requires a record directory (location + length for each record)

What is the definition of an Index?

A file containing structured references to records of another file

What is a Candidate Key (CD)?

A key that is able to uniquely ID a record

What is a Primary Key (PK)?

The selected/chosen candidate key for that record

What is a Secondary Key?

Any non-candidate key

What is a Sort Key?

The key used to order records within a file

What are two ways of classifying an index, and strategies for both?

1. Ordered

• a) Single-level (Sorted file)

• b) Multi-level (B+Tree)

2. Unordered

• Hashing

What is a Primary Index? (Specifically, what 3 characteristics describe a Primary Index)

1. The indexed field is a candidate key

2. The index records are sorted on the key

3. The DB file records are sorted on the key

How many primary indices can exist per file?

At most one

What is a Clustered Index? (Specifically, what 3 characteristics describe a clustered Index)

1. The indexed field is a secondary key

2. The index records are sorted on the key

3. The DB file records are sorted on the key

Per file, the # of primary indices + the # of clustered indices cannot _________.

Exceed one

Index-to-file references can be per-record or per-block. What does this mean?

This is saying that indices can point to the exact location of a record, or to the block that it is located within

What is a Secondary Index? (Specifically, what 3 characteristics describe a secondary Index)

1. The indexed field is any field

2. The index records are sorted on the key

3. The DB file records are not sorted on the key

How many secondary indices can you have per file?

As many as you want, but special index construction may be needed

What is an example of a clustered index?

Student records where the clustered index is on the “Name” field (non-CK field, and clusters dusplicate names together when sorted)

What are the other two ways of categorizing indices? Explain both, give a pro for each

1. Dense Indices

• Holds a pointer to every record in the file of interest

• Allows existence search w/ index only

2. Sparse Indices

• Holds a pointer to blocks of records in the file of interest

• Faster to search the index, since it is smaller than dense