Core Data Structures

How a backend system behaves comes down to which data structure was chosen.

Overview

A data structure is a scheme for storing and accessing data efficiently. For a backend engineer, data structures are the key to understanding database indexes, cache systems, and how distributed systems behave. Why Redis is fast, how PostgreSQL manages indexes, how a distributed database keeps data consistent -- all of it starts with data structures.

Arrays and linked lists

Time complexity by operation

Cache efficiency

Array (Cache-friendly):
  Memory: [1][2][3][4][5][6][7][8]  ← contiguous layout
  1 cache line loaded → 8 elements reachable
 
Linked list (Cache-unfriendly):
  Memory: [Node1]...[Node5]...[Node2]...[Node7]...
  Nodes scattered all over memory → frequent cache misses

What this means in practice: by Big-O alone, insertion and deletion in a linked list are O(1), but in real performance the cost of cache misses dominates. Cache locality, covered in the memory management notes, is what decides actual throughput.

Backend use cases

• Arrays: JSON arrays, Redis lists (internally quicklist plus listpack), contiguous log buffers
• Linked lists: the doubly linked list inside an LRU cache, OS process queues, free lists in memory allocators

Hash tables

Core idea

A key is passed through a hash function to produce an array index, so data can be stored and looked up in O(1) time.

Key: "user:1001"
  → hash("user:1001") = 7
  → table[7] = {name: "Kim", age: 30}
 
┌───┬───┬───┬───┬───┬───┬───┬────────────────┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7: user:1001   │ 8 │
└───┴───┴───┴───┴───┴───┴───┴────────────────┴───┘

Collision resolution

Chaining

Several entries at the same index are stored in a linked list:

table[3] → [key:A, val:1] → [key:B, val:2] → [key:C, val:3]

• Upside: simple to implement, works even when the load factor exceeds 1
• Downside: extra memory for pointers, poor cache behavior

Open addressing

On collision, probe for another empty slot:

Robin Hood hashing

A variant of open addressing in which an element with a long probe distance displaces one with a shorter distance:

• The Rust standard library HashMap used it in the past, but switched to a SwissTable (hashbrown) design in 1.36
• Reducing the variance of probe distances improves worst-case performance

Where hash tables show up

Tree structures

BST (Binary Search Tree)

A binary tree that follows the rule left child < parent < right child:

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

Self-balancing trees

AVL Tree

• At every node, the height difference between the left and right subtrees is at most 1
• Strict balance means fast search, at the cost of rotations on insert and delete
• Used in: in-memory indexes, dictionary structures

Red-Black Tree

• Each node is either red or black
• Rules: the root is black, the children of a red node are black, every path holds the same number of black nodes
• Looser balance than AVL, so fewer rotations on insert and delete
• Used in: the Linux CFS scheduler (process management and CPU scheduling), Java TreeMap, C++ std::map

B-Tree and B+Tree

B-Tree

• A multiway search tree: one node holds several keys
• Optimized for disk I/O: node size is matched to a disk block (4KB to 16KB)
• A B-Tree of order m: each node holds at most m-1 keys and m children

B-Tree (order 4):
              [10 | 20 | 30]
             /    |    |    \
    [3|5|7] [12|15] [22|25] [35|40|45]

B+Tree -- the standard for DB indexes

A B-Tree variant that is the de facto standard for database indexes:

B+Tree:
Internal nodes: keys only (routing)
         [10 | 20 | 30]
        /    |    |    \
Leaf nodes: keys + data, chained as a linked list
[3|5|7] ←→ [10|12|15] ←→ [20|22|25] ←→ [30|35|40]

Why is a B+Tree optimal for a database?

1. High fan-out means a shallower tree, which minimizes disk I/O
2. The leaf linked list makes range queries (WHERE age BETWEEN 20 AND 30) efficient
3. Small internal nodes mean more of them fit in cache

PostgreSQL, MySQL InnoDB, and SQLite all use B+Tree-based indexes.

Heaps

Definition

A complete binary tree plus the heap property (parent >= child for a max heap, parent <= child for a min heap).

Min Heap:
        1
       / \
      3   5
     / \ / \
    7  9 8  10

Operation complexity

Backend applications

Graphs

Representations

Adjacency Matrix

    A  B  C  D
A [ 0  1  1  0 ]
B [ 1  0  0  1 ]
C [ 1  0  0  1 ]
D [ 0  1  1  0 ]

