It sounds to me like the poster above restructured the input data to exploit locality of reference better.

http://en.wikipedia.org/wiki/Locality_of_reference

So assuming the data is one one machine (as I asked), why would an index not solve this problem? And why does Map Reduce solve it?

Indexes do not solve the locality problem (see Non-clustered indexes). Even for in-memory databases, it is non-trivial to minimize cache misses in irregular data structures like B-trees.

Now why MapReduce "might" be a better fit for a problem where data fits into one disk. Consider a program which is embarrassingly parallel. It just reads a tuple and writes a new tuple back to disk. The parallel IO provided by map/reduce can offer a significant benefit in this simple case as well.

Also NoSQL != parallel processing.

It's one of the issues, yes. But I wanted to be more general on purpose.

Maybe I misunderstood what you were asking.

Note both MapReduce and NoSQL are overhyped solutions. They are useful in a handful of cases, but often applied to problems they are not as good.

I'm not sure that the two concepts are resulted at all. Obviously mongo has map reduce baked in - but that's not that relevant. Map/reduce is a reasonable paradigm for crunching information. I have a heavily CPU bound system that I parallelise by running on different machines and aggregating that results. I probably wouldn't call it map reduce - but really it's the same thing.

How do you parallelise your long running tasks otherwise?

I can't say without more information on the problem to solve. As I said above, there are cases where MapReduce is a good tool.

And even if you improve the DS/Algorithm first, usually that is usable by the MapReduce port and you save a lot of time/costs.