file organization indexing and b trees notes

B+ Tree Insertion, Splitting and Occupancy

Databases › File Organization, Indexing and B+ Trees B+ Tree Mechanics Mastering insertion, splitting, and balance. What you will learn here 1 The step-by-step algorithm for inserting keys into leaf and internal nodes. 2 How node splitting works and how the middle key propagates upward. 3 Occupancy constraints: why nodes must be at least half full.

B+ Tree Structure and Order

B+ Tree Structure and Order 1. The Order (m) Defines node capacity. A node has at most m child pointers and m - 1 keys. Note: Verify if the problem specifies "max keys" or "max pointers". 2. Balanced Property All leaf nodes are at the same depth. This guarantees consistent O (lo g n) search time for any key. 3. Leaf vs Internal Nodes Internal Nodes: Contain keys and child pointers. Act as an index. Leaf Nodes: Contain keys and data pointers . Linked for range queries. Key Insight: Because internal nodes do not store data pointers, they can hold more keys per block, reducing the tree height.

Insertion Algorithm: Leaf Node Overflow

Insertion: Leaf Node Overflow 1 Find Leaf Traverse the tree to find the appropriate leaf node L . 2 Check Space If L has < m - 1 keys, insert in sorted order. If full (m - 1 keys), Overflow . 3 Split Leaf Temporarily include new key in L (now m keys). Sort all m keys. Left Node First ⌊ m /2 ⌋ keys Right Node Remaining ⌈ m /2 ⌉ keys Separator: Smallest key of Right Node is copied to parent. Crucial Rule: In B+ Trees, the separator key is copied to the parent, not moved. It remains in the leaf. @keyframes splitLeft { 0% { transform: translateX(0); } 100% { transform: translateX(-20px); } } @keyframes splitRight { 0% { transform: translateX(0); } 100% { transform: translateX(20px); } } @keyframes floatUp { 0% { transform: translateX(-50%) translateY(0); opacity: 0; } 50% { opacity: 1; } 100% { transform: translateX(-50%) translateY(-30px); opacity: 1; } } .anim-leaf-left { animation: splitLeft 2s ease-in-out infinite alternate; } .anim-leaf-right { animation: splitRight 2s ease-in-out infinite alternate; } .anim-float-key { animation: floatUp 2s ease-in-out infinite; } Visualizing Leaf Split [10] [15, 20] 15

24 more cards in this chapter

File Organization, Indexing and B+ Trees Notes for GATE CS

File Organization, Indexing and B+ Trees notes for GATE CS: 27 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

B+ Tree Insertion, Splitting and Occupancy

Databases › File Organization, Indexing and B+ Trees

B+ Tree Mechanics

Mastering insertion, splitting, and balance.

What you will learn here

The step-by-step algorithm for inserting keys into leaf and internal nodes.

How node splitting works and how the middle key propagates upward.

Occupancy constraints: why nodes must be at least half full.

B+ Tree Structure and Order

1. The Order ( $m$ )

Defines node capacity. A node has at most $m$ child pointers and $m - 1$ keys. Note: Verify if the problem specifies "max keys" or "max pointers".

2. Balanced Property

All leaf nodes are at the same depth. This guarantees consistent $O (lo g n)$ search time for any key.

3. Leaf vs Internal Nodes

Internal Nodes: Contain keys and child pointers. Act as an index.

Leaf Nodes: Contain keys and data pointers. Linked for range queries.

Key Insight: Because internal nodes do not store data pointers, they can hold more keys per block, reducing the tree height.

Insertion Algorithm: Leaf Node Overflow

Insertion: Leaf Node Overflow

Find Leaf

Traverse the tree to find the appropriate leaf node $L$ .

Check Space

If $L$ has $< m - 1$ keys, insert in sorted order. If full ( $m - 1$ keys), Overflow.

Split Leaf

Temporarily include new key in $L$ (now $m$ keys). Sort all $m$ keys.

Left Node

First

⌊ m /2 ⌋

keys

Right Node

Remaining

⌈ m /2 ⌉

keys

Separator: Smallest key of Right Node is copied to parent.

Crucial Rule: In B+ Trees, the separator key is copied to the parent, not moved. It remains in the leaf.

Visualizing Leaf Split

[10]

[15, 20]

Worked Example: Leaf Split

Given

Order:

m = 3

(Max 2 keys)

Leaf $L$ :

[10, 20]

Insert:

15

Process

Overflow:

L

is full. Add 15 temporarily:

[10, 15, 20]

Split: Left gets

⌊ 3/2 ⌋ = 1

key

\to [10]

. Right gets

2

keys

\to [15, 20]

Update Parent: Copy

15

to parent.

Result

Parent: $[15]$

Left Leaf: $[10]$

Right Leaf: $[15, 20]$