Time-based key-value store

The query is two-dimensional: find a key, then find the newest version whose timestamp is not after the requested time.

Ownership model

• A hash map owns key → version history.
• Each history is a timestamp-sorted dynamic array.
• Binary search owns “last timestamp ≤ query.”

When timestamps arrive in strictly increasing order for each key, insertion is append-only and needs no tree.

Invariant: every key's history is strictly increasing by timestamp.

Query contract

Use upper_bound(query_timestamp) - 1:

• exact timestamps are included;
• a query between versions returns the earlier one;
• a query before the first version returns no value.

flowchart LR
  accTitle: Time map uses per-key predecessor search
  accDescr: For a key with versions at timestamps two, five, and nine, a query at six advances to the first timestamp greater than six, steps back to five, and returns that version.
  M["Hash map lookup<br/>key → one sorted history"] --> H["History<br/>(2,A) → (5,B) → (9,C)"]
  H --> Q["get(key, 6)"]
  Q --> U["upper_bound points to<br/>timestamp 9"]
  U --> P["Step back to<br/>timestamp 5"]
  P --> R["Return B"]
  H --> N["Query before timestamp 2<br/>has no predecessor"]

Separate the two searches mentally: the hash table chooses the history, then binary search chooses the visible version inside that history.

Tested templates

PythonC++17C++11

class TimeMap:
    """Map each key to an append-only timestamp history."""

    def __init__(self) -> None:
        self.history: dict[str, list[tuple[int, str]]] = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        entries = self.history.setdefault(key, [])
        if entries and timestamp <= entries[-1][0]:
            raise ValueError("timestamps for one key must strictly increase")
        # Increasing timestamps keep the history sorted without extra work.
        entries.append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        entries = self.history.get(key, [])
        # upper_bound(timestamp) - 1 is the newest value not after the query.
        index = bisect_right(entries, timestamp, key=lambda entry: entry[0]) - 1
        return entries[index][1] if index >= 0 else ""

class TimeMap {
 public:
  void set(const std::string& key, std::string value, int timestamp) {
    auto& entries = history_[key];
    if (!entries.empty() && timestamp <= entries.back().first) {
      throw std::invalid_argument(
          "timestamps for one key must strictly increase");
    }
    // Increasing timestamps keep the history sorted without extra work.
    entries.push_back({timestamp, std::move(value)});
  }

  std::string get(const std::string& key, int timestamp) const {
    const auto found = history_.find(key);
    if (found == history_.end()) {
      return "";
    }
    const auto& entries = found->second;
    // upper_bound(timestamp) - 1 is the newest value not after the query.
    const auto after = std::upper_bound(
        entries.begin(), entries.end(), timestamp,
        [](int query, const std::pair<int, std::string>& entry) {
          return query < entry.first;
        });
    return after == entries.begin() ? "" : std::prev(after)->second;
  }

 private:
  std::unordered_map<std::string, std::vector<std::pair<int, std::string>>>
      history_;
};

class TimeMap {
 public:
  void set(const std::string& key, std::string value, int timestamp) {
    auto& entries = history_[key];
    if (!entries.empty() && timestamp <= entries.back().first) {
      throw std::invalid_argument(
          "timestamps for one key must strictly increase");
    }
    // Increasing timestamps keep the history sorted without extra work.
    entries.push_back({timestamp, std::move(value)});
  }

  std::string get(const std::string& key, int timestamp) const {
    const auto found = history_.find(key);
    if (found == history_.end()) {
      return "";
    }
    const auto& entries = found->second;
    // upper_bound(timestamp) - 1 is the newest value not after the query.
    const auto after = std::upper_bound(
        entries.begin(), entries.end(), timestamp,
        [](int query, const std::pair<int, std::string>& entry) {
          return query < entry.first;
        });
    return after == entries.begin() ? "" : std::prev(after)->second;
  }

 private:
  std::unordered_map<std::string, std::vector<std::pair<int, std::string>>>
      history_;
};

Complexity and traps

• Set: O(1) amortized under increasing timestamps.
• Get: O(log m) for m versions of that key.
• Do not use map indexing for a read in C++ if a missing key should not be inserted.
• If timestamps can arrive out of order, append-only history is invalid; maintain ordered storage or sort offline.

Practice

LeetCode: Time Based Key-Value Store