Sample Solutions to Midterm #2
You can ask the TAs or me (Ed) for more detailed explanations during office hours or after class; however, all mark changes must go through me, within 7 days.
Page 2 Q1. b Q2. a,b,c Q3. b,c,d
Page 3 Q4.
The first two keys fit in the empty root node:
70, 1260
Insert 40. This causes the first split:
70
40
Insert 2520. This causes the second split. Then, we can easily add 12.
70,1260
12,40 70 1260,2520
70,1260
1
Insert 8. This causes the third split. Then, we can easily add 9.
70
12
1260 1260,2520
1260 1260,2520
8,9
12,40
70
Insert 3. This causes the final split.
Page 4 Q5.
3
a)
b)
70
8,12
8,9 12,40 70
Insert 12 (causes split):
Global depth nub = 2 00→( 4,12, ) 01→( 1, 3, 5) 10→( 2, 6, ) 11 →
Localdepthnub=2 Localdepthnub=1 Localdepthnub=2 points to 01’s bucket
We need to insert two keys. They either both go into the “00” bucket, or both go into the “10” bucket.
For example, let’s insert 8 and 16 into the “00” bucket. This will cause a split of a local depth nub with a “2” in it, which means it will cause a doubling of the directory. This increases the global depth nub to 3. Here is what we get:
2
Page 5
Global depth nub = 3
000 → ( 8, 16, ) Local depth nub = 3 001→(1, 3, 5) Localdepthnub=1
010 → 011 → 100 → 101 → 110 → 111 →
( 2, 6, ) (4, 12, )
Local depth nub = 2 points to 001’s bucket Local depth nub = 3 points to 001’s bucket points to 010’s bucket points to 001’s bucket
Q6.
In the sort phase, a sorted run (SR) is the same as a “buffer pool fill”.
The first phase is the sort phase. It contains the first pass: Pass 0: ceiling( 12,000 pages / (60 pages / BP fill) )
= 200 SRs of size 60 pages each
The second phase is the merge phase. It contains the second pass:
Pass 1: ceiling( 200 inputSRs / (60 – 1) inputSRs / newSR ) = 4 newSRs
Of these 4 newSRs: 3 SRs have size: (59)(60) = 3540 pages 1 SR has size: 12,000 – 3(3540) = 1380 pages
A third pass is required. This produces the final, sorted file:
Pass 2: ceiling( 4 inputSRs / (60 – 1) inputSRs / newSR ) = 1 final SR of size 12,000 pages
Q7.
We need to completely fill the 3-level tree.
In the root node, we fill all 6 spots to capacity; so, there are 6 key-pointer pairs, plus one extra pointer. We sometimes call the root node: level-0.
The root node has 7 children. All 7 are level-1 nodes. We fill them to capacity (i.e., 6 key-pointer pairs, plus one extra pointer).
Each of the 7 level-1 parents has 7 children of its own. All 49 of these nodes are leaf nodes or level-2 nodes, and they are filled to capacity with key-rid pairs. There are 6 key-rid pairs in each leaf node.
3
Therefore, all 49 leaf pages contain 6 data entries each.
In other words, we have 49 leaf pages * 6 (data entries/leaf page) = 294 data entries (or keys).
Conclusion: There are 294 keys in the leaf pages. There are 1 + 7 + 49 = 57 nodes in this B+ tree. (Adding even one more key, will cause an increase in the height of the tree.)
Page 6
Q8.
a) floor( 4,096 bytes/page / 120 bytes/record ) = 34 records/page
ceiling( 89,000 records / 34 records/page ) = 2,618 data pages
b) floor( 4,096 (bytes/index page) / (4 + 4 + 15 + 10) bytes/DE ) = 124 DE/leaf page ceiling( 89,000 data entries / 124 (DE/leaf page) ) = 718 leaf pages
ceiling( 718 leaf pages / (124 + 1) (leaf pages / parent page ) ) = 6 level-1 pages ceiling( 6 level-1 pages / (124 + 1) (level-1 pages / parent page ) ) = 1 root page This means the B+ tree index has 3 levels.
Q9.
a)
i. We need 1 of the directory pages (it’s OK if you said all 4)
+ 1 bucket
+ 1 data page = 3 page I/Os
ii. We need 4 B+ tree pages (one for each level starting at the root) + 1 data page = 5 page I/Os
b)
i. We need 4 directory pages
+ 25 different buckets
+ 25 different data pages = 54 page I/Os
4
c)
Page 8
ii. We need 1 root page
+ 15 level-1 pages (i.e., all of them)
+ 25 different level-2 pages
+ 25 different level-3 pages (leaf pages) + 25 different data pages = 91 page I/Os
floor (4,096 bytes / leaf page) / ( (4 + 10) bytes/DE ) = 292 DE / leaf page
150,000 leaf pages * 292 DE/leaf page = 43,800,000 data entries
Since there is one DE per record, there are 43,800,000 records in the data table.
Q10.
Key 18 causes the split of bucket 00 (because Next = 0). Key 17 causes the split of bucket 01 (because Next = 1).
The final structure looks like this: Level = 0
000 (16, 8, 32)
001 (25,9, 1)→(17,_,_)
Next = 2
10 (6, 2,10)→(18,_,_)
11 (3,15,_)
100 (4,_,_)
101 (_,_,_)
Pages 9-10
Q11.
a) Sort Phase: Fill all of memory as many times as necessary.
Each “buffer pool fill” represents an initial sorted run (SR).
5
b) Diagram:
ceiling( 600 cylinders / 20 (cylinders / BP fill ) ) = 30 BP fills Thus, there are 30 sorted runs (SRs) coming from the sort phase. How many long seeks and short seeks did we do?
READ: Each fill takes 20 cylinders, which can be accomplished with 1 LS and 19 SS.
We have to do this 30 times (once per BP fill). Therefore, 30 BP fills = 30 LS + 570 SS.
WRITE: The same: 30 LS + 570 SS.
The total number of seeks for the Sort Phase is 60 LS + 1140 SS.
There will be 30 SRs as input; therefore, it will be a 30-way merge. Each input buffer is 0.5 cylinders in size.
This means we need 30 * 0.5 cyl = 15 cylinders, so far.
All the rest of the BP will go to the output buffer.
Therefore, the one output buffer is 20 – 15 = 5 cylinders in size.
c) Merge Phase: As mentioned, there are 30 SRs. It will be a 30-way merge.
READ:
600 cylinders / 0.5 cylinders/sorted run = 1200 input buffer fills in
data-dependent order because we don’t know which will run out first. This is 1200 long seeks (LS) and 0 short seeks (SS).
WRITE:
There are 5 cylinders of output in all.
ceiling( 600 cylinders / (5 cylinders / write operation) ) = 120 write
operations
Each write involves 5 contiguous cylinders: 1 LS followed
immediately thereafter by 4 SS.
There are 120 LS and 480 SS when writing during the Merge Phase
because 120 * (1 LS + 4 SS) = 120 LS and 480 SS.
So, for the entire Merge Phase, we have:
(1200 + 120) LS and (0 + 480 SS) = 1320 LS and 480 SS
6