Stage 10

For example, consider the relation Student having 5 attributes (Roll No, Name, Marks, Grade, Attendance). As an administrator, we might have to frequently get the subset of students having Marks greater than some amount M. Instead of going through each and every record and checking if it satisfies our condition, the index allows us to easily reach the first record with Marks > M.

Internal nodes have size 100 and leaf odes have size 63, each of these nodes are stored in a separate disk block.

Sorted Order in Leaf Nodes: In a B+ tree, all the leaf nodes are linked together in sorted order. This means that once we locate the first leaf node where Marks>M\text{Marks} > MMarks>M, all subsequent leaf nodes (to the right) will contain records with equal or greater marks.

B+ Tree Structure

• Internal Nodes: Store keys to guide searches but do not contain actual data.
• Leaf Nodes: Contain all data records and are linked together in a sorted manner.

A pointer here refers to the block number of the corresponding to their respective children.