The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+2 votes

(a) Suppose you are given an empty B+- tree where each node (leaf and internal) can store up to 5 key values. Suppose values 1, 2,.....10 are inserted, in order, into the tree. Show the tree pictorially

- after 6 insertions, and
- after all 10 insertions

Do NOT show intermediate stages.

(b) Suppose instead of splitting a node when it is full, we try to move a value to the left sibling. If there is no left sibling, or the left sibling is full, we split the node. Show the tree after values 1, 2,......, 9 have been inserted. Assume, as in (a) that each node can hold up to 5 keys.

(c) In general, suppose a B+- tree node can hold a maximum of $m$ keys,and you insert a long sequence of keys in increasing order. Then what approximately is the average number of keys in each leaf level node.

- in the normal case, and
- with the insertion as in (b).

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 5k
- Digital Logic 2k
- Programming & DS 3.6k
- Algorithms 3.1k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 1k
- Others 1.4k
- Admissions 412
- Exam Queries 419
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 9

34,943 questions

41,956 answers

119,194 comments

41,472 users