Test: B - Tree - Computer Science Engineering (CSE) MCQ

The average probability of the split is 1/([m / 2] – 1), where m is the order of B-tree. So, if m larger, the probability of split will be less.

B-tree of order n and with height k has best case height h, where h = logn (k+1) – 1. The best case occurs when all the nodes are completely filled with keys.

2-3-4 trees are isometric of Red-Black trees. It means that, for every 2-3-4 tree, there exists a Red-Black tree with data elements in the same order.

If s splits occur in a B-tree, 2s + 1 nodes are written (2 halves of each split and the parent of the last node split). So, if 5 splits occurred, then 2 * 5 + 1, i.e. 11 nodes are written.

A B-tree of order m of height h will have the maximum number of keys when all nodes are completely filled. So, the B-tree will have n = (m^h+1 – 1) keys in this situation. So, required number of maximum keys = 4³⁺¹ – 1 = 256 – 1 = 255.

In external memory, the data is transferred in form of blocks. These blocks have data valued and pointers. And B-tree can hold both the data values and pointers. So B-tree is used as an external memory data structure.

A non-root node in a B-tree of order n contains at least (n – 1)/2 keys. And contains a maximum of (n – 1) keys and n sons.

At every level, one new node is created except root, at two new nodes is created.
Tips and Tricks:
If database table has h levels and level of root node is 0 then on a new key insertion, maximum number of nodes newly created is h + 2
New nodes = 7 + 2 = 9
If database table has h levels and level of root node is 1 then on a new key insertion, maximum number of nodes newly created is h + 1

CONCEPT:
B-tree is a self-balancing search tree that allows all operations i.e. searching, insertion, deletion in logarithmic(log) time.
Key Points
A B-tree of order m must satisfy the following properties:

• Every node can have maximum m children.
• Every internal node (except root) can have at least [m/2] child nodes.
• The root, if not a leaf node, can have at least two children.
• An internal node with k children contains k − 1 key.
• All leaf nodes must be at the same level.

Hence, if a node has K children in B tree, then the node contains exactly k-1 keys.

Concept:
Considering all nodes are completely full means every node has N − 1 key.
If a new key is inserted, then at every level there will be a new node created, and in the worst-case root node will also be broken into two parts. Since we have 4 levels, then 5 new nodes will be created
Additional Information:
Diagram needs to be updated
First, the overflow happens at the leaf, and second on the parent of that leaf, and so on until the last overflow happens at the root node.

Key Points
If the database table has h levels and the level of the root node is 1 then on a new key insertion, the maximum number of nodes newly created is h + 1