Stage 1 · Code
Advanced Data Structures
B-Tree
Multi-way tree for disk-based storage and databases.
8 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
B-Tree Concept
B-Tree is a self-balancing multi-way search tree optimized for disk storage. Each node can have many children (order m). Minimizes disk I/O by maximizing branching factor. Used in databases (MySQL, PostgreSQL) and filesystems.
B-Tree Properties (order m)
- Each node has at most m children.
- Each internal node (except root) has at least ⌈m/2⌉ children.
- Root has at least 2 children (if not leaf).
- All leaves at same level (perfectly balanced).
- Node with k children has k-1 keys.
- Keys in node sorted: key₁ < key₂ < ... < keyₖ₋₁.
Operations
Gob-tree-node-structure.go
34 linesLn 1, Col 1Go
Node stores keys array and children array. n = current number of keys. t = minimum degree. Max keys = 2t-1, max children = 2t. Min keys (non-root) = t-1.
Split: when node has 2t keys, split at median. Median moves up to parent. Two new nodes with t-1 keys each. Recursively split up if parent full. Insert: always insert into leaf. If leaf full, split first, then descend.
Gob-tree-split-child.go
38 linesLn 1, Col 1Go
y is full child at index i. Create z. Move last t-1 keys of y to z. If not leaf, move last t children. Median key (index t-1) moves up to x. Update counts and arrays.
Variants
| Variant | Description | Use Case |
|---|---|---|
| B+ Tree | All data in leaves, internal nodes only keys | Databases (range queries, sequential access) |
| B* Tree | Non-root nodes at least 2/3 full | Better space utilization |
| B-Tree with prefix compression | Compress common prefixes in keys | String keys |
| LSM Tree | Log-structured merge tree | Write-heavy workloads (Cassandra, RocksDB) |
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.