edited by
11,593 views
40 votes
40 votes

B+ Trees are considered BALANCED because.

  1. The lengths of the paths from the root to all leaf nodes are all equal.
  2. The lengths of the paths from the root to all leaf nodes differ from each other by at most $1$.
  3. The number of children of any two non-leaf sibling nodes differ by at most $1$.
  4. The number of records in any two leaf nodes differ by at most $1$.
edited by

5 Answers

Best answer
54 votes
54 votes

Option A: In $\bf{B^+}$ Tree all leaves are at same level.

In both $B$ Tree and $B^+$ trees, depth (length of root to leaf paths) of all leaf nodes is same. This is made sure by the insertion and deletion operations. In these trees, we do insertions in a way that if we have increase height of tree after insertion, we increase height from the root. This is different from BST where height increases from leaf nodes. Similarly, if we have to decrease height after deletion, we move the root one level down. This is also different from BST which shrinks from the bottom. The above ways of insertion and deletion make sure that depth of every leaf node is same.

edited by
12 votes
12 votes

According to Knuth's definition, a B-tree of order m is a tree which satisfies the following properties:

  1. Every node has at most m children.
  2. Every non-leaf node (except root) has at least ⌈m/2⌉ children.
  3. The root has at least two children if it is not a leaf node.
  4. A non-leaf node with k children contains k−1 keys.
  5. All leaves appear in the same level
4 votes
4 votes

In Computer Science , a B+ tree is a self-balancing(Height balanced) tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time 

so option A

edited by
Answer:

Related questions

56 votes
56 votes
1 answer
1
Akash Kanase asked Feb 12, 2016
11,015 views
Consider the following database table named water_schemes:$$\overset{\text{Water_schemes}}{\begin{array}{|c|c|c|}\hline\textbf{scheme_no}& \textbf{district_name}& \te...
64 votes
64 votes
6 answers
2
Akash Kanase asked Feb 12, 2016
21,840 views
Consider the following database schedule with two transactions $T_{1}$ and $T_{2}$.$S= r_{2}\left(X\right); r_{1}\left(X\right); r_{2} \left(Y\right); w_{1} \left(X\right...