Log-structured-merge trees are that; they are not a functional data structure in memory, but on disk they are. For those who don't know about this, here's how

Log-structured-merge trees are that; they are not a functional data structure in memory, but on disk they are. For those who don't know about this, here's how it works: Construct a b-tree in memory ('level 0'). When it reaches a certain size, move it to disk (to L1, level 1) in a compact fashion (by building the tree from the leaf up. There is no need to keep spare space at any L1 node because it is a functional data structure, and won't be directly mutated. The L0-tree in RAM can now be scrapped, and built up from scratch with more insertions. Again, when it exceeds a threshold, the in-memory L0-tree and the on-disk L1 tree from earlier are merged to create a new L1 tree. This goes on until the L1 tree has grown beyond a level-1 threshold size (some k times the L0 size), at which point, the L1 tree is pushed into L2. And so on. L0 is in RAM, L1 and others are on disk. Lookups are more expensive because multiple trees may have to be consulted, but with a judicious use of multiple cores and bloom filters, that cost can be recouped. This avoidance of in-place mutations works esp. well with SSDs and other copy-on-write systems.