If you have an SQL table with a couple of indices, you have B-tree with random inserts/updates. For truly random data such as scale free graphs, B-tree shows q

If you have an SQL table with a couple of indices, you have B-tree with random inserts/updates. For truly random data such as scale free graphs, B-tree shows quite non-linear performance decline, as if somehow it started to have O(N^2) operation cost instead of O(NlogN). LSM, on the other hand, worked very well there.