in Databases edited by
5,956 views
28 votes
28 votes

Consider a table $T$ in a relational database with a key field $K$. A $B$-tree of order $p$ is used as an access structure on $K$, where $p$ denotes the maximum number of tree pointers in a B-tree index node. Assume that $K$ is $10$ $bytes$ long; disk block size is $512$ $bytes$; each data pointer PD is $8$ bytes long and each block pointer PB is $5$ bytes long. In order for each $B$-tree node to fit in a single disk block, the maximum value of $p$ is

  1. $20$
  2. $22$
  3. $23$
  4. $32$
in Databases edited by
6.0k views

2 Comments

for finding the order in B+ tree and B tree is both the formulas are different or same ??
0
0
different
1
1

2 Answers

43 votes
43 votes
Best answer
It is $\bf{23}.$

$(p-1)(\text{key_ptr_size} + \text{record_ptr_size}) + p. (\text{block_ptr_size}) \leq 512$
$\implies (p-1) (10+ 8) + p \times 5 \leq 512$
$\implies 23p \leq 530$
$\implies p \leq 23.04$

So, maximum value of $p$ possible will be $23.$
edited by

4 Comments

I think your answer is right but we need to do p=23-1=22 bytes as 1 byte will be used to store information.. that is as per NAVATHE book...
0
0
i am not understanding why record pointer is considered in internal nodes?
0
0
Got it... In B tree records are also present in internal nodes. Silly confusion :)
2
2
2 votes
2 votes

(n-1)(key pointer size + record pointer size) + n. (block pointer size) <= 512

=> (n-1) (10+8) + n (5) <= 512 

=> n = 23

Answer:

Related questions