DSA in Real Systems: From B-Trees to Bloom Filters

Every time you run a database query, open a web page, or push to Git, data structures and algorithms are doing the heavy lifting behind the scenes. This is not abstract theory — it is the engineering that makes software fast. Understanding why these choices were made will make you a better system designer, a stronger interviewer, and a more thoughtful developer.

1. B-Trees and B+ Trees — The Backbone of Databases

A binary search tree (BST) is great in memory, but terrible on disk. Why? Each node access is a disk read, and a BST with a million keys is 20 levels deep — that is 20 disk reads per lookup. Disk reads take milliseconds, not nanoseconds.

B-trees solve this by making each node hold hundreds of keys and hundreds of children. A node fills an entire disk page (typically 4-16 KB). A B-tree with a branching factor of 500 can store 500^3 = 125 million keys in just 3 levels — three disk reads for any lookup.

BST node (1 key per node):
┌───┐
│ 42│
└───┘
20 levels = 20 disk reads for 1M keys
B-tree node (~500 keys per node):
┌──────────────────────────────────────────┐
│ 5 │ 12 │ 28 │ 42 │ 67 │ … │ 491 │ 503 │
└──────────────────────────────────────────┘
3 levels = 3 disk reads for 125M keys

B+ trees — the variant databases actually use

• All data lives in leaf nodes only. Internal nodes store only keys for routing.
• Leaf nodes are linked in a doubly-linked list, making range scans (e.g., WHERE age BETWEEN 20 AND 30) a sequential walk.

MySQL InnoDB stores every table as a B+ tree (clustered index). PostgreSQL uses B-trees for its default index type. SQLite is essentially a collection of B-trees.

# Simplified B-tree node structure
class BTreeNode:
    def __init__(self, leaf=False):
        self.keys = []        # sorted keys
        self.children = []    # child pointers (len = len(keys) + 1)
        self.leaf = leaf

    def search(self, key):
        i = 0
        while i < len(self.keys) and key > self.keys[i]:
            i += 1
        if i < len(self.keys) and key == self.keys[i]:
            return True
        if self.leaf:
            return False
        return self.children[i].search(key)

Why this matters for interviews: when someone asks “how does an index work?” the answer is B+ tree. When they ask “why is a range query fast on an indexed column?” the answer is linked leaf nodes.

2. Skip Lists — How Redis Does Sorted Sets

Redis’s ZSET (sorted set) supports ZADD, ZRANK, ZRANGE, and ZRANGEBYSCORE — all in O(log n). The underlying structure is a skip list.

A skip list is a linked list with express lanes. Imagine a train system:

• Level 0 (local): stops at every station (every element)
• Level 1 (express): stops at every ~2nd station
• Level 2 (super express): stops at every ~4th station

To search, start at the top express lane, ride until you overshoot, drop down a level, and repeat.

Level 3: HEAD ──────────────────────────→ 50 ──────────→ NIL
Level 2: HEAD ──────→ 20 ──────────────→ 50 ──→ 70 ──→ NIL
Level 1: HEAD ──→ 10 → 20 ──→ 30 ──────→ 50 → 60 → 70 → NIL
Level 0: HEAD → 5 → 10 → 20 → 25 → 30 → 50 → 55 → 60 → 70 → NIL

import random

class SkipNode:
    def __init__(self, key, level):
        self.key = key
        self.forward = [None] * (level + 1)

class SkipList:
    def __init__(self, max_level=16, p=0.5):
        self.max_level = max_level
        self.p = p
        self.header = SkipNode(-1, max_level)
        self.level = 0

    def random_level(self):
        lvl = 0
        while random.random() < self.p and lvl < self.max_level:
            lvl += 1
        return lvl

    def search(self, key):
        current = self.header
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
        current = current.forward[0]
        return current and current.key == key

Why skip list over a balanced BST? Redis chose skip lists because they are simpler to implement, naturally support range operations (just walk the bottom level), and are easier to make concurrent (no tree rotations).

3. Inverted Indexes — How Google Search Works

When you search “data structures tutorial,” Google does not scan every web page. It looks up each word in an inverted index — a hash map from words to the list of documents containing that word.

# Building a simple inverted index
from collections import defaultdict

def build_index(documents):
    index = defaultdict(set)
    for doc_id, text in enumerate(documents):
        for word in text.lower().split():
            index[word].add(doc_id)
    return index

docs = [
    "data structures and algorithms",
    "algorithms for competitive programming",
    "data science with python",
]
index = build_index(docs)
# Search "data algorithms" → intersection of index["data"] and index["algorithms"]
result = index["data"] & index["algorithms"]
print(result)  # {0}

Real search engines enhance this with:

• Tries for autocomplete (prefix matching)
• TF-IDF or BM25 for ranking (not just presence, but relevance)
• Positional indexes that record where each word appears (for phrase queries)

Elasticsearch and Apache Lucene are essentially giant inverted indexes with compression, caching, and distribution layers on top.

4. Dijkstra and Bellman-Ford — How the Internet Routes Packets

Your data travels across the internet through routers. Each router needs to decide: “which neighbour should I forward this packet to?” This is a shortest-path problem.

OSPF uses Dijkstra

The Open Shortest Path First protocol has each router share its link states (connections and costs) with all other routers. Each router then runs Dijkstra’s algorithm locally to build a shortest-path tree to every destination.

RIP uses Bellman-Ford

The Routing Information Protocol is simpler. Each router tells its neighbours “I can reach network X in Y hops.” Neighbours update their tables. This is distributed Bellman-Ford — it converges after at most V-1 rounds.

# Simplified OSPF: each router runs Dijkstra
import heapq

