DBMS Notes
HubUnit 1 — Introduction to DBMS & Entity-Relationship ModelAdvantages and Disadvantages of DBMSAggregation — Database Management SystemsCharacteristics of DBMSData IndependenceData ModelsDatabase Users and AdministratorsDBMS LanguagesER DiagramsEntity-Relationship (ER) ModelIntroduction to DBMSKeys in DBMSRelationships and CardinalitySchema and InstanceSpecialization and GeneralizationDBMS Unit 1 Summary - Database FundamentalsThree-Level Architecture (ANSI/SPARC Architecture)Weak Entity SetUnit 2 — Relational Model & SQLConstraints in SQLCursorsDCL and TCL CommandsDDL CommandsDML CommandsDomain Relational Calculus (DRC) - Complete TutorialFunctions and Stored ProceduresJoins in SQLNested Queries (Subqueries)Relational AlgebraRelational Calculus in Database Management SystemsRelational ModelSQL IntroductionDBMS Unit 2 Summary - SQL and Relational ModelTriggers in SQL — Database Management SystemsTuple Relational Calculus (TRC)Views in SQL — Database Management SystemsArmstrong\Boyce-Codd Normal Form (BCNF) — Database Management SystemsClosure of AttributesDependency PreservationFifth Normal Form (5NF)First Normal Form (1NF) - Database NormalizationFourth Normal Form (4NF)Functional DependencyLossless DecompositionMultivalued DependencyNormal Forms — OverviewNormalization — IntroductionSecond Normal Form (2NF) — Database Management SystemsUnit 3 Summary — NormalizationThird Normal Form (3NF) — Database Management SystemsUnit 4 — Transaction Management & Concurrency ControlACID PropertiesCheckpointsConcurrency Control & SerializabilityDeadlock in DBMSLock-Based Protocols & Two-Phase LockingLog-Based RecoveryRecovery SystemSerializabilityShadow PagingUnit 4 Summary — Transaction Management & Concurrency ControlTimestamp-Based ProtocolTransaction ManagementTransaction StatesTwo-Phase Locking (2PL)Unit 5 — Storage & IndexingB+ TreeB-TreeCost EstimationDynamic HashingFile OrganizationHashing TechniquesIndexing — IntroductionMulti-Level IndexingQuery Optimization — Database Management SystemsQuery ProcessingSingle-Level IndexingStatic HashingUnit 5 Summary — Storage & IndexingUnit 6 — Advanced Topics in DBMSBig Data and DBMSCloud DatabaseData MiningData WarehouseDatabase SecurityDistributed DatabaseDistributed Query ProcessingDistributed DBMS Architecture, Fragmentation & ReplicationMongoDB — IntroductionNoSQL DatabaseReplication in Distributed DatabasesUnit 6 Summary — Advanced Topics in DBMSViva Voce — DBMSImportant Viva Questions — DBMSInterview Questions — DBMSViva Answers — DBMSDBMS Multiple Choice Questions (MCQs)DBMS Lab Programs
A B-Tree (Balanced Tree) is a self-balancing, sorted tree data structure that maintains sorted data and allows searches, insertions, and deletions in O(log...
What is a B-Tree?
A B-Tree (Balanced Tree) is a self-balancing, sorted tree data structure that maintains sorted data and allows searches, insertions, and deletions in O(log n) time. It is designed for efficient disk-based storage where reading a full node (disk block) at a time is optimal.
Proposed by Rudolf Bayer and Edward McCreight in 1970.
B-Tree Node Structure
A node in a B-Tree of order m:
┌──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│ P₀ │ K₁ │ P₁ │ K₂ │ P₂ │ ... │ Pₖ │
└──────┴──────┴──────┴──────┴──────┴──────┴──────┘
Pᵢ = pointer to child subtree (or data record for leaf)
Kᵢ = key value (K₁ < K₂ < ... < Kₖ)
Keys in subtree of P₀ < K₁
K₁ < Keys in subtree of P₁ < K₂
...
Kₖ < Keys in subtree of Pₖ
Example — B-Tree of Order 3
Example
B-Tree (order 3, max 2 keys per node, max 3 children):
[30 | 70]
/ | \
[10|20] [40|60] [80|90]
/ | \ / | \ / | \
[5] [15] [25] [35] [50] [65] [75] [85] [95]
- Root: [30|70] has 2 keys, 3 children ✓
- Every leaf at same level ✓
- Each node has ≤ 3 children, ≥ ⌈3/2⌉ = 2 children ✓
- DATA stored in every node (including internal nodes)
Search in B-Tree
| 2. If K = Kᵢ | FOUND, return associated data |
| 3. If K < Kᵢ | recurse into child Pᵢ₋₁ |
| 4. If K > all keys | recurse into rightmost child |
| 5. If N is a leaf and K not found | NOT FOUND |
| Example | Search for 50 in tree above |
| Step 1: Root [30|70] | 50 > 30, 50 < 70 → go to middle child [40|60] |
| Step 2: [40|60] | 50 > 40, 50 < 60 → go to middle child [50] |
| Step 3: [50] | found! ✓ |
| Cost | 3 node reads = 3 disk I/Os |
Insertion in B-Tree
| 2. If leaf has space (< m−1 keys) | insert K there |
| Example | Insert 45 into order-3 B-Tree |
| Find position | goes into node [40|60] |
| [40|60] is full | split! |
| Median = 50 | promote 50 to parent |
| Left | [40], Right: [60] |
Deletion in B-Tree
Example
Delete key K:
Case 1: K is in a LEAF node
→ Remove K directly
→ If node now has < ⌈m/2⌉−1 keys → UNDERFLOW
→ Try borrowing from sibling (rotation)
→ If cannot borrow → MERGE with sibling
(pull down a key from parent into merged node)
→ Parent may underflow → repeat upward
Case 2: K is in an INTERNAL node
→ Replace K with its in-order predecessor or successor
(which is in a leaf node)
→ Delete that leaf entry (apply leaf deletion logic)
B-Tree Height and Performance
| Minimum height | h_min = ⌈log_m(n+1)⌉ |
| Maximum height | h_max = ⌊log_⌈m/2⌉((n+1)/2)⌋ + 1 |
| Operations | O(log_m(n)) = O(log n / log m) |
B-Tree vs B+ Tree Preview
| Feature | B-Tree | B+ Tree |
|---|---|---|
| Data storage | All nodes (internal + leaf) | Only leaf nodes |
| Internal nodes | Keys + data pointers | Keys only (routing) |
| Leaf nodes | Linked? No | Linked as list ✓ |
| Range queries | Less efficient | Very efficient |
| Space usage per node | Less keys (data takes space) | More keys (routing only) |
| Most used in DBMS | No | Yes (almost universally) |
The key limitation of B-Trees is that data stored in internal nodes reduces the fan-out (number of children per node), making the tree taller. B+ Trees solve this.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for B-Tree.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Database Management Systems (DBMS) topic.
Search Terms
dbms, database management systems (dbms), unit, tree, b-tree
Related Database Management Systems (DBMS) Topics
Continue learning this concept
Unit 5B+ TreeA B+ Tree is a variation of the B-Tree where: - All data records (or pointers to them) are stored only in leaf nodes - Internal nodes store only keys used...Unit 5Unit 5 — Storage & IndexingThis unit addresses one of the most critical aspects of database management — how data is physically stored on disk and how it can be retrieved efficiently. While SQL andUnit 5Cost EstimationCost estimation is the process of predicting the execution cost of a query plan without actually running it. The query optimizer uses cost estimates to...Unit 5Dynamic HashingStatic hashing suffers when data size changes unpredictably: - Too few buckets → overflow chains → slow - Too many buckets → wasted spaceUnit 5File OrganizationFile organization refers to how data records are physically arranged and stored on disk. The choice of file organization directly impacts the performance of...Unit 5Hashing TechniquesHashing is a data access technique that uses a mathematical function (called a hash function) to compute the storage address of a record directly from its...