Tree and B-Trees

Why do we use B-Tree? if depth is still same as Binary tree 

Memory Hierarchy                   

if we use B-Tree we can utilize the whole block , instead if we use Binary tree we will have more disk io 

 

B-Tree (2-3Tree , B(branch factor)=2 )

B <= number of child <2B 

B-1 <= number of keys < 2B-1 

all the leaves are at same depth , no dangling children

2-3Tree

Search

same as binary tree O(logn)

 

Insertion

even though we find right location we might have oveflow (where key is bigger than 2B-1) situation.

Split nodes into 2 part 

1. remove the middle node 

2. insert middle node into parent node 

3. now parent might be overflow , we do this recursively until root (O(logn))

 

Deletion

now its underflow issue, number of keys need to be at most (B-1)

1. swap item to delete with inorder successor if time is not leaf 

2. redistribute and merge nodes if there is underflowing 

redistribution

1. look at sibling

1-1. if there is enough sibling's number of keys, which is at most 1 bigger than the minimum. you kinda rotate with parent key so sibling key goes to parent node and parent key goes to underflow node. 

1-2 if there is only minimum  we need to merge

reference == R2. 2-3 Trees and B-Trees - YouTube