(Once more thing I might put in the list of "not a big-O improvement but a rearrangement that made new things possible" is an essentially economic observation Google and others made: once you're planning to serve enough queries/sec, putting unreasonable-sounding quantities of data into expensive storage (like much of your Web search index in RAM) starts to make sense. I saw it referred to as "online data-intensive" at https://perspectives.mvdirona.com/2012/03/power-management-o... and linked papers but don't know if it has a more common name.)