• Space: O(V^2)
• Edge lookup: O(1) -- matrix[u][v]
• Suits dense graphs

Adjacency List

A → [B, C]
B → [A, D]
C → [A, D]
D → [B, C]

• Space: O(V + E)
• Edge lookup: O(degree(v))
• Suits sparse graphs -- which is most real-world graphs

Graphs in the backend

LSM-Tree

Core concept

A write-optimized data structure. Where a B+Tree is read-optimized, an LSM-Tree is designed for high write throughput.

How it works

Components

The read path

Read request → check MemTable → check L0 SSTable → L1 → L2 → ...
             (fast)          (Bloom Filter rules out misses fast)

B+Tree vs LSM-Tree

Systems that use it

Recent optimization directions

• SpanDB (FAST 2021): exploits NVMe SSD speed by placing the WAL and the upper LSM levels on the fast SSD
• Dynamic scheduling: uses NVMe protocol characteristics to run flushes and compactions without interfering with client requests
• Tiered Compaction: groups SSTables by tier instead of compacting level by level, reducing write amplification

Bloom Filter

Concept

A data structure that answers whether an element belongs to a set probabilistically:

• If it answers "absent", the element is definitely absent (no false negatives)
• If it answers "present", the element may or may not be there (false positives are possible)

Structure

Bit array: [0][0][0][0][0][0][0][0][0][0]
             ↑        ↑     ↑
hash1("key") hash2("key") hash3("key")
 
After insert: [0][1][0][0][1][0][1][0][0][0]
 
Lookup: if all 3 hashed positions are 1, "probably present"
        if any one is 0, "definitely absent"

False positive probability

With a bit array of size m, k hash functions, and n inserted elements:

P(false positive) ≈ (1 - e^(-kn/m))^k

Backend applications

Skip List

Concept

A sorted linked list with several levels of express lanes added on top, giving O(log n) search:

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

Time complexity

Advantages over a B+Tree

• Simpler to implement (no rotations)
• Lock-free implementations are possible, which helps under concurrency
• This is why the Redis Sorted Set (ZSET) uses a Skip List

CRDT

The problem: conflicts in distributed systems

When several nodes modify the same data at once, conflicts arise. A CRDT is a data structure in which conflicts are mathematically impossible.

Core idea

Every edit operation is expressed as a commutative operation:

Node A: counter += 1 (A: 1)
Node B: counter += 3 (B: 3)
 
Merge: A + B = 1 + 3 = 4 (order does not matter)

CRDT types

Real-world use

Relationship to the CAP theorem

CAP theorem: only 2 of Consistency, Availability, Partition Tolerance can be chosen
 
In an AP (Availability + Partition Tolerance) system, a CRDT gives a
mathematical guarantee of Eventual Consistency.
→ Consensus algorithms such as Raft/Paxos are the answer for CP (Consistency + Partition Tolerance) systems

Probabilistic data structures

HyperLogLog -- estimating distinct counts

Estimates cardinality over a large dataset using very little memory:

# Redis HyperLogLog
PFADD visitors "user1" "user2" "user3"
PFCOUNT visitors
# (integer) 3
# Even a billion entries still use only ~12KB

Count-Min Sketch -- frequency estimation

Approximates the occurrence frequency of an item in streaming data:

• Returns a value at least as large as the true frequency (overestimates are possible, underestimates are not)
• Used for: network traffic analysis, hot item detection, anomaly detection

Cuckoo Filter

An improvement on the Bloom Filter:

• Supports deletion (a Bloom Filter cannot delete)
• Better space efficiency at high load factors
• Used for: duplicate detection, network packet filtering

Summary

The data structure a system relies on is the visible result of matching a structure to a workload. The table below lists which structure sits at the core of several representative systems.

Read-heavy workloads use a B+Tree to cut disk seeks, and write-heavy workloads pick an LSM-Tree for sequential writes. In-memory lookups belong to hash tables, while sorted range queries belong to skip lists or trees. In some workloads accuracy can be traded away, as in large-scale membership tests and cardinality estimation.

There, probabilistic structures such as Bloom Filter and HyperLogLog save a great deal of memory. In a distributed setting, CRDTs handle conflicts in AP systems and consensus algorithms handle consistency in CP systems. Choosing a data structure is ultimately a trade-off about which operations get to be fast and what gets given up.