DBMS Topics
HubUnit 1 — Introduction to DBMS & Entity-Relationship ModelAdvantages and Disadvantages of DBMSAggregationCharacteristics of DBMSData IndependenceData ModelsDatabase Users and AdministratorsDBMS LanguagesER DiagramsEntity-Relationship ER ModelIntroduction to DBMSKeys in DBMSRelationships and CardinalitySchema and InstanceSpecialization and GeneralizationUnit 1 Summary — Introduction to DBMS & ER ModelThree-Level Architecture ANSI/SPARC ArchitectureWeak Entity SetUnit 2 — Relational Model & SQLConstraints in SQLCursorsDCL and TCL CommandsDDL CommandsDML CommandsDomain Relational Calculus DRCFunctions and Stored ProceduresJoins in SQLNested Queries SubqueriesRelational AlgebraRelational CalculusRelational ModelSQL IntroductionUnit 2 Summary — Relational Model & SQLTriggers in SQLTuple Relational Calculus TRCViews in SQLArmstrong's Axioms & Closure of AttributesBoyce-Codd Normal Form BCNFClosure of AttributesDependency PreservationFifth Normal Form 5NFFirst Normal Form 1NFFourth Normal Form 4NFFunctional DependencyLossless DecompositionMultivalued DependencyNormal Forms — OverviewNormalization — IntroductionSecond Normal Form 2NFUnit 3 Summary — NormalizationThird Normal Form 3NFUnit 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 2PLUnit 5 — Storage & IndexingB+ TreeB-TreeCost EstimationDynamic HashingFile OrganizationHashing TechniquesIndexing — IntroductionMulti-Level IndexingQuery OptimizationQuery 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 MCQsDBMS Lab Programs
B-Tree
Last Updated : 21 May, 2026
A B-Tree Balanced Tree is a self-balancing, sorted tree data structure that maintains sorted data and allows searches, insertions, and deletions in Olog n time. It is des
Unit 5276 words9 headingsTables includedExamples included
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 Properties (Order m)
A B-Tree of order m (also called degree m or maximum degree m) satisfies:
- Every node has at most m children
- Every non-root internal node has at least ⌈m/2⌉ children
- The root has at least 2 children (if it is not a leaf)
- All leaf nodes are at the same level (tree is balanced)
- A node with k children contains k−1 keys
- Data records (or pointers) are stored in ALL nodes (both internal and leaf)
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
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
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 DBMS topic.
Search Terms
dbms, database management system, database notes, sql, unit, tree, b-tree
Related DBMS Topics
Continue learning this concept
Unit 5B+ TreeA B+ Tree is a variation of the B-Tree where:Unit 5Unit 5 — Storage & IndexingThis unit covers how databases physically store and efficiently retrieve data. Understanding storage structures and indexing is essential for database performance tuning Unit 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 compare alternativUnit 5Dynamic HashingStatic hashing suffers when data size changes unpredictably:Unit 5File OrganizationFile organization refers to how data records are physically stored on disk. The choice of file organization affects the speed of data retrieval, insertion, deletion, and Unit 5Hashing TechniquesHashing is a technique for direct address computation — a hash function maps a key value directly to a bucket address disk block where the record is stored. It avoids the