Time-Based Key-Value Store: DSA Design & Implementation

A TimeMap stores every version of a value and answers: what was this key’s value at time t?

The design:

map[key] → append-only list of (timestamp, value). Timestamps arrive strictly increasing, so each list is born sorted — set is O(1) and get is a binary search.

Focus on recognizing:

“Value at timestamp T” = per-key sorted version list + floor search

Core Template

Watch two sets build a version list for key "a", then three gets resolve at different times — including one before any version exists. Press ▶ to animate.

Time-Based Key-Value Store

get(key, t) returns the value set at the largest timestamp ≤ t.

Each key maps to a list of (timestamp, value), appended in increasing time order. get binary-searches for the latest timestamp ≤ t and returns its value, or "" if none. Set is O(1) append, get is O(log k).

TIMELINE VISUALIZER

Steps –

key = a

(1, 1)

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        set(k, v, t): append (t, v) to map[k] — timestamps strictly increase
                      
                        2
                        get(k, t): binary search map[k] for largest timestamp ≤ t
                      
                        3
                                    found → its value;  none → ""

class TimeMap {
    private record Version(int ts, String val) {}
    private final Map<String, List<Version>> store = new HashMap<>();

    public void set(String key, String value, int timestamp) {
        store.computeIfAbsent(key, k -> new ArrayList<>())
             .add(new Version(timestamp, value));
    }

    public String get(String key, int timestamp) {
        List<Version> versions = store.get(key);
        if (versions == null) return "";

        int lo = 0, hi = versions.size() - 1;
        String best = "";

        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (versions.get(mid).ts() <= timestamp) {
                best = versions.get(mid).val();   // candidate
                lo = mid + 1;                     // try later ones
            } else {
                hi = mid - 1;
            }
        }
        return best;
    }
}

from bisect import bisect_right

class TimeMap:
    def __init__(self):
        self.store = {}   # key -> ([timestamps], [values])

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store:
            self.store[key] = ([], [])
        ts, vs = self.store[key]
        ts.append(timestamp)
        vs.append(value)

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return ""
        ts, vs = self.store[key]
        i = bisect_right(ts, timestamp) - 1   # latest ≤ timestamp
        return vs[i] if i >= 0 else ""

class TimeMap {
    unordered_map<string, vector<pair<int, string>>> store;

public:
    void set(string key, string value, int timestamp) {
        store[key].push_back({timestamp, value});
    }

    string get(string key, int timestamp) {
        auto& versions = store[key];
        string best = "";
        int lo = 0, hi = (int)versions.size() - 1;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (versions[mid].first <= timestamp) {
                best = versions[mid].second;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return best;
    }
};

class TimeMap {
  constructor() {
    this.store = new Map(); // key -> [[ts, val], ...]
  }

  set(key, value, timestamp) {
    if (!this.store.has(key)) this.store.set(key, []);
    this.store.get(key).push([timestamp, value]);
  }

  get(key, timestamp) {
    const versions = this.store.get(key);
    if (!versions) return "";

    let lo = 0,
      hi = versions.length - 1,
      best = "";

    while (lo <= hi) {
      const mid = (lo + hi) >> 1;
      if (versions[mid][0] <= timestamp) {
        best = versions[mid][1];
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }
    return best;
  }
}

The search finds the floor — largest timestamp ≤ t — not an exact match.

Why Append-Only Works

The problem guarantees timestamps are strictly increasing. That means:

No sorting ever needed — appends keep lists sorted.
Binary search is valid on every get.
If timestamps could arrive out of order, you’d need to sort/insert in the middle and lose O(1) sets.

Increasing timestamps = free sorted list = O(1) set + O(log n) floor query.

Common Mistakes

Exact-match search.

get(key, t) must return the value at the LATEST time ≤ t, not fail when t isn’t an exact stored timestamp.

Forgetting the empty result.

No version at or before t → return "", not crash or the newest value.

Storing one value per key.

Overwriting kills history. Every set appends a new version.

Complexity

Operation	Time
set	O(1)
get	O(log n)
Space	O(total versions)

⚠️ Animation & Content Notice

Time-Based Key-Value Store

Core Template

⚠️ Animation & Content Notice

Time-Based Key-Value Store

Why Append-Only Works

Common Mistakes

Complexity

Premium Content

My Private Notes

Earn Premium with Referrals

Core Template

Time-Based Key-Value Store

Why Append-Only Works

Common Mistakes

Complexity

Premium Content

My Private Notes