retagged by
1,658 views

3 Answers

Best answer
3 votes
3 votes

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 $\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

selected by
1 votes
1 votes
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.
0 votes
0 votes

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

Related questions

1 votes
1 votes
2 answers
1
2 votes
2 votes
1 answer
2
1 votes
1 votes
1 answer
3
makhdoom ghaya asked Aug 30, 2016
975 views
A file organization component VSAM file isRelative records data setKeyed sequential data setEntry sequential data setAll of the above
0 votes
0 votes
1 answer
4
makhdoom ghaya asked Aug 30, 2016
811 views
Block or Buffer caches are used toImprove disk performanceHandle interruptsIncrease the capacity of main memorySpeed up main memory Read operations