Mastering Time‑Space Trade‑offs: Indexing, Caching, Compression & More

Introduction

Software design is often a series of trade‑offs between performance and other quality attributes such as security, scalability, and observability. Before a system reaches a bottleneck, developers can apply a set of well‑known techniques to improve performance without incurring excessive cost.

Six General Time‑Space Trade‑off Techniques

1. Indexing

Indexing exchanges extra storage for faster query time, turning linear scans (O(n)) into logarithmic or constant‑time lookups (O(log n) or O(1)). Common index structures and their typical use cases include:

Hash Table : Provides O(1) lookups; used by most language‑level map/dict implementations.

Binary Search Tree (e.g., Red‑Black Tree) : Balanced tree used in Java TreeMap, C++ std::map, Linux CPU scheduler, etc.

B‑Tree : Multi‑way tree for large datasets; used by MongoDB.

B+ Tree : Leaf‑only variant; used by MySQL and many file systems.

LSM Tree : Write‑optimized structure for NoSQL stores; sacrifices read speed for write throughput.

Trie (Prefix Tree) : Efficient for prefix searches, auto‑completion, URL routing; radix tree variant used in Nginx Geo module and Redis.

Skip List : Layered ordered list; suitable for high‑concurrency writes, used by Redis ZSet.

Inverted Index : Keyword‑to‑document mapping; core of Elasticsearch and Prometheus label queries.

When designing database indexes, consider primary‑key choice (auto‑increment vs. UUID) and follow practical guidelines such as indexing primary keys, frequently filtered columns, and avoiding indexes on high‑cardinality or frequently updated fields.

2. Caching

Caching also trades storage for speed, and it appears at many layers—from DNS resolvers and CDN edge nodes to in‑process memory caches and CPU caches. Typical cache‑related concerns include invalidation, penetration, thundering herd, and avalanche. Mitigations involve empty‑value caching, bloom filters, request coalescing, and random TTLs. Object‑pooling (e.g., JVM constant pool, connection pools, thread pools, Go sync.Pool) is a form of caching that reduces allocation overhead.

There are only two hard things in Computer Science: cache invalidation and naming things.

3. Compression

Compression spends CPU cycles to reduce data size, which can lower network latency or storage cost. Lossless techniques are used for HTTP gzip/deflate, HPACK header compression, JS/CSS minification, binary RPC payloads, and storage of large blobs. Lossy compression applies to media (MP3, JPEG) and can be acceptable when bandwidth is limited. Extreme size reduction can involve tree‑shaking, removing unused code, enabling HTTP/2, trimming cookies, and using bit‑maps or Bloom filters.

4. Prefetching

Prefetching adds a “time‑for‑time” trade‑off: it spends time up‑front to load data that will likely be needed soon, improving perceived latency. Common scenarios include video buffering, HTTP/2 Server Push, client‑side background loading, server warm‑up (populating caches, JIT compilation), and pre‑allocating resources for flash‑sale or ticket‑sale spikes. The downside is increased startup time and resource consumption.

5. Peak‑Valley Smoothing (削峰填谷)

This technique trades “peak” time for “valley” time, smoothing workload spikes. Approaches include:

Front‑end lazy loading and code splitting for first‑paint optimization.

Rate limiting, throttling, and debouncing at gateways to protect against abusive traffic.

Message‑queue buffering and asynchronous processing for backend bursts.

Scheduling background jobs during off‑peak periods.

Back‑off retry strategies to avoid error‑storm cascades.

6. Batch Processing

Batching aggregates many small operations into a larger one, reducing per‑operation overhead. Examples span from bundling JS assets, using requestAnimationFrame for UI updates, queueing database writes, to OS‑level buffered I/O (writev/readv). Optimal batch size varies by system: Redis pipelines work well with 50‑100 keys, MySQL bulk inserts around 5 000‑10 000 rows, and message‑queue payloads often capped at ~1 MB.

Advanced Parallelism Techniques (Preview)

The next part of the series will cover four advanced methods that focus on increasing parallelism: resource exhaustion (八门遁甲), horizontal scaling (影分身术), sharding (奥义), and lock‑free algorithms (秘术).