---
topic: dev-practices
author: Crashtech Editorial
published: Nov 15, 2026 · read: 3 min
---

10 Core Data Structures Engineers Use Daily: Memory Layouts and Production Trade-Offs

A systems breakdown of the ten essential data structures: arrays, hash maps, B-trees, LSM trees, heaps, bloom filters, and skip lists.

– –

When code runs slowly, developers often reach for hardware upgrades. Yet profiling routinely reveals that the bottleneck is an inappropriate data structure: a linked list triggering continuous CPU cache stalls, or an in-memory hash map exhausting RAM with pointer alignment bloat. Data structures are blueprints for physical hardware interaction.

The Production Data Structure Spectrum

Modern distributed systems rely on ten foundational structures categorized by memory and I/O efficiency:

[ In-Memory Cache Friendly ]           [ Probabilistic & Compact ]          [ Disk & Storage Engines ]
- Contiguous Array                    - Bloom Filter                       - B-Tree / B+Tree (MySQL)
- Hash Table (Open Addressing)        - HyperLogLog (Cardinality)          - LSM-Tree (RocksDB, Cassandra)
- Binary Min/Max Heap (Priority)      - Count-Min Sketch (Frequency)       - Inverted Index (Elasticsearch)
- Skip List (Lock-Free Memory Table)

1. Contiguous Arrays vs Linked Lists: The Cache Line Reality

On paper, inserting into the middle of a linked list is $O(1)$ if you have the pointer, while an array requires $O(N)$ shifting. In real-world hardware, arrays frequently outperform linked lists for thousands of items.

Array in RAM:       [Item 1][Item 2][Item 3][Item 4]  <--- Loaded into CPU L1 Cache Line (64 Bytes) in 1 Cycle!
Linked List in RAM: [Item 1] ---> [Pointer] ---------> [Item 2 (Far away in RAM: Cache Miss = 200 Cycles!)]

Modern CPU memory controllers fetch data from RAM in 64-byte cache lines. When an algorithm reads array[0], the CPU automatically prefetches array[1]..array[7] into the L1 cache. Linked lists scatter node objects across the heap; traversing pointers stalls the CPU while waiting for main memory fetches.

2. Hash Tables: Chaining vs Open Addressing

Every engineer uses hash maps, but their collision resolution strategy dictates throughput:

StrategyMechanismCache LocalityMemory Footprint
Chaining (Java HashMap)Collisions create linked lists in bucketsPoor (pointer chasing across heap)High: 16-32 bytes overhead per entry
Open Addressing (Python / Rust)Probes adjacent array slots linearlyOptimal (sequential memory scan)Minimal: packed flat arrays

Modern high-performance runtimes (such as Python’s dict and Rust’s hashbrown) use open addressing with Swiss Tables or Robin Hood hashing, packing hash fingerprints into SIMD vector registers to evaluate 16 keys simultaneously.

3. Storage Engines: B+Trees vs LSM-Trees

When data spills from RAM to disk, data structures dictate write amplification and read latency:

B+Trees (In-Place Transactional Storage)

Used by PostgreSQL, MySQL (InnoDB), and SQLite.

  • All leaf nodes reside at identical depth and are linked sequentially for fast range scans.
  • Strength: $O(\log N)$ point reads and writes. Reads fetch exactly one 16KB disk page.
  • Weakness: Random writes update pages in-place on disk, causing heavy write amplification and fragmentation on SSDs.

Log-Structured Merge-Trees (LSM-Trees)

Used by RocksDB, Apache Cassandra, and ScyllaDB.

  • All writes append sequentially to an in-memory MemTable (often a Skip List) and a Write-Ahead Log (WAL).
  • When the MemTable fills, it flushes to disk as an immutable SSTable (Sorted String Table).
  • Strength: Extremely fast sequential write throughput.
  • Weakness: Point reads must search through multiple SSTable files on disk, mitigated by Bloom Filters.

4. Probabilistic Filters: Bloom Filters

When querying petabyte-scale storage, asking disk “Does this key exist?” incurs costly I/O. A Bloom Filter provides a sub-microsecond answer in memory:

[Key: "user_8492"]
       |
       +---> Hash 1 (h1) = 2  ---+
       +---> Hash 2 (h2) = 7  ---|---> Set bits [2, 7, 11] in Bit Array
       +---> Hash 3 (h3) = 11 ---+

When checking a key:

  • If any bit in [2, 7, 11] is 0: The key is definitely NOT in the database. (Skips disk read!)
  • If all bits are 1: The key MIGHT be in the database. (Proceed to disk read).

Do

  • Prefer contiguous flat arrays and open-addressing hash maps to maximize CPU L1/L2 cache prefetching.
  • Deploy B+Trees for read-heavy transactional workloads and LSM-Trees for append-heavy streaming pipelines.
  • Protect disk storage engines with in-memory Bloom Filters to eliminate wasted reads on missing keys.

Don't

  • Do not default to linked lists without measuring the CPU cache-miss penalty on target hardware.
  • Avoid building multi-threaded concurrent trees with coarse locks; use Skip Lists with atomic CAS operations.
  • Never allocate small, fragmented heap objects inside high-frequency loops; use memory pools or arenas.

Data structures are not theoretical academic exercises; they are the physical mechanisms through which software commands hardware registers, cache lines, and storage controllers. Understanding their real-world trade-offs separates junior code implementers from master systems architects.

Advertisement

Frequently asked questions

Why are contiguous arrays often faster than linked lists even for insertions?

Modern CPU performance is dominated by hardware caching (L1/L2/L3) and spatial locality. Contiguous arrays load entire sequential memory cache lines into CPU registers, whereas linked lists scatter nodes across heap pointers, causing frequent CPU cache misses.

What is the structural difference between a B-Tree and an LSM-Tree?

B-Trees organize data into sorted, balanced page trees updated in-place on disk, optimizing for read-heavy transactional workloads. LSM-Trees (Log-Structured Merge-Trees) buffer writes sequentially in memory before flushing immutable SSTables, maximizing write throughput.

What is a Bloom Filter and where is it used in production databases?

A Bloom Filter is a space-efficient probabilistic data structure that tests set membership. It can return false positives (might be in set) but never false negatives (definitely not in set), allowing databases like Cassandra and RocksDB to skip reading disks for missing keys.

Why do distributed databases prefer Skip Lists over red-black trees in memory?

Skip lists implement probabilistic multi-level linked lists that provide $O(\log N)$ search without requiring complex tree rotations. This allows lock-free concurrent updates using atomic compare-and-swap (CAS) pointers, drastically outperforming locked binary trees.

Sources & further reading

/* Comments */