UGC NET CSE | June 2011 | Part 2 | Question: 23

Question

The number of disk accesses performed by insertion operation in B-tree of height $h$ is

• A. $0(1)$
• B. $0(1gh)$
• C. $0(h)$
• D. None of these

Answer 1

Inserting a key k into a B-tree T of height h is done in a single pass down the tree, requiring O(h) disk accesses.

Algorithm:

B-TREE-INSERT(T,k)

1 r $\leftarrow$ root[T];

2 if n[r] = 2t - 1 

3 then s $\leftarrow$ ALLOCATE-NODE()

4 root[T] $\leftarrow$ s

5 leaf[s] $\leftarrow$ FALSE

6 n[s] $\leftarrow$ 0

7 c1[s] $\leftarrow$ r

8 B-TREE-SPLIT-CHILD(s,1,r)

9 B-TREE-INSERT-NONFULL(s,k)

10 else B-TREE-INSERT-NONFULL(r,k)

Reffer it : http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap19.htm

Answer 2

In B-tree block pointer, data block pointer and key are stored within a each node.

New key is always inserted at leaf level ...

So we need O(h) comparisons to reach at last level.

So O(h) is the ans.

Answer 3

Ans: C

The number of disk accesses performed by insertion operation in B-tree of height hh is O(lgn). As h=lgn so O(h)

where n is the no. of nodes