What you described can be implemented efficiently with B-trees. The problem is, the required operation is low-level and not usually exposed by the database engines. Basically you need to be able to walk the tree, up and down.

Say your table is `[data, timestamp]`, with data sorted ascendingly and timestamp sorted descendingly in the tree, and you want to scan for values for `as_of(T)`. Assume you have found `[data1, T1]` as a valid row. To get the next row, instead of the usual scanning, you seek to the value greater than `[data1, neg_inf]`. Now assume the value you get for the seek is `[data2, T2]`. If `T2 <= T`, then you get a match and can continue with the loop by seeking to `[data2, neg_inf]`, otherwise seek to `[data2, T]` and see what you get.

It is doable in SQLite, but you must use its VM directly, as you cannot do tree-walking with SQL.

Assume you have `M` keys and that for every key you have `N` timestamped data points. The above algorithm cuts down the as-of query time from linear complexity in `N` (`MN log(M)`) to logarithmic complexity in `N` (`M log(MN)`), which I think is the best we can do.