LSMs and fractal trees handle random inserts much better. But you still lose locality of lookups: items generated near each other time-wise are not correlated on disk.