Lab 4: Record formats; index structures

Task 1: Construct fixed-length and variable-length records

Imagine that we are working with the Room table from the university database that we used in Lab 2 and Lab 3. That table has the following schema:

Room(id CHAR(4), name VARCHAR(20), capacity INT)

Consider the following tuple from that table:

('0123', 'PHO 206', 199)

1. If we use the fixed-length record format discussed in lecture, what would the record look like for this tuple?

2. What is the length in bytes of this record if we assume that:

   • characters are one byte each
   • integer data values are four bytes each.

3. Now assume that we are using the third type of variable-length record discussed in lecture, in which each record begins with a header of field offsets. What will the record look like for the above tuple? In addition to one-byte characters and four-byte integer data values, you should assume that we use two-byte integers for integer metadata like lengths and offsets.

4. What is the length in bytes of the record from part 3?

5. Now imagine that the room didn’t have a name and we used a value of NULL to indicate this:

   ('0123', NULL, 199)
   

   How would the answer to part 3 change?

Task 2: Perform insertions in a B-tree

Consider the following diagram, which shows a portion of a B-tree of order 2:

We are only showing the keys, which we assume are integers. We are not showing the values associated with each key.

What would the tree look like after we insert each of the following?

1. an item (i.e., a key-value pair) whose key is 19
2. an item whose key is 25
3. an item whose key is 41
4. an item whose key is 40

Task 3: Perform insertions in a B+tree

Consider the following diagram, which shows a portion of a B+tree (note the + symbol!) of order 2:

Note that this tree is similar to the initial tree in Task 2, but some keys are missing, and other keys appear in two places.

0. Why does it make sense that we have repeated keys?

What would the tree look like after we insert each of the following?

1. an item (i.e., a key-value pair) whose key is 19
2. an item whose key is 25
3. an item whose key is 41
4. an item whose key is 40

Task 4: Perform dynamic linear hashing

Another type of index structure used by a DBMS is an on-disk hash table. For the purposes of this exercise, assume that:

• The hash table is being maintained using dynamic linear hashing.

• The items have integer keys, and we are using the following hash function:

  h(k) = k % 10
  

• We grow the table whenever the number of items (f) becomes more than twice the number of buckets (n).

Here is the current state of the table:

0 [1000, 972]
1 [713]

Note: With only two buckets, we use the rightmost 1 bit of the hash code’s binary value to determine which bucket it belongs in. That’s because log₂ 2 = 1. More generally, for a table with n buckets, we use the rightmost i bits, where i is obtained by computing log₂ n and rounding up if the result is not an integer.

What would the table look like after we insert each of the following?

1. an item (i.e., a key-value pair) whose key is 12

2. an item whose key is 436

3. an item whose key is 113

4. an item whose key is 116

Extra-practice on record formats

Consider the Room table from Task 1:

Room(id CHAR(4), name VARCHAR(20), capacity INT)

and assume that we are again inserting the following record into that table:

('0123', 'PHO 206', 199)

1. If we use the second type of variable-length record discussed in lecture – in which each field is preceded by its length – what would the record for the above tuple look like?

2. What is the length in bytes of this record? Use the same assumptions about the sizes of characters, integer data values, and integer metadata that we made in Task 1.

Extra-practice on B-trees and B+trees

1. Insert the following sequence of keys into an initially empty B-tree of order 2:

   51, 3, 10, 77, 20, 40, 34, 28, 61, 80, 68, 93, 90, 97, 14
   

2. Insert the same sequence of keys into an initially empty B+tree of order 2.

   1. Before performing the insertions, do you expect the result to be the same or different? Why?

   2. Perform the sequence of insertions and draw the B+tree as it is formed.

3. How would you perform a range search on this tree for all keys in the range (25, 60)? Why is such a query easier in a B+tree than it is in a standard B-tree?

Last updated on October 2, 2024.