Page 190 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 8: B-trees

B-trees: B-trees are balanced trees that are optimized for situations when part or the entire tree Notes
must be maintained in secondary storage such as a magnetic disk.

8.11 Self Assessment

Choose the appropriate answers:
1. A b-tree has a minimum number of allowable children for each node known as the ............
..............................................
(a) Minimization factor
(b) Maximization factor
(c) Operational factor

(d) Situational factor
2. Binary tree is a special type of tree having degree.
(a) 3
(b) 1
(c) 2

(d) 4
Fill in the blanks:
3. The search operation on a b-tree is ................................. to a search on a binary tree.
4. A ................................. is a collection of data organized in a fashion that facilitates updating,
retrieving, and managing the data.
5. A B-tree is kept balanced by requiring that all leaf nodes are at the same ............................
6. The .............................. operation creates an empty b-tree by allocating a new root node that
has no keys and is a leaf node.

State whether the following statements are True or False:
7. Deletion of a key from a b-tree is possible.
8. B-trees do not shrink when keys are deleted.
9. The lower and upper bounds on the number of child nodes are typically fixed for a

particular implementation.
10. To perform an insertion on a b-tree, the appropriate node for the key must be located using
an algorithm similiar to B-Tree-Search.

8.12 Review Questions

1. Generalize the amortized analysis given in the text for incrementing four-digit binary
integers to n-digit binary integers.
2. Describe the deletion of an item from b-trees.

3. Describe of structure of B-tree. Also explain the operation of B-tree.
4. Explain how will you insert an item in b-trees.

LOVELY PROFESSIONAL UNIVERSITY 185