Core Data Structures

The selected data structure determines how a backend system behaves.

Overview

A data structure organizes data for efficient storage and access. Data structures help explain database indexes, cache systems, and how distributed systems behave. They explain Redis performance, PostgreSQL index management, and data consistency in distributed databases.

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

Practical effect: linked-list insertion and deletion have O(1) complexity, but cache misses dominate actual performance. Cache locality, described in the memory management notes, determines 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 hash function converts a key into an array index. The index lets the table store and retrieve data 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 describes most real-world graphs

Graphs in the backend

LSM-Tree

Core concept

An LSM-Tree is a write-optimized data structure designed for high write throughput. A B+Tree is optimized for reads.

How it works

flowchart TD
    W["Write request"] --> WAL["WAL (Write-Ahead Log, on disk)"]
    WAL --> MT["MemTable (in memory, sorted)"]
    MT -->|"when full"| IMT["Immutable MemTable"]
    IMT -->|"flush"| L0["SSTable L0 (on disk)"]
    L0 -->|"compaction"| L1["SSTable L1"]
    L1 -->|"compaction"| L2["SSTable L2"]
    L2 --> More["..."]

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): places the WAL and upper LSM levels on the fast SSD
• Asynchronous request processing: SpanDB combines request processing with polling I/O to reduce inter-thread synchronization. This does not guarantee that client requests experience no interference.
• 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 skip list adds several search levels to a sorted linked list. These levels support 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

Distributed System Conflicts

When several nodes modify the same data at once, conflicts arise. A CRDT is a data structure whose merge rules resolve concurrent updates deterministically.

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

Systems use data structures that match their workloads. The table lists the main structures used by representative systems.

Read-heavy workloads use a B+Tree to reduce disk seeks. Write-heavy workloads use an LSM-Tree for sequential writes. Hash tables support in-memory lookups, while skip lists or trees support sorted range queries. Large-scale membership tests and cardinality estimates can sometimes accept reduced accuracy.

Probabilistic structures such as Bloom Filter and HyperLogLog reduce memory use in these workloads. CRDTs handle conflicts in distributed AP systems, while consensus algorithms handle consistency in CP systems. Selecting a data structure means choosing which operations to accelerate and which costs to accept.