DBMS Indexing questions & some DS question
Varun Shinde
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 D 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:
(A) 20 (B) 22 (C) 23 (D)32
2. If Nested loop join algorithm is employed to perform the join,
with the
most
appropriate choice of table to be used in outer loop, the number of
block
accesses required for reading the data are:
(A) 800000 (B) 40080 (C) 32020 (D) 100
3. If, instead of Nested loop join, Block nested loop join is used,
again
with the most appropriate choice of table in the outer loop, the
reduction
in number of block accesses required for reading the data will be:
(A) 0 (B) 30400 (C) 38400 (D)798400
4. In a database file structure the search key field is 9 bytes long,
the
block size is 512 bytes record pointer is 7 bytes and the block
pointer is 6
bytes. The largest possible order of non-leaf node in a B+ tree
implementing
this file structure is:
a) 23 b) 24 c) 34 d) 44
5. what is the total number of key values in the internal nodes of B+
tree
with 1 leaves.
6. what is the maximum nuber of internal nodes in a b+ tree of order 4
with
52 leaves.
7. what is the minimum nuber of leaves of order d and height h(n>=1)
**
Thanks.
**
plz answer these question...........
Varun Shinde
Mayur Mahrotri
Because, the maximum number of internal nodes would occur when every node has minimum number of keys i.e. n/2 = 2 = number of children in the internal node.
There are 52 leaves, meaning 26 internal nodes at the (n-1)st level.
13 nodes at (n-2)nd level.
6 nodes at (n-3)rd level.
3 nodes at (n-4)th level.
1 node at (n-5)th level.
Thus, total internal nodes will be 26+13+6+3+1 = 49.
1st and 4th question, you will easily get after studying about the structure of the internal nodes in a B+ tree. It is given in the material given by Vani Institute. Refer that. One more good source of that is G.K. Publishers (surprisingly :) ). The node structure is explained.
7th would be some formula. I tried google but no luck. :(
2nd and 3rd question is something i am not sure is in our course. That is a part of Database optimization. But, if its there, I am not sure, you should read it at this point of time. :)
May be if someone else has done the nested loop thing, can explain.
With Regards,
Mayur.
Varun Shinde
Thanks a lot for replying....
On Feb 10, 8:35 pm, Mayur Mahrotri <mayurmahro...@gmail.com> wrote:
> I think the answer to the 6th question would be 49.
>
> Because, the maximum number of internal nodes would occur when every node
> has minimum number of keys i.e. n/2 = 2 = number of children in the internal
> node.
>
> There are 52 leaves, meaning 26 internal nodes at the (n-1)st level.
> 13 nodes at (n-2)nd level.
> 6 nodes at (n-3)rd level.
> 3 nodes at (n-4)th level.
> 1 node at (n-5)th level.
>
> Thus, total internal nodes will be 26+13+6+3+1 = 49.
>
> 1st and 4th question, you will easily get after studying about the structure
> of the internal nodes in a B+ tree. It is given in the material given by
> Vani Institute. Refer that. One more good source of that is G.K. Publishers
> (surprisingly :) ). The node structure is explained.
>
> 7th would be some formula. I tried google but no luck. :(
>
> 2nd and 3rd question is something i am not sure is in our course. That is a
> part of Database optimization. But, if its there, I am not sure, you should
> read it at this point of time. :)
>
> May be if someone else has done the nested loop thing, can explain.
>
harshjpathak
2nd and 3rd question were asked in GATE IT paper. The theory is given in korth book chapter 13 , join operation. If you read it everything will be clear.