GATE CSE 2020 | Question: 54

Question

Consider a database implemented using $\text{B+}$ tree for file indexing and installed on a disk drive with block size of $\text{4 KB}$. The size of search key is $\text{12 bytes}$ and the size of tree/disk pointer is $\text{8 bytes}$. Assume that the database has one million records. Also assume that no node of the $\text{B+}$ tree and no records are present initially in main memory. Consider that each record fits into one disk block. The minimum number of disk accesses required to retrieve any record in the database is _______

Comments

If it were a binary tree, we know the number of leafs = $10^6$

So, height would be $log_2(10^6)=19.93=20$ And accesses would be $21$

This is what I did. Which was incorrect in hindsight.

 

This is a B+ tree, it need not have two children. Number of children, at max = 205 (as calculated)

Hence, height of the tree = $log_{205}(10^6)=2.59=3$. And accesses would be $4$

---

incorrect, base of log should be 102 not 205.

again hindsight

---

why?

---

@ijnuhb , Why 102? 

There is  mistake with @JashanArora ‘s answer when we take log 205(10^6)

because this means each node has only one element in it ( But we have 204 elements in each node)

So  it should be log 205( 10^6 / 204)

( but i want to know your approach too of base 102)

---

So how the B+ tree looks like?

 

So now we will see in another way,

 I have just flipped the picture and nothing else.

Now let ‘p’ be the number of block pointers in a block. So the number of keys will be (p-1) keys in each block.

p*8+(p-1)*12 $\leq$ 4096

=> p = $\leq \left \lfloor 205.4 \right \rfloor$

=> p = 205

The number of block pointers in a block is 205 and the number of keys is 204 and the record pointers in the 1^st  is 204.

Number of records already given 1 million = 1000000 records

The number of blocks in the 1^st level will be =

(Number of records in a database/ number of record pointers) = $\left \lceil \frac{1000000}{204} \right \rceil$ = 4902

Number of blocks for 1^st level will be the number of records for 2^nd level.

The number of blocks in the 2^nd  level will be =  (number of records/ number of block pointers)  = $\left \lceil \frac{4902}{205} \right \rceil$  = 24

Number of blocks for 2^nd  level will be the number of records for 3^rd  level.

The number of blocks in the 3^rd   level will be =  (number of records/ number of block pointers)  = $\left \lceil \frac{24}{205} \right \rceil$  = 1 = root

So we can vizualize that to retrieve any record we need 3 block access as  there are 3 levels + 1 more access to actually access the record = 4 block access.

 

---

What if when its use B-tree @Anyone

---

I think its 3 access @Anyone please correct me

---

@Aman_777 An internal node of a B tree is of the following format:

How can you find the order of the B tree when size of record pointer is not even given in the question?

Answer 1

Given,

1. Search Key: $12$ bytes
2. Tree Pointer: $8$ bytes
3. Block Size: $4096$ bytes
4. Number of database records: $10^6$

Since it's a $B^+$ tree, an internal node only has search key values and tree pointers. Let $p$ be the order of an internal node. Hence,

$p(8) + (p-1)(12) \leq 4096$

which gives $p \leq 205.4$.

Therefore $p = 205$

Now, $$\small \begin{array}{c|c|c|c} \hline \text{Level} & \text{Nodes} & \text{Keys} & \text{Pointers} \\\hline  1 & 1 & 204 & 205 \\ 2 & 205 & 204 \times 205 & 205^{2} \\ 3 & 205^{2} & 204 \times 205^{2} & 205^{3} \\\hline \end{array}$$

Level $3$ alone has approximately $8.5\times10^6$ entries. So we can be sure that a $3$-level $B+$ tree is sufficient to index $10^6$ records.

So to access any record (in the worst case), we need $3$ block access to search for the record in the index along with $1$ more access to actually access the record.

Hence, $4$ accesses are required. 

Comments

" to access any record (in worst case), we need 3 block access to search for the record in the index along with 11 more access to actually access the record." -- can u please explain it more clearly ? I am not able to get it . In exam too,I marked as 3 which is incorrect. Why yet 1 more access ?

---

s_dr_13 We require three accesses to get the record pointer and finally one more access to actually get the data or record using the record pointer we have got.

---

Loved the table making approach, directly taken from Navathe. Book reference in answers are always beautiful.

Answer 2

Here, In the question size of tree pointer and disk pointer is the same. So, the order of leaf and non-leaf will be the same.

Suppose the order of non-leaf node = P. Where P= no. of tree pointer contains by a node.

So,

( P x 8 ) + ( (P-1) * 12) = 4096

8P+12P-12=4096

20P=4108

P=205.4

So P=205.

Now we will know the order of the node and that is 205.

Here, the database file contains 1 million records.

so, No. of search key at the last level should be 1 million. We require minimum no. of disk access so node of the B+ tree should be fully filled. 

 

Level	No . of Child Pointer	No. of Search Key
1	205	204
2	$205^{2}$	205 * 204
3	$205^{3}$	$205^{2}$ * 204 =8573100

So, for 1 million records total 3 level requires.

Now after getting search key in B+ tree, one extra disk access requires to access a record.

So Total 3+1=4 minimum disk access requires.

Comments

In the question size of tree pointer and disk pointer is the same. So, the order of leaf and non-leaf will be the same.

Can you share any resource supporting your statement?

Order of Internal Node(B+ tree)= P.Block_pointer_size +(P-1)(Key_size)<= Block size

Order of Leaf node(B+ tree)=p.(Key_size+Record_pointer_size)+Next_block_pointer<= Block_size

---

3 levels are sufficient to have all keys..

but dont we need one more level because it is b+ tree and in b+ tree we have a copy of all keys in last level (as we dont have record pointer in internal node so we store the copy of keys of internal node in leaf node.)thats why 4 level to store all keys + 1 to store actual record = 5 ??

---

what is tree and disk pointer here…

cant understand them as I’m familiar with block pointer and record pointer terms, so how do we know whether we have to consider leaf or non leaf of B+ tree?

---

Consider that each record fits into one disk block.

 @Abhineet Singh disk pointer here means record pointer, and block pointer is also known as node pointer or tree pointer. And when block pointer and record pointer are same then order for leaf node and Internal node is same.

Answer 3

In B+ trees there are n-1 search keys for n pointers.
so here in this question search keys is of size 12 Bytes where disk pointers is of size 8 bytes now.
 [ 8 * n ] + [12 * (n-1)] <= 4096 …….this is because block size is 4KB and in most outer block we will be having only one block which will have index overhead of inner blocks 
8n + 12n – 12 = 4096
20n = 4084
n = 204.2
so most outer block can have 205 nodes.i.e 204 search keys.

for inner one for each search key there will 205 nodes so at second level 204 * 205 = 41820 
at 3^rd level 41820 * 205 = 8573100 
now 8573100  is way bigger than 1 million so we can easily put 1 million records in 3^rd level so we need 3 block access to get the node pointer and 1 block access to retrive DATA.

so total 4 Block Access.

Comments

Hii @ProtonicRED In most outer block (leaf node) how many record pointer/data pointer it has ??

Either 205 or 204

---

as I have mentioned it will have 205 nodes per block so it will have 205 record pointers as well.