Well, there is already a lot of thought that goes into LSM trees on flash storage - check out RocksDB [0] for example, which goes to great lengths to allow the

Well, there is already a lot of thought that goes into LSM trees on flash storage - check out RocksDB [0] for example, which goes to great lengths to allow the user to deal with Read / Write amplification, a problem specific to flash storage. So I don't think that more SSD adoption will fundamentally change anything. The tradeoff from LSM tree to B-tree, very generally speaking, is more about access patterns: LSM trees lend themselves to insert-heavy workloads because the structure is conceptually just a big array that you very quickly append stuff to the end of without checking the rest of the array. That's the magic of why it's so fast for insertions - there's no overhead. You just ignore the older key/values. When doing a read, you read backwards from the end, reading only the newest values. When you fill your memory budget, you flush your array to a lower layer, removing the duplicate old values. I encourage everyone to read the paper - it's not that arcane, just skip the difficult bits [1]. (nb: the original uses trees at each layer, but people have moved away from that for various reasons of changing hardware, scale, use cases) Another point is that oftentimes these data structures span storage layers (or the "cache hierarchy" as database systems people like calling it) - e.g. you could have an LSM tree that has a top layer fitting in L3, then a bunch more in memory, then the majority of it spilling over to disk. Another example is the Bw-Tree [2], which introduces a mapping table that is a storage-agnostic lookup table that tells you wherever a record is, disk or memory or otherwise, and is smart about paging stuff in and out of memory based on hotness. So is this really one "data structure"? Is it a combo of many? Could we change each layer based on the storage type? It gets confusing. When you squint, a lot of data structures start looking like each other, except for certain details that form the fundamental characteristics. Figure 4 in the Monkey paper [3] is one of my favourite figures ever - their observation is that there is a tradeoff continuum of read and lookup costs, and on one end of that continuum is logs (very easy to append to, hard to find things without searching the whole thing), the other end is a sorted array (very easy to find things with binary search, very hard to append to). This is already pretty cool, but then in the middle are tiered and layered LSM trees. And you can actually tweak the level of tiering and layering to reap the benefits of that tradeoff. Then when you start thinking about how big you want your layers to be, how you want to connect them, etc, you eventually arrive to binary trees, btrees, etc. It's sort of magical how related all the storage structures are. [0] https://github.com/facebook/rocksdb/wiki/rocksdb-basics https://github.com/facebook/rocksdb/wiki/rocksdb-basics [1] https://blog.acolyer.org/2014/11/26/the-log-structured-merge-tree-lsm-tree/ https://blog.acolyer.org/2014/11/26/the-log-structured-merge... [2] https://pdfs.semanticscholar.org/7655/9c6cc259c6ab5baf7bd19dd54bb6c773736a.pdf https://pdfs.semanticscholar.org/7655/9c6cc259c6ab5baf7bd19d... [3] https://stratos.seas.harvard.edu/files/stratos/files/monkeykeyvaluestore.pdf https://stratos.seas.harvard.edu/files/stratos/files/monkeyk...