Insertion of an item into an ancestor page may cause that page to overflow, thereby causing the split to propagate.

• Insertion of an item into an ancestor page may cause that page to overflow, thereby causing the split to propagate.

• In extreme cases it may propagate up to the root

• This is the only way a B tree may increase in height

• B trees grow from the leaf nodes to the root

Previous slide

Next slide

Back to first slide

View graphic version