How Real Systems Use DSA

Interview questions can feel like puzzles with no connection to real work. In fact, almost every structure in this course sits inside software you use daily. Knowing where they live makes you better at system design rounds, at reading documentation, and at debugging slow systems, because you can reason about what the software is doing underneath.

This lesson tours five areas: database indexes, storage engines, network routing, schedulers and timers, and distributed caches. Each section names the structure, explains why it was chosen, and includes a small model you can run. These are simplified teaching models, not the real implementations.

Database indexes are B-trees

When you write CREATE INDEX in MySQL, the index is a B-tree (strictly, a B+ tree variant). The MySQL reference manual says: "With the exception of spatial indexes, InnoDB indexes are B-tree data structures", and the default index page is 16 KB.

Why not a binary search tree? Because data lives on disk, and reading one page from disk costs far more than comparing keys already in memory. A B-tree node fills a whole page and holds hundreds of keys, so each node has hundreds of children. This fanout makes the tree extremely shallow, and a lookup reads only a few pages.

import math

def levels_needed(rows, fanout):
    return math.ceil(math.log(rows, fanout))

for rows in [10**5, 10**7, 10**9]:
    print(f"{rows:>13,} rows: binary tree ~{levels_needed(rows, 2)} levels, "
          f"B-tree (fanout 500) ~{levels_needed(rows, 500)} levels")

      100,000 rows: binary tree ~17 levels, B-tree (fanout 500) ~2 levels
   10,000,000 rows: binary tree ~24 levels, B-tree (fanout 500) ~3 levels
1,000,000,000 rows: binary tree ~30 levels, B-tree (fanout 500) ~4 levels

(Fanout 500 is an illustrative figure; the real number depends on key size.) Three or four page reads for a billion rows, and the top levels usually stay cached in memory. In a B+ tree, the leaves hold the keys in sorted order and are linked together, so a range query such as WHERE amount BETWEEN 500 AND 1000 finds the start with a tree search and then simply walks along the leaves. You can model that walk with a sorted list and bisect:

import bisect

# (amount, order_id) pairs, kept sorted like the leaf level of an index
index = sorted([(1299, "A17"), (450, "A03"), (999, "A11"), (500, "A05"), (2150, "A21"),
                (750, "A08"), (1000, "A12"), (499, "A04"), (875, "A09")])

def range_scan(index, low, high):
    start = bisect.bisect_left(index, (low,))            # find the first key >= low
    out = []
    for amount, oid in index[start:]:                    # then walk forward
        if amount > high:
            break
        out.append(oid)
    return out

print(range_scan(index, 500, 1000))

['A05', 'A08', 'A09', 'A11', 'A12']

This is why an index helps BETWEEN and ORDER BY but cannot help WHERE amount % 7 = 0: the sorted order only speeds up questions about ranges of the key.

Storage engines: LSM trees and Bloom filters

Write-heavy databases such as RocksDB and Apache Cassandra use a log-structured merge tree (LSM tree). New writes go into a sorted structure in memory; when it fills, it is written to disk as an immutable sorted file. Background jobs merge files, exactly like the merge step of Merge Sort or a k-way merge with a heap. Writes are fast because they are sequential.

Reads may have to check several files. To avoid opening files that cannot contain the key, each file carries a Bloom filter: a "definitely not here" answer skips the file. B-trees and LSM trees are the two main families; B-trees usually favour reads and LSM trees favour heavy writes.

Network routing runs Dijkstra

Inside a large organisation's network, routers using the OSPF protocol share a map of links and costs, and each router computes shortest paths to every destination with Dijkstra's algorithm; the OSPF specification (RFC 2328) describes this calculation. When a link fails, routers flood the update and recompute. Map and ride apps also start from Dijkstra but add heavy precomputation and goal-directed search (such as A*), because a country-sized road graph is too big to search from scratch on every request.

Schedulers and timers use ordered structures

An operating system must keep choosing which task runs next. Linux's Completely Fair Scheduler (CFS) kept runnable tasks in a red-black tree, a self-balancing BST; the kernel documentation says "CFS maintains a time-ordered rbtree, where all runnable tasks are sorted by the p->se.vruntime key", so the task that has had the least CPU time is the leftmost node. From Linux 6.6 the kernel began moving to a newer scheduler called EEVDF.

Timers are the other half: "retry this payment in 30 seconds", "expire this OTP in 5 minutes". A min-heap of deadlines gives the next timer to fire in O(1) and adds a timer in O(log n). Cancelling a timer deep inside the heap is awkward, so many systems use lazy cancellation: mark it cancelled and skip it when it reaches the top.

import heapq
import itertools

