I think people are tainted on Map/Reduce because they see how it is done with other NoSQL DBs like MongoDB where it doesn't store the indexes
Maybe I misunderstand what you mean by stored indexes, but MongoDB supports indexes (http://www.mongodb.org/display/DOCS/Indexes), it just doesn't require them so you can perform exploratory ad-hoc queries when you need to.
I used the wrong term, I apologize. From what I understand MongoDB doesn't store the results from Map/Reduce calculation and treats each query using Map/Reduce separately and on demand. Which means that if you have a large data set, your M/R might be too computationally demanding to run every time.
Where as with CouchDB, every time the view (M/R results) are accessed, it gets incrementally updated and stored. So even complex M/R queries on large datasets will be fast subsequently.
Just some clarification here as comparing MongoDB and CouchDB's Map/Reduce is a bit of "Apples and Oranges" as they are designed for different purposes.
While in CouchDB, all queries are created with Map/Reduce, in MongoDB Map/Reduce is designed for aggregation. There is a separate system for standard querying which performs much better than Map/Reduce (Before people jump on me here my performance comparison is Mongo queries to MONGO Map/Reduce. Not Couch Map/Reduce or Map/Reduce in general; Not looking to get into a benchmark discussion here, just feature clarification).
The two differ greatly---while Couch requires precalculation of "Views", MongoDB focuses on dynamic querying. Given CouchDB's use of Map/Reduce for these static views, the way they do the iterative addition of new data without re-reducing the entire dataset makes sense.
However, MongoDB doesn't require you to use Map/Reduce to run queries and its MapReduce not designed for day to day querying. Rather, one should use MongoDB Map/Reduce for data aggregation tasks.
Also notable is that in 1.8, MongoDB has added some additional functionality for those who are using Map/Reduce which allows you to merge output and build data across jobs. I did a write up on the changes a few weeks ago: http://blog.evilmonkeylabs.com/2011/01/27/MongoDB-1_8-MapRed...
(In the interest of Full Disclosure: I work for 10gen, the company behind MongoDB; I'm also working on a book about MongoDB.)
I think he meant that couchdb keeps stuff on disk (through btrees to be more precise) for the views so that when the corresponding database is updated, the map reduce does not run over the whole dataset, only on the new document.
As far as I know, this does not work on mondodb.
Personally, I simply do not see the point of map reduce for something like couch: the whole point is to be able to parallel jobs on multiple machines so that data do not need to move back and forth through the network. Debugging them is particularly painful, especially if you need to support non programmers (sql is used by many non-programmers people in my experience).
MongoDB uses btree indexes as well, it just doesn't use Map/Reduce for its regular querying like CouchDB does. See my above comment on differences as well as a writeup I did on new output options in MongoDB's M/R system.
The original part in couchdb design is using btree for views to hold temporary data for M/R jobs, as btree are indeed used by mongodb (and most db engines).
The new stuff for M/R in mongodb looks interesting, thanks for the update.
Maybe I misunderstand what you mean by stored indexes, but MongoDB supports indexes (http://www.mongodb.org/display/DOCS/Indexes), it just doesn't require them so you can perform exploratory ad-hoc queries when you need to.