[go: up one dir, main page]
Scribd
Upload
43 views4 pages

Tutorial 5

The document contains 5 exercises related to database concepts: 1) Calculates block factor of 39 records per block for a file with 4096 byte blocks and 100 byte records. 2) Determines the number of dense (200 blocks) and sparse (20 blocks) index blocks for a database with 10000 records, 1000 byte blocks, and 50 entries per index block. 3) Constructs B+-trees for a set of numbers allowing 4, 6, and 8 pointers per node. 4) Shows the changes to the B+-tree from exercise 3a after inserting and deleting numbers.

Uploaded by

Gurmehak kaur
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
43 views4 pages

Tutorial 5

The document contains 5 exercises related to database concepts: 1) Calculates block factor of 39 records per block for a file with 4096 byte blocks and 100 byte records. 2) Determines the number of dense (200 blocks) and sparse (20 blocks) index blocks for a database with 10000 records, 1000 byte blocks, and 50 entries per index block. 3) Constructs B+-trees for a set of numbers allowing 4, 6, and 8 pointers per node. 4) Shows the changes to the B+-tree from exercise 3a after inserting and deleting numbers.

Uploaded by

Gurmehak kaur
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Exercise 1: ​Consider the database with the below parameters:

block size is 4096 bytes


header size is 100 bytes
record size is 100 bytes
Consider a file storing variable length records. What is the block factor?

Answer. ​Block factor (number of records per block) can be calculated as


BF = (Block Size - Header Size) / Record Size = (4096-100)/100 = 39 records per block

Exercise 2: ​Consider the database with the below parameters:


Block Size = 1000 bytes
Record Size = 100 bytes
Key Size = 12 Bytes
Pointer Size = 8 bytes
Given 10000 records, determine the number of dense and sparse index blocks?

Answer. ​Database file block factor = Block size/ record size = 1000/100 = 10 records per block
Index file block factor = block size / (key+pointer) size = 1000/(12+8) = 50 entries per block

To find out dense index blocks:


No. of entries = No. of records = 10000
No. of dense index blocks = No. of entries / Index file block factor = 10000/50 = 200 blocks

To find out sparse index blocks:


No. of entries = No. of database blocks
No. of database blocks = No. of records/ database file block factor = 10000/10 = 1000 blocks
No. of blocks = 1000/50 = 20 blocks

Exercise 3: ​Construct a B+-tree for the following set of key values:


(2, 3, 5, 7, 11, 17, 19, 23, 29, 31)
Assume that the tree is initially empty and values are added in ascending order. Construct
B+-trees for the cases where the number of pointers that will fit in one node is as follows:
a. Four
b. Six
c. Eight
Answer 3(a): ​The following were generated by inserting values into the B+- tree in ascending
order. A node (other than the root) was never allowed to have fewer than ⌈n/2⌉ values/pointers.

3(b)

3(c)

Exercise 4: ​For the B+ tree of exercise 3(a), show the form of the tree after the following series
of operations:
a. Insert 9.
b. Insert 10.
c. Insert 8.
d. Delete 23.
e. Delete 19.
Answer.
Insert 8

You might also like