Storage and Retrieval

Question 1

What are the two types of database workload?

Answer 1

Transactional Workload (write intensive), Analytical Workload (read-intensive)

Question 2

What are logs?

Answer 2

Logs are used by databases to record the data in the database, they are read-only data files storing the records in sequence

Question 3

What is the disadvantage of log files?

Answer 3

Reading the file is in O(n) which is slow for a large databse

Question 4

How might log file access be sped up?

Answer 4

Using binary files rather than plain text

Question 5

How are records deleted form log files?

Answer 5

Instead of scanning the entire log to delete a record a special delete (tombstone) record is appended to the end

Question 6

What is a hash index?

Answer 6

An index for key-value data, similar to dictionaries.

Question 7

How is disk space managed for log files?

Answer 7

The log is broken into segments of a certain size by closing the file when it reaches a given size. Subsequent writes are on a new file.

Question 8

What is compaction?

Answer 8

The process of removing duplicate keys to reduce segment size.

Question 9

What are the advantages of a Hash table?

Answer 9

1. Sequential write operations are much faster than random access to disk
2. Crash Recovery can be easier since when updating a value you’re not actually overwriting its old content

Question 10

What are the disadvantages of a hash table?

Answer 10

1. The hash table must fit into memory
2. Range queries are not possible

Question 11

What are SSTables?

Answer 11

Sorted String Tables in which keys appear only once per segment and the log is sorted by key.

Question 12

How do SSTables locate keys?

Answer 12

A sparse selection of keys are held in memory pointing to segments. To find a specific key the segment is found by comparing alphabetically to the keys in index.

Question 13

How is the SSTables log kept sorted by key?

Answer 13

Using an AVL tree