One enhancement I've toyed with in the past is to have subtrees beneath each leaf node for the historical data for each record. You switch the indexing value to

One enhancement I've toyed with in the past is to have subtrees beneath each leaf node for the historical data for each record. You switch the indexing value to the timestamp of record insertion time or a TX number and keep inserting in append-only fashion. There's some enhancements you can make because the common case is for the key to be a monotonically increasing number, but nothing is strictly necessary. I'd love to build a datalog system on top of something like that at some point, even if it's just for fun.