B+ Tree Database Indexing Lab

Interactive deep-dive into Root, Branch, Leaf page structures, and Heap tuple pointers.

Database Physical Storage Engine

Step 1 of 4 • $O(\log N)$ Point Lookup

Search Target ID:

Root Page #1 (Disk Block: 0x01)8 KB Page

ptr_0 (< 30)[ Key: 30 ]ptr_1 (30 - 70)[ Key: 70 ]ptr_2 (> 70)

Branch Page #3 (Disk Block: 0x03)Internal Routing Page

ptr_0 (30 - 40)[ Key: 40 ]ptr_1 (40 - 60)[ Key: 60 ]ptr_2 (60 - 70)

Leaf Page #8 (Doubly-Linked with Page #7 and #9)Record Pointers

[ id: 41 ➔ Blk 11:1 ]⇄[ id: 45 ➔ Blk 12:4 ]⇄[ id: 52 ➔ Blk 14:2 ]

Step Narration:

45 > 30 and 45 <= 70. Follow pointer between 30 and 70 to Branch Page #3.