Siksha Sarovar

Siksha Sarovar (sikshasarovar.com) is a free educational web application that helps students in India learn programming and prepare for academic and competitive exams. The platform offers structured coding courses (C, C++, Python, Java, HTML, CSS, PHP, Power BI, AI, Machine Learning, Data Science), complete university curriculum notes for BCA/MCA students with previous year question papers, Class 10 and Class 12 CBSE/HBSE school notes, and dedicated preparation material for SSC, UPSC, Banking, Railway and other government exams. Browsing the site is completely free and requires no account. Users may optionally sign in with Google solely to save their learning progress, quiz scores and personal preferences across devices.

Privacy Policy | Terms of Service | Contact Siksha Sarovar | About Siksha Sarovar

v4.0.9 · PWA
Siksha Sarovar logo
Siksha Sarovar
Your Learning Universe

Siksha Sarovar is a free e-learning platform for coding courses, BCA university notes and competitive exam preparation. Optional Google sign-in saves your learning progress across devices.

Initializing knowledge base…
Compiling modules 0%

Unit 3: Example Creating a B-Tree

Lesson 11 of 14 in the free Data Structure notes on Siksha Sarovar, written by Rohit Jangra.

Step-by-Step B-Tree Creation

Let's build a B-Tree of Order 3.

  • Max Keys per Node: 2 (M-1)
  • Max Children per Node: 3 (M)
  • Overflow: Occurs at 3rd key. Action: Split & Promote Median.

Insert Sequence: 10, 20, 5, 6, 12, 30

StepInsertActionTree Structure
110Root = [10][10]
220Add to root[10, 20] (full)
35Overflow! Split. 10 promoted[10] with children [5], [20]
466 < 10, go left[5, 6] as left child
51212 > 10, go right[12, 20] as right child
630Overflow in right! 20 promotedRoot: [10, 20], children: [5,6], [12], [30]

Final Structure:

       [10, 20]
      /    |    \
   [5,6] [12]  [30]

B-Tree Deletion

Deletion is more complex than insertion. There are several cases:

CaseConditionAction
Case 1Key is in a leaf with enough keysSimply remove it
Case 2Key is in an internal nodeReplace with predecessor/successor, delete from leaf
Case 3Leaf has minimum keys (underflow)Borrow from sibling or merge nodes

Underflow Resolution:

  • Borrow from Sibling: If an adjacent sibling has more than minimum keys, rotate a key through the parent.
  • Merge: If no sibling can lend, merge with a sibling and pull down the parent key.

B+ Trees — The Database Favorite

FeatureB-TreeB+ Tree
Data storageIn ALL nodes (internal + leaf)Only in leaf nodes
Internal nodesStore keys + data + pointersStore keys + pointers only
Leaf nodesNo special linkingLinked together (linked list)
Range queriesMust traverse up and downSimply scan leaf linked list
Branching factorLower (data takes space)Higher (internal nodes are smaller)
DuplicatesKeys appear onceKeys may appear in internal + leaf
Used byFile systemsDatabases (MySQL InnoDB, PostgreSQL)
Why B+ Trees for databases? Range queries (e.g., "find all students with GPA > 3.5") are extremely efficient because leaf nodes are linked sequentially.

Choosing B-Tree Order

FactorRecommendation
Disk block sizeChoose M so one node fits in one disk block
Key sizeLarger keys → smaller M
Typical orders50–200 for databases
Rule of thumbM = (Block Size) / (Key Size + Pointer Size)