class TimerQueue:
    def __init__(self):
        self.heap, self.cancelled = [], set()
        self.ids = itertools.count(1)

    def schedule(self, at, action):
        tid = next(self.ids)
        heapq.heappush(self.heap, (at, tid, action))   # tid breaks ties in order
        return tid

    def cancel(self, tid):
        self.cancelled.add(tid)                        # O(1): skip it later

    def run_until(self, now):
        while self.heap and self.heap[0][0] <= now:
            at, tid, action = heapq.heappop(self.heap)
            if tid in self.cancelled:
                self.cancelled.discard(tid)
                continue
            print(f"t={at:>3}: {action}")

timers = TimerQueue()
timers.schedule(300, "expire OTP for Priya")
retry = timers.schedule(30, "retry UPI payment #8812")
timers.schedule(60, "send delivery reminder to Kabir")
timers.schedule(30, "refresh exchange rates")
timers.cancel(retry)                                   # payment succeeded meanwhile
timers.run_until(100)
timers.run_until(400)

t= 30: refresh exchange rates
t= 60: send delivery reminder to Kabir
t=300: expire OTP for Priya

The tid in each tuple is a tie-breaker: two timers at the same time fire in the order they were scheduled, and Python never has to compare the action strings. Systems with millions of timers, such as network stacks, often use a timing wheel instead, which is an array of buckets indexed by time, like a circular queue.

Distributed caches use consistent hashing

A website spreads its cache across several servers. The obvious rule server = hash(key) % n breaks badly when a server is added: almost every key now maps to a different server, so the whole cache misses at once. Consistent hashing places servers and keys on a ring of hash values; each key belongs to the first server clockwise from it. Adding a server only moves the keys between it and its neighbour. Each server is placed at many points ("virtual nodes") to spread the load evenly. The ring is just a sorted list plus bisect:

import bisect, hashlib

def h(text):
    return int.from_bytes(hashlib.md5(text.encode()).digest()[:8], "big")

class Ring:
    def __init__(self, servers, vnodes=100):
        self.points = sorted((h(f"{s}#{i}"), s) for s in servers for i in range(vnodes))
        self.hashes = [p for p, _ in self.points]

    def server_for(self, key):
        i = bisect.bisect(self.hashes, h(key)) % len(self.points)   # wrap around
        return self.points[i][1]

keys = [f"user:{i}" for i in range(10000)]
before = Ring(["cache-a", "cache-b", "cache-c", "cache-d"])
after = Ring(["cache-a", "cache-b", "cache-c", "cache-d", "cache-e"])
moved_ring = sum(before.server_for(k) != after.server_for(k) for k in keys)
moved_mod = sum(h(k) % 4 != h(k) % 5 for k in keys)
print(f"consistent hashing moved {moved_ring / len(keys):.0%} of keys")
print(f"hash % n moved {moved_mod / len(keys):.0%} of keys")

consistent hashing moved 19% of keys
hash % n moved 80% of keys

Going from 4 to 5 servers, consistent hashing moves about 1/5 of the keys (the new server's fair share), while % n moves about 4/5. MD5 is fine here because this is load spreading, not security.

A map from problems to structures

Common mistakes

• Assuming an index helps every query. It helps equality, ranges and ordering on the indexed columns, not arbitrary expressions on them.
• Using hash(key) % n for sharding when servers can be added or removed.
• Removing cancelled items from the middle of a heap with list.remove(), which is O(n) and breaks the heap order unless you re-heapify.
• Treating teaching models as real implementations. Production B-trees, schedulers and rings handle concurrency, crashes and many details left out here.

Key points

• Database indexes are B-trees: high fanout keeps them 3 to 4 levels deep even for huge tables, and sorted leaves make range scans cheap.
• LSM-tree storage engines merge sorted files and use Bloom filters to skip files.
• Link-state routing protocols such as OSPF compute routes with Dijkstra's algorithm.
• Schedulers keep tasks ordered in balanced trees; timers use heaps with lazy cancellation or timing wheels.
• Consistent hashing moves only about 1/n of keys when a server is added.
• Recognising these structures helps in system design interviews and when tuning real systems.

class TokenBucket:
    def __init__(self, capacity, rate):
        self.capacity, self.rate = capacity, rate
        self.tokens, self.last = capacity, 0.0

    def allow(self, now):
        elapsed = now - self.last
        self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

bucket = TokenBucket(capacity=3, rate=1)
for t in [0, 0.1, 0.2, 0.3, 1.5, 1.6, 5]:
    print(t, bucket.allow(t))

0 True
0.1 True
0.2 True
0.3 False
1.5 True
1.6 False
5 True