Skip to content

B-Tree Hot Sheet

Use this page when the real lesson is one high-fanout multiway ordered dictionary, not one contest-first binary search-tree route.

Do Not Use When

Choose By Signal

  • high-fanout node splitting and textbook external-memory flavor -> B-Tree
  • one dynamic ordered set with rank / k-th -> PBDS
  • self-hosted split/merge route -> Treap
  • binary balanced-tree compare exercise -> Balanced BST compare note

Core Invariants

  • keys inside each node stay sorted
  • all leaves stay at the same depth
  • every non-root node respects the min/max key-capacity bounds
  • insert only descends into non-full children
  • splitting promotes one median key upward

Main Traps

  • treating B-trees like binary trees with rotations
  • descending into a full child during insert
  • using this in contest code just because it sounds stronger than PBDS
  • forgetting that deletion is intentionally out of the first route

Exact Starter Route

Reopen Paths