edited by
7,580 views
34 votes
34 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$
edited by

2 Answers

Best answer
49 votes
49 votes
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
3 votes
3 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

38 votes
38 votes
3 answers
1
Ishrat Jahan asked Nov 2, 2014
10,851 views
Consider two tables in a relational database with columns and rows as follows:$$\overset{\text{Table: Student}}{\begin{array}{|c|c|c|} \hline \textbf {Roll_no} & \textbf{...
43 votes
43 votes
6 answers
2
Ishrat Jahan asked Nov 2, 2014
12,131 views
Consider the following schedule $S$ of transactions $T1$ and $T2:$$${\begin{array}{l|l}\textbf{T1}& \textbf{T2} \\\hline\text{Read(A)} \\\text{A = A – 10}\\& \text...
43 votes
43 votes
5 answers
3
Ishrat Jahan asked Nov 2, 2014
10,532 views
A table T1 in a relational database has the following rows and columns: $$\begin{array}{|c|c|c|} \hline \text {Roll no. } & \text {Marks} \\\hline 1& 10 \\\hline 2 & 20 ...
58 votes
58 votes
6 answers
4
Ishrat Jahan asked Nov 2, 2014
17,454 views
A relation $\text{Empdtl}$ is defined with attributes empcode (unique), name, street, city, state and pincode. For any pincode, there is only one city and state. Also, fo...