def dijkstra_routing(graph, source):
    dist = {node: float('inf') for node in graph}
    dist[source] = 0
    next_hop = {source: source}
    pq = [(0, source)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                next_hop[v] = next_hop[u] if u != source else v
                heapq.heappush(pq, (dist[v], v))

    return dist, next_hop

Why this matters: when someone asks in a system design interview “how does traffic get routed?”, you can explain that it is literally Dijkstra running on every router.

5. Git’s Directed Acyclic Graph

Every Git commit is a node in a directed acyclic graph (DAG). Each commit points to its parent(s). A merge commit has two parents. Branches are just pointers to commits.

A ← B ← C ← D   (main)
↖
E ← F  (feature branch)
Merge:
A ← B ← C ← D ← G   (main, after merge)
↖       ↗
E ← F

SHA-1 hashing ensures integrity. Each commit’s hash depends on its content, its parent’s hash, the tree hash, and metadata. If anyone tampers with history, all subsequent hashes change — immediately detectable.

# Conceptual: Git objects
class GitCommit:
    def __init__(self, message, tree_hash, parents):
        self.message = message
        self.tree_hash = tree_hash
        self.parents = parents  # list of parent commit hashes
        self.hash = self._compute_hash()

    def _compute_hash(self):
        import hashlib
        content = f"tree {self.tree_hash}\n"
        for p in self.parents:
            content += f"parent {p}\n"
        content += f"\n{self.message}"
        return hashlib.sha1(content.encode()).hexdigest()

Operations as graph algorithms:

• git log = DFS/BFS traversal of the commit DAG
• git merge-base = finding the Lowest Common Ancestor
• git rebase = transplanting a subgraph to a new parent

6. Consistent Hashing — How Load Balancers Distribute Traffic

With regular hashing (server = hash(key) % N), adding or removing a server remaps almost every key. Consistent hashing arranges servers on a virtual ring so that only K/N keys move when a server is added or removed.

Server A
/         

Key 3 •           • Key 1
|     ring      |
Server C            Server B
\           /
• Key 2

import hashlib
import bisect

class ConsistentHash:
    def __init__(self, nodes, replicas=100):
        self.replicas = replicas
        self.ring = []           # sorted hash values
        self.hash_to_node = {}   # hash -> server name

        for node in nodes:
            for i in range(replicas):
                h = self._hash(f"{node}:{i}")
                self.ring.append(h)
                self.hash_to_node[h] = node
        self.ring.sort()

    def _hash(self, key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def get_node(self, key):
        h = self._hash(key)
        idx = bisect.bisect_right(self.ring, h) % len(self.ring)
        return self.hash_to_node[self.ring[idx]]

Used by: Amazon DynamoDB, Apache Cassandra, Memcached, and CDNs like Akamai. Virtual nodes (replicas) ensure even distribution.

7. Bloom Filters — Probabilistic Membership Testing

A Bloom filter tells you “definitely not in the set” or “probably in the set.” It uses k hash functions and a bit array. No false negatives, but possible false positives.

Chrome Safe Browsing: before navigating to a URL, Chrome checks a local Bloom filter of known malicious URLs. If the filter says “no,” the URL is safe — no network request needed. If “maybe yes,” Chrome sends the hash to Google’s server for a definitive check.

import hashlib

class BloomFilter:
    def __init__(self, size, num_hashes):
        self.size = size
        self.num_hashes = num_hashes
        self.bits = [False] * size

    def _hashes(self, item):
        results = []
        for i in range(self.num_hashes):
            h = int(hashlib.sha256(
                f"{item}:{i}".encode()
            ).hexdigest(), 16) % self.size
            results.append(h)
        return results

    def add(self, item):
        for h in self._hashes(item):
            self.bits[h] = True

    def might_contain(self, item):
        return all(self.bits[h] for h in self._hashes(item))

bf = BloomFilter(1000, 5)
bf.add("malicious-site.com")
print(bf.might_contain("malicious-site.com"))  # True
print(bf.might_contain("safe-site.com"))        # Almost certainly False

Other uses:

• Databases: check if an SSTable might contain a key before reading from disk (RocksDB, Cassandra)
• Spell checkers: quickly reject correctly-spelled words before expensive dictionary lookup
• Network deduplication: detect duplicate packets without storing all seen packets

8. Why Understanding DSA Makes You a Better System Designer

Every system design decision is, at its core, a data structure choice:

When an interviewer asks “design a URL shortener,” the right answer involves hash tables. When they ask “design a search engine,” you need inverted indexes. When they ask “design a distributed cache,” consistent hashing is the answer.

The gap between “I know arrays and linked lists” and “I can design systems” is filled by understanding how these fundamental structures are applied at scale.

Real-World Decision Making

Here is a decision framework for choosing the right data structure in system design:

1. What operations dominate? Reads, writes, range scans, or membership checks?
2. Where does data live? Memory (arrays, hash maps, trees) or disk (B-trees, LSM trees)?
3. What are the scale constraints? Millions of keys? Billions? Distributed?
4. Is approximate OK? If yes, probabilistic structures (Bloom filters, HyperLogLog) save massive space.
5. Do you need ordering? If yes, hash maps are out — you need trees or skip lists.

Recap

Data structures and algorithms are not just interview questions — they are the foundation of every system you use:

• B+ trees make databases fast by minimising disk reads
• Skip lists give Redis efficient sorted operations
• Inverted indexes make search engines possible
• Dijkstra routes your internet traffic
• DAGs give Git its branching and merging model
• Consistent hashing keeps distributed systems balanced
• Bloom filters save bandwidth and disk reads everywhere

Study these not just for interviews, but because understanding them makes you a fundamentally better engineer.

Next steps

Ready to compare data structures head-to-head? Check out Data Structures Comparison Guide for a comprehensive decision framework.

Questions or feedback? Email codeloomdevv@gmail.com.