I used to think of a database as a simple bucket: you dump data in, and you pull it out with SQL.
But I’ve been digging into Database Anatomy lately, and my mind is officially blown. There is a massive "engine" under the hood making split-second decisions for every query.
Here are my 3 biggest "Aha!" moments from this week’s deep dive:
1. The Consistency Tug-of-War (ACID vs. BASE) ⚖️
It’s all about trade-offs. You can’t have everything at once.
- ACID is like a Bank: It’s obsessed with being 100% correct. Every cent must be accounted for, even if the transaction takes an extra millisecond.
- BASE is like a Social Media Feed: It’s okay if a post takes a second to show up for your followers, as long as the app stays fast and never crashes.
2. B-Trees vs. LSM-Trees (Read vs. Write) 🌳
How data is physically written to a disk changes everything about performance.
- B-Trees are the kings of Reads. If you need to find a specific user profile instantly, B-Trees are your best friend.
- LSM-Trees are built for Writes. If you’re ingesting millions of sensor logs per second, LSM-Trees win because they append data sequentially rather than hunting for a spot on the disk.
The Code: B-Tree (The Read Specialist)
package com.bt;
import java.util.ArrayList;
import java.util.List;
public class BTree<K extends Comparable<K>, V> {
private final int T;
private Node root;
private class Node {
List<K> keys = new ArrayList<>();
List<V> values = new ArrayList<>();
List<Node> children = new ArrayList<>();
boolean isLeaf = true;
int findKey(K key) {
for (int i = 0; i < keys.size(); i++) {
if (keys.get(i).compareTo(key) >= 0) return i;
}
return keys.size();
}
}
public BTree(int t) {
this.T = t;
this.root = new Node();
}
public V get(K key) { return search(root, key); }
private V search(Node node, K key) {
int i = node.findKey(key);
if (i < node.keys.size() && node.keys.get(i).compareTo(key) == 0) return node.values.get(i);
return node.isLeaf ? null : search(node.children.get(i), key);
}
// Update is just a Put that replaces the value if key exists
public void put(K key, V value) {
if (root.keys.size() == 2 * T - 1) {
Node s = new Node();
s.isLeaf = false;
s.children.add(root);
splitChild(s, 0, root);
root = s;
}
insertNonFull(root, key, value);
}
private void insertNonFull(Node node, K key, V value) {
int i = node.findKey(key);
if (i < node.keys.size() && node.keys.get(i).compareTo(key) == 0) {
node.values.set(i, value); // UPDATE: In-place replacement
return;
}
if (node.isLeaf) {
node.keys.add(i, key);
node.values.add(i, value);
} else {
if (node.children.get(i).keys.size() == 2 * T - 1) {
splitChild(node, i, node.children.get(i));
if (key.compareTo(node.keys.get(i)) > 0) i++;
}
insertNonFull(node.children.get(i), key, value);
}
}
private void splitChild(Node parent, int i, Node fullNode) {
Node newNode = new Node();
newNode.isLeaf = fullNode.isLeaf;
for (int j = 0; j < T - 1; j++) {
newNode.keys.add(fullNode.keys.remove(T));
newNode.values.add(fullNode.values.remove(T));
}
if (!fullNode.isLeaf) {
for (int j = 0; j < T; j++) newNode.children.add(fullNode.children.remove(T));
}
parent.children.add(i + 1, newNode);
parent.keys.add(i, fullNode.keys.remove(T - 1));
parent.values.add(i, fullNode.values.remove(T - 1));
}
public void delete(K key) {
delete(root, key);
if (root.keys.isEmpty() && !root.isLeaf) root = root.children.get(0);
}
private void delete(Node node, K key) {
int i = node.findKey(key);
if (i < node.keys.size() && node.keys.get(i).compareTo(key) == 0) {
if (node.isLeaf) {
node.keys.remove(i);
node.values.remove(i);
} else {
// Simplified: Logic for internal node deletion usually involves
// finding predecessor/successor or merging.
node.keys.remove(i);
node.values.remove(i);
System.out.println("B-Tree: Internal key removed. Rebalancing required in production.");
}
} else if (!node.isLeaf) {
delete(node.children.get(i), key);
}
}
}
The Code: LSM-Tree (The Write Specialist)
package com.lsm;
import java.util.*;
import java.util.concurrent.ConcurrentSkipListMap;
public class LSMTree<K extends Comparable<K>, V> {
private static final Object TOMBSTONE = new Object();
private ConcurrentSkipListMap<K, Object> memTable = new ConcurrentSkipListMap<>();
private final List<Map<K, Object>> ssTables = new ArrayList<>();
private final int MAX_MEMTABLE_SIZE = 3;
// UPDATE & PUT are identical: Just append to memory
public void put(K key, V value) {
memTable.put(key, value);
checkFlush();
}
// DELETE: Append a Tombstone marker
public void delete(K key) {
System.out.println("[LSM] Deleting key: " + key + " (Adding Tombstone)");
memTable.put(key, TOMBSTONE);
checkFlush();
}
private void checkFlush() {
if (memTable.size() >= MAX_MEMTABLE_SIZE) {
System.out.println("[LSM] Flushing to SSTable segment...");
ssTables.add(0, new TreeMap<>(memTable));
memTable.clear();
}
}
@SuppressWarnings("unchecked")
public V get(K key) {
// 1. Check Memory
Object val = memTable.get(key);
if (val != null) return handleResult(val);
// 2. Check immutable segments (SSTables)
for (Map<K, Object> segment : ssTables) {
val = segment.get(key);
if (val != null) return handleResult(val);
}
return null;
}
private V handleResult(Object val) {
if (val == TOMBSTONE) {
System.out.println("[LSM] Key found but it is marked for deletion (Tombstone).");
return null;
}
return (V) val;
}
}
The Code for Benchmarking
import com.bt.BTree;
import com.lsm.LSMTree;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class DatabaseBenchmarkRunner {
private static final int DATA_SIZE = 100_000;
private static final Random random = new Random();
public static void main(String[] args) {
// Initialize engines (using degree 32 for B-Tree as is common)
BTree<Integer, String> bTree = new BTree<>(2);
LSMTree<Integer, String> lsmTree = new LSMTree<>();
List<Integer> keys = new ArrayList<>();
List<String> values = new ArrayList<>();
for (int i = 0; i < DATA_SIZE; i++) {
int randomValue = random.nextInt(DATA_SIZE);
keys.add(randomValue);
values.add("Value_" + randomValue);
}
System.out.println("Starting Benchmark for " + DATA_SIZE + " records...\n");
// --- PHASE 1: WRITE PERFORMANCE ---
long bTreeWriteTime = benchmark("B-Tree Write", () -> {
for (int i = 0; i < DATA_SIZE; i ++) {
bTree.put(keys.get(i), values.get(i));
}
});
long lsmWriteTime = benchmark("LSM-Tree Write", () -> {
for (int i = 0; i < DATA_SIZE; i++) {
lsmTree.put(keys.get(i), values.get(i));
}
});
// --- PHASE 2: UPDATE PERFORMANCE (Random) ---
long bTreeUpdateTime = benchmark("B-Tree Random Update", () -> {
for (int i = 0; i < DATA_SIZE/10; i++) {
bTree.put(random.nextInt(DATA_SIZE), "Updated_Value");
}
});
long lsmUpdateTime = benchmark("LSM-Tree Random Update", () -> {
for (int i = 0; i < DATA_SIZE/10; i++) {
lsmTree.put(random.nextInt(DATA_SIZE), "Updated_Value");
}
});
// --- PHASE 3: READ PERFORMANCE (Random) ---
long bTreeReadTime = benchmark("B-Tree Random Read", () -> {
for (int i = 0; i < DATA_SIZE; i++) {
bTree.get(random.nextInt(DATA_SIZE));
}
});
long lsmReadTime = benchmark("LSM-Tree Random Read", () -> {
for (int i = 0; i < DATA_SIZE; i++) {
lsmTree.get(random.nextInt(DATA_SIZE));
}
});
printSummary(bTreeWriteTime, lsmWriteTime, bTreeUpdateTime, lsmUpdateTime, bTreeReadTime, lsmReadTime);
}
private static long benchmark(String label, Runnable task) {
long start = System.nanoTime();
task.run();
long end = System.nanoTime();
long durationMs = (end - start) / 1_000_000;
System.out.printf("%-25s: %d ms\n", label, durationMs);
return durationMs;
}
private static void printSummary(long bW, long lW, long bU, long lU, long bR, long lR) {
System.out.println("\n--- Final Analysis ---");
System.out.println("Write Speed Winner : " + (lW < bW ? "LSM-Tree" : "B-Tree"));
System.out.println("Update Speed Winner : " + (lU < bU ? "LSM-Tree" : "B-Tree"));
System.out.println("Read Speed Winner : " + (bR < lR ? "B-Tree" : "LSM-Tree"));
System.out.println("----------------------");
}
}
3. The "Safety Net" (Write-Ahead Logging) đź“ť
I always wondered: What happens if the power cuts mid-update? The answer is WAL. The database "scribbles" your change into a simple, lightweight log file before it tries the heavy lifting of updating the main data files. If it crashes, it just reboots, checks the log, and finishes what it started. No data lost.
The big takeaway? There is no "perfect" database—only the right tool for the specific job. 🛠️
Top comments (1)
Hi Ashwin, It’s a great article.
The engaging visuals make the blog post more interesting to read.