SERVER-8791 SERVER-9165 SERVER-9212 move build into own class, clean up getKeys calls

23 files changed, 463 insertions, 728 deletions

diff --git a/src/mongo/SConscript b/src/mongo/SConscript
index 762eb6b48f3..0f2a25f2f85 100644
--- a/src/mongo/SConscript
+++ b/src/mongo/SConscript
@@ -397,6 +397,7 @@ serverOnlyFiles = [ "db/curop.cpp",
                     "db/index/2d_access_method.cpp",
                     "db/index/2d_index_cursor.cpp",
                     "db/index/btree_access_method.cpp",
+                    "db/index/btree_based_builder.cpp",
                     "db/index/btree_index_cursor.cpp",
                     "db/index/btree_interface.cpp",
                     "db/index/btree_key_generator.cpp",
diff --git a/src/mongo/db/btree.cpp b/src/mongo/db/btree.cpp
index f669bdb142c..7835afa6806 100644
--- a/src/mongo/db/btree.cpp
+++ b/src/mongo/db/btree.cpp
@@ -27,7 +27,6 @@
 #include "mongo/db/db.h"
 #include "mongo/db/dbhelpers.h"
 #include "mongo/db/dur_commitjob.h"
-#include "mongo/db/index_insertion_continuation.h"
 #include "mongo/db/json.h"
 #include "mongo/db/kill_current_op.h"
 #include "mongo/db/pdfile.h"
@@ -1699,52 +1698,6 @@ namespace mongo {
 
     /** @thisLoc disk location of *this */
     template< class V >
-    void BtreeBucket<V>::insertStepOne(DiskLoc thisLoc, 
-                             IndexInsertionContinuationImpl<V>& c,
-                             bool dupsAllowed) const {
-        dassert( c.key.dataSize() <= this->KeyMax );
-        verify( c.key.dataSize() > 0 );
-
-        int pos;
-        bool found = find(c.idx, c.key, c.recordLoc, c.order, pos, !dupsAllowed);
-
-        if ( found ) {
-            const _KeyNode& kn = k(pos);
-            if ( kn.isUnused() ) {
-                LOG(4) << "btree _insert: reusing unused key" << endl;
-                c.b = this;
-                c.pos = pos;
-                c.op = IndexInsertionContinuation::SetUsed;
-                return;
-            }
-
-            DEV {
-                log() << "_insert(): key already exists in index (ok for background:true)\n";
-                log() << "  " << c.idx.indexNamespace() << " thisLoc:" << thisLoc.toString() << '\n';
-                log() << "  " << c.key.toString() << '\n';
-                log() << "  " << "recordLoc:" << c.recordLoc.toString() << " pos:" << pos << endl;
-                log() << "  old l r: " << this->childForPos(pos).toString() << ' ' << this->childForPos(pos+1).toString() << endl;
-            }
-            alreadyInIndex();
-        }
-
-        Loc ch = this->childForPos(pos);
-        DiskLoc child = ch;
-
-        if ( child.isNull() ) {
-            // A this->new key will be inserted at the same tree height as an adjacent existing key.
-            c.bLoc = thisLoc;
-            c.b = this;
-            c.pos = pos;
-            c.op = IndexInsertionContinuation::InsertHere;
-            return;
-        }
-
-        child.btree<V>()->insertStepOne(child, c, dupsAllowed);
-    }
-
-    /** @thisLoc disk location of *this */
-    template< class V >
     int BtreeBucket<V>::_insert(const DiskLoc thisLoc, const DiskLoc recordLoc,
                              const Key& key, const Ordering &order, bool dupsAllowed,
                              const DiskLoc lChild, const DiskLoc rChild, IndexDetails& idx) const {
@@ -1818,18 +1771,6 @@ namespace mongo {
         _log() << "\n" << indent << "  " << hex << this->nextChild.getOfs() << dec << endl;
     }
 
-    template< class V >
-    void BtreeBucket<V>::twoStepInsert(DiskLoc thisLoc, IndexInsertionContinuationImpl<V> &c,
-                                       bool dupsAllowed) const
-    {
-
-        if ( c.key.dataSize() > this->KeyMax ) {
-            problem() << "ERROR: key too large len:" << c.key.dataSize() << " max:" << this->KeyMax << ' ' << c.key.dataSize() << ' ' << c.idx.indexNamespace() << endl;
-            return; // op=Nothing
-        }
-        insertStepOne(thisLoc, c, dupsAllowed);
-    }
-
     /** todo: meaning of return code unclear clean up */
     template< class V >
     int BtreeBucket<V>::bt_insert(const DiskLoc thisLoc, const DiskLoc recordLoc,
@@ -1976,7 +1917,4 @@ namespace mongo {
             }
         }
     } btunittest;
-
-
-    IndexInsertionContinuation::~IndexInsertionContinuation() {}
 }
diff --git a/src/mongo/db/btree.h b/src/mongo/db/btree.h
index 32e0e239ea3..96ac8d3b5f9 100644
--- a/src/mongo/db/btree.h
+++ b/src/mongo/db/btree.h
@@ -588,9 +588,6 @@ namespace mongo {
     };
 
     class IndexDetails;
-    class IndexInsertionContinuation;
-    template< class V>
-    struct IndexInsertionContinuationImpl;
 
     /**
      * This class adds functionality for manipulating buckets that are assembled
@@ -623,7 +620,6 @@ namespace mongo {
     template< class V >
     class BtreeBucket : public BucketBasics<V> {
         friend class BtreeCursor;
-        friend struct IndexInsertionContinuationImpl<V>;
     public:
         // make compiler happy:
         typedef typename V::Key Key;
@@ -700,11 +696,6 @@ namespace mongo {
                       const BSONObj& key, const Ordering &order, bool dupsAllowed,
                       IndexDetails& idx, bool toplevel = true) const;
 
-        /** does the insert in two steps - can then use an upgradable lock for step 1, which 
-            is the part which may have page faults.  also that step is most of the computational work.
-        */
-        void twoStepInsert(DiskLoc thisLoc, IndexInsertionContinuationImpl<V> &c, bool dupsAllowed) const;
-
         /**
          * Preconditions:
          *  - 'key' has a valid schema for this index, and may have objsize() > KeyMax.
@@ -957,9 +948,6 @@ namespace mongo {
                     const Key& key, const Ordering &order, bool dupsAllowed,
                     const DiskLoc lChild, const DiskLoc rChild, IndexDetails &idx) const;
 
-        void insertStepOne(
-                DiskLoc thisLoc, IndexInsertionContinuationImpl<V>& c, bool dupsAllowed) const;
-
         bool find(const IndexDetails& idx, const Key& key, const DiskLoc &recordLoc, const Ordering &order, int& pos, bool assertIfDup) const;        
         static bool customFind( int l, int h, const BSONObj &keyBegin, int keyBeginLen, bool afterKey, const vector< const BSONElement * > &keyEnd, const vector< bool > &keyEndInclusive, const Ordering &order, int direction, DiskLoc &thisLoc, int &keyOfs, pair< DiskLoc, int > &bestParent ) ;
         static void findLargestKey(const DiskLoc& thisLoc, DiskLoc& largestLoc, int& largestKey);
diff --git a/src/mongo/db/cloner.cpp b/src/mongo/db/cloner.cpp
index 2dbacd03ddc..11a3939220c 100644
--- a/src/mongo/db/cloner.cpp
+++ b/src/mongo/db/cloner.cpp
@@ -33,7 +33,6 @@
 #include "mongo/db/namespacestring.h"
 #include "mongo/db/repl/oplog.h"
 #include "mongo/db/pdfile.h"
-#include "mongo/db/sort_phase_one.h"
 
 namespace mongo {
 
@@ -98,7 +97,7 @@ namespace mongo {
     Cloner::Cloner() { }
 
     struct Cloner::Fun {
-        Fun() : lastLog(0), _sortersForIndex(NULL) { }
+        Fun() : lastLog(0) { }
         time_t lastLog;
         void operator()( DBClientCursorBatchIterator &i ) {
             Lock::GlobalWrite lk;
@@ -148,18 +147,8 @@ namespace mongo {
                 }
 
                 try {
-                    // add keys for presorting
                     DiskLoc loc = theDataFileMgr.insertWithObjMod(to_collection, js);
                     loc.assertOk();
-                    if (_sortersForIndex != NULL) {
-                        // add key to SortersForNS
-                        for (SortersForIndex::iterator iSorter = _sortersForIndex->begin();
-                             iSorter != _sortersForIndex->end();
-                             ++iSorter) {
-                            iSorter->second.preSortPhase.addKeys(iSorter->second.spec, js,
-                                                                 loc, false);
-                        }
-                    }
                     if ( logForRepl )
                         logOp("i", to_collection, js);
 
@@ -186,7 +175,6 @@ namespace mongo {
         Client::Context *context;
         bool _mayYield;
         bool _mayBeInterrupted;
-        SortersForIndex *_sortersForIndex;  // sorters that build index keys during query
     };
 
     /* copy the specified collection
@@ -210,12 +198,6 @@ namespace mongo {
         f._mayYield = mayYield;
         f._mayBeInterrupted = mayBeInterrupted;
 
-        if (!isindex) {
-            SortersForNS::iterator it = _sortersForNS.find(to_collection);
-            if (it != _sortersForNS.end())
-                f._sortersForIndex = &it->second;
-        }
-
         int options = QueryOption_NoCursorTimeout | ( slaveOk ? QueryOption_SlaveOk : 0 );
         {
             f.context = cc().getContext();
@@ -232,14 +214,6 @@ namespace mongo {
                 BSONObj js = *i;
                 scoped_lock precalcLock(theDataFileMgr._precalcedMutex);
                 try {
-                    // set the 'precalculated' index data and add the index
-                    SortersForNS::iterator sortIter = _sortersForNS.find(js["ns"].String());
-                    if (sortIter != _sortersForNS.end()) {
-                        SortersForIndex::iterator it = sortIter->second.find(js["name"].String());
-                        if (it != sortIter->second.end()) {
-                            theDataFileMgr.setPrecalced(&it->second.preSortPhase);
-                        }
-                    }
                     theDataFileMgr.insertWithObjMod(to_collection, js);
                     theDataFileMgr.setPrecalced(NULL);
 
@@ -395,34 +369,6 @@ namespace mongo {
             mayInterrupt( opts.mayBeInterrupted );
             dbtempreleaseif r( opts.mayYield );
 
-#if 0
-            // fetch index info
-            auto_ptr<DBClientCursor> cur = _conn->query(idxns.c_str(), BSONObj(), 0, 0, 0,
-                                                       opts.slaveOk ? QueryOption_SlaveOk : 0 );
-            if (!validateQueryResults(cur, errCode, errmsg)) {
-                errmsg = "index query on ns " + ns + " failed: " + errmsg;
-                return false;
-            }
-            while(cur->more()) {
-                BSONObj idxEntry = cur->next();
-                massert(16536, "sync source has invalid index data",
-                               idxEntry.hasField("key") &&
-                               idxEntry.hasField("ns") &&
-                               idxEntry.hasField("name"));
-
-                // validate index version (similar to fixIndexVersion())
-                SortPhaseOne initialSort;
-                IndexInterface* interface = &IndexInterface::defaultVersion();
-
-                // initialize sorter for this index
-                PreSortDetails details;
-                details.preSortPhase.sorter.reset(
-                            new BSONObjExternalSorter(*interface,idxEntry["key"].Obj().copy()));
-                details.spec = IndexSpec(idxEntry["key"].Obj().copy(), idxEntry.copy());
-                _sortersForNS[idxEntry["ns"].String()].insert(make_pair(idxEntry["name"].String(),
-                                                                        details));
-            }
-#endif
             // just using exhaust for collection copying right now
             
             // todo: if snapshot (bool param to this func) is true, we need to snapshot this query?
diff --git a/src/mongo/db/cloner.h b/src/mongo/db/cloner.h
index de437ea3c6a..813725e38bb 100644
--- a/src/mongo/db/cloner.h
+++ b/src/mongo/db/cloner.h
@@ -19,7 +19,6 @@
 #pragma once
 
 #include "mongo/db/jsobj.h"
-#include "mongo/db/sort_phase_one.h"
 
 namespace mongo {
 
@@ -94,18 +93,8 @@ namespace mongo {
                   bool masterSameProcess, bool slaveOk, bool mayYield, bool mayBeInterrupted,
                   Query q);
 
-        // index presort info
-        typedef struct {
-            IndexSpec spec;
-            SortPhaseOne preSortPhase;
-        } PreSortDetails;
-
-        typedef map<string, PreSortDetails> SortersForIndex; // map from index name to presorter
-        typedef map<string, SortersForIndex> SortersForNS;   // map from ns to indices/sorters
-
         struct Fun;
         auto_ptr<DBClientBase> _conn;
-        SortersForNS _sortersForNS;
     };
 
     struct CloneOptions {
diff --git a/src/mongo/db/compact.cpp b/src/mongo/db/compact.cpp
index 86e5e3f5598..fc3d321d34a 100644
--- a/src/mongo/db/compact.cpp
+++ b/src/mongo/db/compact.cpp
@@ -38,7 +38,6 @@
 #include "mongo/db/jsobj.h"
 #include "mongo/db/kill_current_op.h"
 #include "mongo/db/pdfile.h"
-#include "mongo/db/sort_phase_one.h"
 #include "mongo/util/concurrency/task.h"
 #include "mongo/util/timer.h"
 #include "mongo/util/touch_pages.h"
@@ -60,10 +59,8 @@ namespace mongo {
 
     /** @return number of skipped (invalid) documents */
     unsigned compactExtent(const char *ns, NamespaceDetails *d, const DiskLoc diskloc, int n,
-                const scoped_array<IndexSpec> &indexSpecs,
-                scoped_array<SortPhaseOne>& phase1, int nidx, bool validate, 
-                double pf, int pb)
-    {
+                           int nidx, bool validate, double pf, int pb) {
+
         log() << "compact begin extent #" << n << " for namespace " << ns << endl;
         unsigned oldObjSize = 0; // we'll report what the old padding was
         unsigned oldObjSizeWithPadding = 0;
@@ -125,13 +122,6 @@ namespace mongo {
                         recNew = (Record *) getDur().writingPtr(recNew, lenWHdr);
                         addRecordToRecListInExtent(recNew, loc);
                         memcpy(recNew->data(), objOld.objdata(), sz);
-
-                        {
-                            // extract keys for all indexes we will be rebuilding
-                            for( int x = 0; x < nidx; x++ ) { 
-                                phase1[x].addKeys(indexSpecs[x], objOld, loc, false);
-                            }
-                        }
                     }
                     else { 
                         if( ++skipped <= 10 )
@@ -203,8 +193,7 @@ namespace mongo {
         NamespaceDetailsTransient::get(ns).clearQueryCache();
 
         int nidx = d->nIndexes;
-        scoped_array<IndexSpec> indexSpecs( new IndexSpec[nidx] );
-        scoped_array<SortPhaseOne> phase1( new SortPhaseOne[nidx] );
+        scoped_array<BSONObj> indexSpecs( new BSONObj[nidx] );
         {
             NamespaceDetails::IndexIterator ii = d->ii(); 
             // For each existing index...
@@ -226,17 +215,7 @@ namespace mongo {
                     // Pass the element through to the new index spec.
                     b.append(e);
                 }
-                // Add the new index spec to 'indexSpecs'.
-                BSONObj o = b.obj().getOwned();
-                indexSpecs[idxNo].reset(o);
-                // Create an external sorter.
-                phase1[idxNo].sorter.reset
-                        ( new BSONObjExternalSorter
-                           // Use the default index interface, since the new index will be created
-                           // with the default index version.
-                         ( IndexInterface::defaultVersion(),
-                           o.getObjectField("key") ) );
-                phase1[idxNo].sorter->hintNumObjects( d->stats.nrecords );
+                indexSpecs[idxNo] = b.obj().getOwned();
             }
         }
 
@@ -245,8 +224,6 @@ namespace mongo {
             d->deletedList[i].writing().Null();
         }
 
-
-
         // Start over from scratch with our extent sizing and growth
         d->lastExtentSize=0;
 
@@ -276,7 +253,7 @@ namespace mongo {
         }
 
         for( list<DiskLoc>::iterator i = extents.begin(); i != extents.end(); i++ ) { 
-            skipped += compactExtent(ns, d, *i, n++, indexSpecs, phase1, nidx, validate, pf, pb);
+            skipped += compactExtent(ns, d, *i, n++, nidx, validate, pf, pb);
             pm.hit();
         }
 
@@ -294,18 +271,9 @@ namespace mongo {
         string si = s.db + ".system.indexes";
         for( int i = 0; i < nidx; i++ ) {
             killCurrentOp.checkForInterrupt(false);
-            BSONObj info = indexSpecs[i].info;
+            BSONObj info = indexSpecs[i];
             log() << "compact create index " << info["key"].Obj().toString() << endl;
-            scoped_lock precalcLock(theDataFileMgr._precalcedMutex);
-            try {
-                theDataFileMgr.setPrecalced(&phase1[i]);
-                theDataFileMgr.insert(si.c_str(), info.objdata(), info.objsize());
-            }
-            catch(...) {
-                theDataFileMgr.setPrecalced(NULL);
-                throw;
-            }
-            theDataFileMgr.setPrecalced(NULL);
+            theDataFileMgr.insert(si.c_str(), info.objdata(), info.objsize());
         }
 
         return true;
diff --git a/src/mongo/db/index.cpp b/src/mongo/db/index.cpp
index 82944bd188d..bcec35239b2 100644
--- a/src/mongo/db/index.cpp
+++ b/src/mongo/db/index.cpp
@@ -38,27 +38,10 @@
 
 namespace mongo {
 
-    IndexInterface::IndexInserter::IndexInserter() {}
-    IndexInterface::IndexInserter::~IndexInserter() {
-        for (size_t i = 0; i < _continuations.size(); ++i)
-            delete _continuations[i];
-    }
-
-    void IndexInterface::IndexInserter::addInsertionContinuation(IndexInsertionContinuation *c) {
-        _continuations.push_back(c);
-    }
-
-    void IndexInterface::IndexInserter::finishAllInsertions() {
-        for (size_t i = 0; i < _continuations.size(); ++i) {
-            _continuations[i]->doIndexInsertionWrites();
-        }
-    }
-
     IndexInterface& IndexInterface::defaultVersion() {
         return *IndexDetails::iis[ DefaultIndexVersionNumber ];
     }
 
-
     template< class V >
     class IndexInterfaceImpl : public IndexInterface { 
     public:
@@ -66,20 +49,6 @@ namespace mongo {
         virtual int keyCompare(const BSONObj& l,const BSONObj& r, const Ordering &ordering);
 
     public:
-        IndexInsertionContinuation *beginInsertIntoIndex(
-                int idxNo, IndexDetails &_idx,
-                DiskLoc _recordLoc, const BSONObj &_key,
-                const Ordering& _order, bool dupsAllowed) {
-
-            IndexInsertionContinuationImpl<V> *continuation = new IndexInsertionContinuationImpl<V>(
-                    _idx.head, _recordLoc, _key, _order, _idx);
-            ScopeGuard allocGuard = MakeGuard(boost::checked_delete<IndexInsertionContinuation>,
-                                              continuation);
-            _idx.head.btree<V>()->twoStepInsert(_idx.head, *continuation, dupsAllowed);
-            allocGuard.Dismiss();
-            return continuation;
-        }
-
         virtual long long fullValidate(const DiskLoc& thisLoc, const BSONObj &order) { 
             return thisLoc.btree<V>()->fullValidate(thisLoc, order);
         }
@@ -229,28 +198,6 @@ namespace mongo {
         }
     }
 
-    void IndexDetails::getKeysFromObject( const BSONObj& obj, BSONObjSet& keys) const {
-        getSpec().getKeys( obj, keys );
-    }
-
-    void setDifference(BSONObjSet &l, BSONObjSet &r, vector<BSONObj*> &diff) {
-        // l and r must use the same ordering spec.
-        verify( l.key_comp().order() == r.key_comp().order() );
-        BSONObjSet::iterator i = l.begin();
-        BSONObjSet::iterator j = r.begin();
-        while ( 1 ) {
-            if ( i == l.end() )
-                break;
-            while ( j != r.end() && j->woCompare( *i ) < 0 )
-                j++;
-            if ( j == r.end() || i->woCompare(*j) != 0  ) {
-                const BSONObj *jo = &*i;
-                diff.push_back( (BSONObj *) jo );
-            }
-            i++;
-        }
-    }
-
     // should be { <something> : <simpletype[1|-1]>, .keyp.. }
     static bool validKeyPattern(BSONObj kp) {
         BSONObjIterator i(kp);
diff --git a/src/mongo/db/index.h b/src/mongo/db/index.h
index f3fd904a3fd..c6184e0920c 100644
--- a/src/mongo/db/index.h
+++ b/src/mongo/db/index.h
@@ -23,7 +23,6 @@
 #include <vector>
 
 #include "mongo/db/diskloc.h"
-#include "mongo/db/index_insertion_continuation.h"
 #include "mongo/db/indexkey.h"
 #include "mongo/db/jsobj.h"
 #include "mongo/db/key.h"
@@ -35,22 +34,6 @@ namespace mongo {
     protected:
         virtual ~IndexInterface() { }
     public:
-        class IndexInserter : private boost::noncopyable {
-        public:
-            IndexInserter();
-            ~IndexInserter();
-
-            void addInsertionContinuation(IndexInsertionContinuation *c);
-            void finishAllInsertions();
-
-        private:
-            std::vector<IndexInsertionContinuation *> _continuations;
-        };
-
-        virtual IndexInsertionContinuation *beginInsertIntoIndex(
-            int idxNo,
-            IndexDetails &_idx, DiskLoc _recordLoc, const BSONObj &_key,
-            const Ordering& _order, bool dupsAllowed) = 0;
 
         virtual int keyCompare(const BSONObj& l,const BSONObj& r, const Ordering &ordering) = 0;
         virtual long long fullValidate(const DiskLoc& thisLoc, const BSONObj &order) = 0;
@@ -117,13 +100,6 @@ namespace mongo {
             return res;
         }
 
-        /* pull out the relevant key objects from obj, so we
-           can index them.  Note that the set is multiple elements
-           only when it's a "multikey" array.
-           keys will be left empty if key not found in the object.
-        */
-        void getKeysFromObject( const BSONObj& obj, BSONObjSet& keys) const;
-
         /* get the key pattern for this object.
            e.g., { lastname:1, firstname:1 }
         */
diff --git a/src/mongo/db/index/btree_access_method.cpp b/src/mongo/db/index/btree_access_method.cpp
index e04977f7403..788f9b40939 100644
--- a/src/mongo/db/index/btree_access_method.cpp
+++ b/src/mongo/db/index/btree_access_method.cpp
@@ -22,6 +22,7 @@
 #include "mongo/db/index/btree_index_cursor.h"
 #include "mongo/db/index/btree_interface.h"
 #include "mongo/db/jsobj.h"
+#include "mongo/db/keypattern.h"
 #include "mongo/db/pdfile.h"
 #include "mongo/db/pdfile_private.h"
 
@@ -169,8 +170,11 @@ namespace mongo {
         setDifference(data->oldKeys, data->newKeys, &data->removed);
         setDifference(data->newKeys, data->oldKeys, &data->added);
 
-        // Check for dups.
-        if (!data->added.empty() && _descriptor->unique() && !options.dupsAllowed) {
+        bool checkForDups = !data->added.empty()
+            && (KeyPattern::isIdKeyPattern(_descriptor->keyPattern()) || _descriptor->unique())
+            && !options.dupsAllowed;
+
+        if (checkForDups) {
             for (vector<BSONObj*>::iterator i = data->added.begin(); i != data->added.end(); i++) {
                 if (_interface->wouldCreateDup(_descriptor->getOnDisk(), _descriptor->getHead(),
                                                **i, _ordering, record)) {
diff --git a/src/mongo/db/index/btree_access_method_internal.h b/src/mongo/db/index/btree_access_method_internal.h
index 1a932712949..095aa620fc6 100644
--- a/src/mongo/db/index/btree_access_method_internal.h
+++ b/src/mongo/db/index/btree_access_method_internal.h
@@ -64,8 +64,7 @@ namespace mongo {
 
     protected:
         // Friends who need getKeys.
-        // TODO: uncomment when builder is in.
-        // template <class K> friend class BtreeBasedIndexBuilder;
+        friend class BtreeBasedBuilder;
 
         // See below for body.
         class BtreeBasedPrivateUpdateData;
diff --git a/src/mongo/db/index/btree_based_builder.cpp b/src/mongo/db/index/btree_based_builder.cpp
new file mode 100644
index 00000000000..331d5e45500
--- /dev/null
+++ b/src/mongo/db/index/btree_based_builder.cpp
@@ -0,0 +1,214 @@
+/**
+*    Copyright (C) 2013 10gen Inc.
+*
+*    This program is free software: you can redistribute it and/or  modify
+*    it under the terms of the GNU Affero General Public License, version 3,
+*    as published by the Free Software Foundation.
+*
+*    This program is distributed in the hope that it will be useful,
+*    but WITHOUT ANY WARRANTY; without even the implied warranty of
+*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+*    GNU Affero General Public License for more details.
+*
+*    You should have received a copy of the GNU Affero General Public License
+*    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include "mongo/db/index/btree_based_builder.h"
+
+#include "mongo/db/btreebuilder.h"
+#include "mongo/db/index/catalog_hack.h"
+#include "mongo/db/index/index_descriptor.h"
+#include "mongo/db/index/index_access_method.h"
+#include "mongo/db/kill_current_op.h"
+#include "mongo/db/repl/is_master.h"
+#include "mongo/db/repl/rs.h"
+#include "mongo/db/sort_phase_one.h"
+#include "mongo/util/processinfo.h"
+#include "mongo/db/pdfile_private.h"
+
+namespace mongo {
+
+    template< class V >
+    void buildBottomUpPhases2And3( bool dupsAllowed,
+                                   IndexDetails& idx,
+                                   BSONObjExternalSorter& sorter,
+                                   bool dropDups,
+                                   set<DiskLoc>& dupsToDrop,
+                                   CurOp* op,
+                                   SortPhaseOne* phase1,
+                                   ProgressMeterHolder& pm,
+                                   Timer& t,
+                                   bool mayInterrupt ) {
+        BtreeBuilder<V> btBuilder(dupsAllowed, idx);
+        BSONObj keyLast;
+        auto_ptr<BSONObjExternalSorter::Iterator> i = sorter.iterator();
+        // verifies that pm and op refer to the same ProgressMeter
+        verify(pm == op->setMessage("index: (2/3) btree bottom up",
+                                    "Index: (2/3) BTree Bottom Up Progress",
+                                    phase1->nkeys,
+                                    10));
+        while( i->more() ) {
+            RARELY killCurrentOp.checkForInterrupt( !mayInterrupt );
+            BSONObjExternalSorter::Data d = i->next();
+
+            try {
+                if ( !dupsAllowed && dropDups ) {
+                    LastError::Disabled led( lastError.get() );
+                    btBuilder.addKey(d.first, d.second);
+                }
+                else {
+                    btBuilder.addKey(d.first, d.second);                    
+                }
+            }
+            catch( AssertionException& e ) {
+                if ( dupsAllowed ) {
+                    // unknown exception??
+                    throw;
+                }
+
+                if( e.interrupted() ) {
+                    killCurrentOp.checkForInterrupt();
+                }
+
+                if ( ! dropDups )
+                    throw;
+
+                /* we could queue these on disk, but normally there are very few dups, so instead we
+                    keep in ram and have a limit.
+                */
+                dupsToDrop.insert(d.second);
+                uassert( 10092 , "too may dups on index build with dropDups=true", dupsToDrop.size() < 1000000 );
+            }
+            pm.hit();
+        }
+        pm.finished();
+        op->setMessage("index: (3/3) btree-middle", "Index: (3/3) BTree Middle Progress");
+        LOG(t.seconds() > 10 ? 0 : 1 ) << "\t done building bottom layer, going to commit" << endl;
+        btBuilder.commit( mayInterrupt );
+        if ( btBuilder.getn() != phase1->nkeys && ! dropDups ) {
+            warning() << "not all entries were added to the index, probably some keys were too large" << endl;
+        }
+    }
+
+    void BtreeBasedBuilder::addKeysToPhaseOne(NamespaceDetails* d, const char* ns,
+                           const IndexDetails& idx,
+                           const BSONObj& order,
+                           SortPhaseOne* phaseOne,
+                           int64_t nrecords,
+                           ProgressMeter* progressMeter,
+                           bool mayInterrupt, int idxNo) {
+        shared_ptr<Cursor> cursor = theDataFileMgr.findAll( ns );
+        phaseOne->sorter.reset( new BSONObjExternalSorter( idx.idxInterface(), order ) );
+        phaseOne->sorter->hintNumObjects( nrecords );
+        auto_ptr<IndexDescriptor> desc(CatalogHack::getDescriptor(d, idxNo));
+        auto_ptr<BtreeBasedAccessMethod> iam(CatalogHack::getBtreeBasedIndex(desc.get()));
+        while ( cursor->ok() ) {
+            RARELY killCurrentOp.checkForInterrupt( !mayInterrupt );
+            BSONObj o = cursor->current();
+            DiskLoc loc = cursor->currLoc();
+            BSONObjSet keys;
+            iam->getKeys(o, &keys);
+            phaseOne->addKeys(keys, loc, mayInterrupt);
+            cursor->advance();
+            progressMeter->hit();
+            if ( logLevel > 1 && phaseOne->n % 10000 == 0 ) {
+                printMemInfo( "\t iterating objects" );
+            }
+        }
+    }
+
+    uint64_t BtreeBasedBuilder::fastBuildIndex(const char* ns, NamespaceDetails* d,
+                                               IndexDetails& idx, bool mayInterrupt,
+                                               int idxNo) {
+        CurOp * op = cc().curop();
+
+        Timer t;
+
+        tlog(1) << "fastBuildIndex " << ns << ' ' << idx.info.obj().toString() << endl;
+
+        bool dupsAllowed = !idx.unique() || ignoreUniqueIndex(idx);
+        bool dropDups = idx.dropDups() || inDBRepair;
+        BSONObj order = idx.keyPattern();
+
+        getDur().writingDiskLoc(idx.head).Null();
+
+        if ( logLevel > 1 ) printMemInfo( "before index start" );
+
+        /* get and sort all the keys ----- */
+        ProgressMeterHolder pm(op->setMessage("index: (1/3) external sort",
+                                              "Index: (1/3) External Sort Progress",
+                                              d->stats.nrecords,
+                                              10));
+        SortPhaseOne phase1;
+        addKeysToPhaseOne(d, ns, idx, order, &phase1, d->stats.nrecords, pm.get(),
+                          mayInterrupt, idxNo );
+        pm.finished();
+
+        BSONObjExternalSorter& sorter = *(phase1.sorter);
+        // Ensure the index and external sorter have a consistent index interface (and sort order).
+        fassert( 16408, &idx.idxInterface() == &sorter.getIndexInterface() );
+
+        if( phase1.multi ) {
+            d->setIndexIsMultikey(ns, idxNo);
+        }
+
+        if ( logLevel > 1 ) printMemInfo( "before final sort" );
+        phase1.sorter->sort( mayInterrupt );
+        if ( logLevel > 1 ) printMemInfo( "after final sort" );
+
+        LOG(t.seconds() > 5 ? 0 : 1) << "\t external sort used : " << sorter.numFiles() << " files " << " in " << t.seconds() << " secs" << endl;
+
+        set<DiskLoc> dupsToDrop;
+
+        /* build index --- */
+        if( idx.version() == 0 )
+            buildBottomUpPhases2And3<V0>(dupsAllowed,
+                                         idx,
+                                         sorter,
+                                         dropDups,
+                                         dupsToDrop,
+                                         op,
+                                         &phase1,
+                                         pm,
+                                         t,
+                                         mayInterrupt);
+        else if( idx.version() == 1 ) 
+            buildBottomUpPhases2And3<V1>(dupsAllowed,
+                                         idx,
+                                         sorter,
+                                         dropDups,
+                                         dupsToDrop,
+                                         op,
+                                         &phase1,
+                                         pm,
+                                         t,
+                                         mayInterrupt);
+        else
+            verify(false);
+
+        if( dropDups ) 
+            log() << "\t fastBuildIndex dupsToDrop:" << dupsToDrop.size() << endl;
+
+        BtreeBasedBuilder::doDropDups(ns, d, dupsToDrop, mayInterrupt);
+
+        return phase1.n;
+    }
+
+    void BtreeBasedBuilder::doDropDups(const char* ns, NamespaceDetails* d,
+                                       const set<DiskLoc>& dupsToDrop, bool mayInterrupt) {
+
+        for( set<DiskLoc>::const_iterator i = dupsToDrop.begin(); i != dupsToDrop.end(); ++i ) {
+            RARELY killCurrentOp.checkForInterrupt( !mayInterrupt );
+            theDataFileMgr.deleteRecord( d,
+                                         ns,
+                                         i->rec(),
+                                         *i,
+                                         false /* cappedOk */,
+                                         true /* noWarn */,
+                                         isMaster( ns ) /* logOp */ );
+            getDur().commitIfNeeded();
+        }
+    }
+
+}  // namespace mongo
diff --git a/src/mongo/db/index/btree_based_builder.h b/src/mongo/db/index/btree_based_builder.h
new file mode 100644
index 00000000000..4f9c35fb1a1
--- /dev/null
+++ b/src/mongo/db/index/btree_based_builder.h
@@ -0,0 +1,75 @@
+/**
+*    Copyright (C) 2013 10gen Inc.
+*
+*    This program is free software: you can redistribute it and/or  modify
+*    it under the terms of the GNU Affero General Public License, version 3,
+*    as published by the Free Software Foundation.
+*
+*    This program is distributed in the hope that it will be useful,
+*    but WITHOUT ANY WARRANTY; without even the implied warranty of
+*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+*    GNU Affero General Public License for more details.
+*
+*    You should have received a copy of the GNU Affero General Public License
+*    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#pragma once
+
+#include <set>
+
+#include "mongo/db/jsobj.h"
+#include "mongo/db/pdfile.h"
+
+namespace IndexUpdateTests {
+    class AddKeysToPhaseOne;
+    class InterruptAddKeysToPhaseOne;
+    class DoDropDups;
+    class InterruptDoDropDups;
+}
+
+namespace mongo {
+
+    class BSONObjExternalSorter;
+    class IndexDetails;
+    class NamespaceDetails;
+    class ProgressMeter;
+    class ProgressMeterHolder;
+    class SortPhaseOne;
+
+    class BtreeBasedBuilder {
+    public:
+        /**
+         * Want to build an index?  Call this.  Throws DBException.
+         */
+        static uint64_t fastBuildIndex(const char* ns, NamespaceDetails* d, IndexDetails& idx,
+                                       bool mayInterrupt, int idxNo);
+    private:
+        friend class IndexUpdateTests::AddKeysToPhaseOne;
+        friend class IndexUpdateTests::InterruptAddKeysToPhaseOne;
+        friend class IndexUpdateTests::DoDropDups;
+        friend class IndexUpdateTests::InterruptDoDropDups;
+
+        static void addKeysToPhaseOne(NamespaceDetails* d, const char* ns, const IndexDetails& idx,
+                                      const BSONObj& order, SortPhaseOne* phaseOne,
+                                      int64_t nrecords, ProgressMeter* progressMeter, bool mayInterrupt,
+                                      int idxNo);
+
+        static void doDropDups(const char* ns, NamespaceDetails* d, const set<DiskLoc>& dupsToDrop,
+                               bool mayInterrupt );
+    };
+
+    // Exposed for testing purposes.
+    template< class V >
+    void buildBottomUpPhases2And3( bool dupsAllowed,
+                                   IndexDetails& idx,
+                                   BSONObjExternalSorter& sorter,
+                                   bool dropDups,
+                                   set<DiskLoc>& dupsToDrop,
+                                   CurOp* op,
+                                   SortPhaseOne* phase1,
+                                   ProgressMeterHolder& pm,
+                                   Timer& t,
+                                   bool mayInterrupt );
+
+}  // namespace mongo
diff --git a/src/mongo/db/index/catalog_hack.h b/src/mongo/db/index/catalog_hack.h
index 1e306d9b08e..34bf8171075 100644
--- a/src/mongo/db/index/catalog_hack.h
+++ b/src/mongo/db/index/catalog_hack.h
@@ -14,8 +14,11 @@
 *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
 
+#pragma once
+
 #include "mongo/db/index/2d_access_method.h"
 #include "mongo/db/index/btree_access_method.h"
+#include "mongo/db/index/btree_access_method_internal.h"
 #include "mongo/db/index/fts_access_method.h"
 #include "mongo/db/index/hash_access_method.h"
 #include "mongo/db/index/haystack_access_method.h"
@@ -36,6 +39,27 @@ namespace mongo {
             return new IndexDescriptor(nsd, idxNo, &id, id.info.obj());
         }
 
+        static BtreeBasedAccessMethod* getBtreeBasedIndex(IndexDescriptor* desc) {
+            string type = KeyPattern::findPluginName(desc->keyPattern());
+            if ("hashed" == type) {
+                return new HashAccessMethod(desc);
+            } else if ("2dsphere" == type) {
+                return new S2AccessMethod(desc);
+            } else if ("text" == type || "_fts" == type) {
+                return new FTSAccessMethod(desc);
+            } else if ("geoHaystack" == type) {
+                return new HaystackAccessMethod(desc);
+            } else if ("" == type) {
+                return new BtreeAccessMethod(desc);
+            } else if ("2d" == type) {
+                return new TwoDAccessMethod(desc);
+            } else {
+                cout << "Can't find index for keypattern " << desc->keyPattern() << endl;
+                verify(0);
+                return NULL;
+            }
+        }
+
         static IndexAccessMethod* getIndex(IndexDescriptor* desc) {
             string type = KeyPattern::findPluginName(desc->keyPattern());
             if ("hashed" == type) {
diff --git a/src/mongo/db/index_insertion_continuation.h b/src/mongo/db/index_insertion_continuation.h
deleted file mode 100644
index 67493138296..00000000000
--- a/src/mongo/db/index_insertion_continuation.h
+++ /dev/null
@@ -1,70 +0,0 @@
-/**
- *    Copyright (C) 2008 10gen Inc.
- *
- *    This program is free software: you can redistribute it and/or  modify
- *    it under the terms of the GNU Affero General Public License, version 3,
- *    as published by the Free Software Foundation.
- *
- *    This program is distributed in the hope that it will be useful,
- *    but WITHOUT ANY WARRANTY; without even the implied warranty of
- *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- *    GNU Affero General Public License for more details.
- *
- *    You should have received a copy of the GNU Affero General Public License
- *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
- */
-#pragma once
-
-#include "mongo/db/diskloc.h"
-#include "mongo/db/jsobj.h"
-
-namespace mongo {
-
-    class IndexDetails;
-    template <typename V> class BtreeBucket;
-
-    /**
-     * This class represents the write phase of the two-phase index insertion.
-     */
-    class IndexInsertionContinuation : private boost::noncopyable {
-    public:
-        enum Op { Nothing, SetUsed, InsertHere };
-
-        virtual ~IndexInsertionContinuation();
-        virtual void doIndexInsertionWrites() const = 0;
-    };
-
-    template< class V >
-    struct IndexInsertionContinuationImpl : public IndexInsertionContinuation {
-
-        IndexInsertionContinuationImpl(DiskLoc thisLoc, DiskLoc _recordLoc, const BSONObj &_key,
-                                       Ordering _order, IndexDetails& _idx) :
-            bLoc(thisLoc), recordLoc(_recordLoc), key(_key), order(_order), idx(_idx) {
-            op = Nothing;
-        }
-
-        DiskLoc bLoc;
-        DiskLoc recordLoc;
-        typename V::KeyOwned key;
-        const Ordering order;
-        IndexDetails& idx;
-        Op op;
-
-        int pos;
-        const BtreeBucket<V> *b;
-
-        void doIndexInsertionWrites() const {
-            if( op == Nothing )
-                return;
-            else if( op == SetUsed ) {
-                const typename V::_KeyNode& kn = b->k(pos);
-                kn.writing().setUsed();
-            }
-            else {
-                b->insertHere(bLoc, pos, recordLoc, key, order, DiskLoc(), DiskLoc(), idx);
-            }
-        }
-    };
-
-
-}  // namespace mongo
diff --git a/src/mongo/db/index_update.cpp b/src/mongo/db/index_update.cpp
index 5f511b83de6..83f2f86c5c5 100644
--- a/src/mongo/db/index_update.cpp
+++ b/src/mongo/db/index_update.cpp
@@ -22,13 +22,13 @@
 #include "mongo/db/clientcursor.h"
 #include "mongo/db/extsort.h"
 #include "mongo/db/index.h"
+#include "mongo/db/index/btree_based_builder.h"
 #include "mongo/db/index/catalog_hack.h"
 #include "mongo/db/kill_current_op.h"
 #include "mongo/db/namespace_details.h"
 #include "mongo/db/pdfile_private.h"
 #include "mongo/db/repl/is_master.h"
 #include "mongo/db/repl/rs.h"
-#include "mongo/db/sort_phase_one.h"
 #include "mongo/util/processinfo.h"
 #include "mongo/util/startup_test.h"
 
@@ -120,192 +120,6 @@ namespace mongo {
     // Bulk index building
     //
 
-    void addKeysToPhaseOne( const char* ns,
-                            const IndexDetails& idx,
-                            const BSONObj& order,
-                            SortPhaseOne* phaseOne,
-                            int64_t nrecords,
-                            ProgressMeter* progressMeter,
-                            bool mayInterrupt ) {
-        shared_ptr<Cursor> cursor = theDataFileMgr.findAll( ns );
-        phaseOne->sorter.reset( new BSONObjExternalSorter( idx.idxInterface(), order ) );
-        phaseOne->sorter->hintNumObjects( nrecords );
-        const IndexSpec& spec = idx.getSpec();
-        while ( cursor->ok() ) {
-            RARELY killCurrentOp.checkForInterrupt( !mayInterrupt );
-            BSONObj o = cursor->current();
-            DiskLoc loc = cursor->currLoc();
-            phaseOne->addKeys( spec, o, loc, mayInterrupt );
-            cursor->advance();
-            progressMeter->hit();
-            if ( logLevel > 1 && phaseOne->n % 10000 == 0 ) {
-                printMemInfo( "\t iterating objects" );
-            }
-        }
-    }
-
-    template< class V >
-    void buildBottomUpPhases2And3( bool dupsAllowed,
-                                   IndexDetails& idx,
-                                   BSONObjExternalSorter& sorter,
-                                   bool dropDups,
-                                   set<DiskLoc>& dupsToDrop,
-                                   CurOp* op,
-                                   SortPhaseOne* phase1,
-                                   ProgressMeterHolder& pm,
-                                   Timer& t,
-                                   bool mayInterrupt ) {
-        BtreeBuilder<V> btBuilder(dupsAllowed, idx);
-        BSONObj keyLast;
-        auto_ptr<BSONObjExternalSorter::Iterator> i = sorter.iterator();
-        // verifies that pm and op refer to the same ProgressMeter
-        verify(pm == op->setMessage("index: (2/3) btree bottom up",
-                                    "Index: (2/3) BTree Bottom Up Progress",
-                                    phase1->nkeys,
-                                    10));
-        while( i->more() ) {
-            RARELY killCurrentOp.checkForInterrupt( !mayInterrupt );
-            BSONObjExternalSorter::Data d = i->next();
-
-            try {
-                if ( !dupsAllowed && dropDups ) {
-                    LastError::Disabled led( lastError.get() );
-                    btBuilder.addKey(d.first, d.second);
-                }
-                else {
-                    btBuilder.addKey(d.first, d.second);                    
-                }
-            }
-            catch( AssertionException& e ) {
-                if ( dupsAllowed ) {
-                    // unknown exception??
-                    throw;
-                }
-
-                if( e.interrupted() ) {
-                    killCurrentOp.checkForInterrupt();
-                }
-
-                if ( ! dropDups )
-                    throw;
-
-                /* we could queue these on disk, but normally there are very few dups, so instead we
-                    keep in ram and have a limit.
-                */
-                dupsToDrop.insert(d.second);
-                uassert( 10092 , "too may dups on index build with dropDups=true", dupsToDrop.size() < 1000000 );
-            }
-            pm.hit();
-        }
-        pm.finished();
-        op->setMessage("index: (3/3) btree-middle", "Index: (3/3) BTree Middle Progress");
-        LOG(t.seconds() > 10 ? 0 : 1 ) << "\t done building bottom layer, going to commit" << endl;
-        btBuilder.commit( mayInterrupt );
-        if ( btBuilder.getn() != phase1->nkeys && ! dropDups ) {
-            warning() << "not all entries were added to the index, probably some keys were too large" << endl;
-        }
-    }
-
-    void doDropDups( const char* ns,
-                     NamespaceDetails* d,
-                     const set<DiskLoc>& dupsToDrop,
-                     bool mayInterrupt ) {
-        for( set<DiskLoc>::const_iterator i = dupsToDrop.begin(); i != dupsToDrop.end(); ++i ) {
-            RARELY killCurrentOp.checkForInterrupt( !mayInterrupt );
-            theDataFileMgr.deleteRecord( d,
-                                         ns,
-                                         i->rec(),
-                                         *i,
-                                         false /* cappedOk */,
-                                         true /* noWarn */,
-                                         isMaster( ns ) /* logOp */ );
-            getDur().commitIfNeeded();
-        }
-    }
-
-    // throws DBException
-    uint64_t fastBuildIndex(const char* ns,
-                            NamespaceDetails* d,
-                            IndexDetails& idx,
-                            bool mayInterrupt) {
-        CurOp * op = cc().curop();
-
-        Timer t;
-
-        tlog(1) << "fastBuildIndex " << ns << ' ' << idx.info.obj().toString() << endl;
-
-        bool dupsAllowed = !idx.unique() || ignoreUniqueIndex(idx);
-        bool dropDups = idx.dropDups() || inDBRepair;
-        BSONObj order = idx.keyPattern();
-
-        getDur().writingDiskLoc(idx.head).Null();
-
-        if ( logLevel > 1 ) printMemInfo( "before index start" );
-
-        /* get and sort all the keys ----- */
-        ProgressMeterHolder pm(op->setMessage("index: (1/3) external sort",
-                                              "Index: (1/3) External Sort Progress",
-                                              d->stats.nrecords,
-                                              10));
-        SortPhaseOne _ours;
-        SortPhaseOne *phase1 = theDataFileMgr.getPrecalced();
-        if( phase1 == 0 ) {
-            phase1 = &_ours;
-            addKeysToPhaseOne( ns, idx, order, phase1, d->stats.nrecords, pm.get(), mayInterrupt );
-        }
-        pm.finished();
-
-        BSONObjExternalSorter& sorter = *(phase1->sorter);
-        // Ensure the index and external sorter have a consistent index interface (and sort order).
-        fassert( 16408, &idx.idxInterface() == &sorter.getIndexInterface() );
-
-        if( phase1->multi ) {
-            int idxNo = IndexBuildsInProgress::get(ns, idx.info.obj()["name"].valuestr());
-            d->setIndexIsMultikey(ns, idxNo);
-        }
-
-        if ( logLevel > 1 ) printMemInfo( "before final sort" );
-        phase1->sorter->sort( mayInterrupt );
-        if ( logLevel > 1 ) printMemInfo( "after final sort" );
-
-        LOG(t.seconds() > 5 ? 0 : 1) << "\t external sort used : " << sorter.numFiles() << " files " << " in " << t.seconds() << " secs" << endl;
-
-        set<DiskLoc> dupsToDrop;
-
-        /* build index --- */
-        if( idx.version() == 0 )
-            buildBottomUpPhases2And3<V0>(dupsAllowed,
-                                         idx,
-                                         sorter,
-                                         dropDups,
-                                         dupsToDrop,
-                                         op,
-                                         phase1,
-                                         pm,
-                                         t,
-                                         mayInterrupt);
-        else if( idx.version() == 1 ) 
-            buildBottomUpPhases2And3<V1>(dupsAllowed,
-                                         idx,
-                                         sorter,
-                                         dropDups,
-                                         dupsToDrop,
-                                         op,
-                                         phase1,
-                                         pm,
-                                         t,
-                                         mayInterrupt);
-        else
-            verify(false);
-
-        if( dropDups ) 
-            log() << "\t fastBuildIndex dupsToDrop:" << dupsToDrop.size() << endl;
-
-        doDropDups(ns, d, dupsToDrop, mayInterrupt);
-
-        return phase1->n;
-    }
-
     class BackgroundIndexBuildJob : public BackgroundOperation {
 
         unsigned long long addExistingToIndex(const char *ns, NamespaceDetails *d,
@@ -467,11 +281,9 @@ namespace mongo {
 
         verify( Lock::isWriteLocked(ns) );
 
-        // Build index spec here in case the collection is empty and the index details are invalid
-        idx.getSpec();
-
         if( inDBRepair || !background ) {
-            n = fastBuildIndex(ns.c_str(), d, idx, mayInterrupt);
+            int idxNo = IndexBuildsInProgress::get(ns.c_str(), idx.info.obj()["name"].valuestr());
+            n = BtreeBasedBuilder::fastBuildIndex(ns.c_str(), d, idx, mayInterrupt, idxNo);
             verify( !idx.head.isNull() );
         }
         else {
@@ -594,41 +406,6 @@ namespace mongo {
         return true;
     }
 
-    /**
-     * DEPRECATED -- only used by prefetch.cpp
-     *  step one of adding keys to index idxNo for a new record
-     */
-    void fetchIndexInserters(BSONObjSet & /*out*/keys,
-                             IndexInterface::IndexInserter &inserter,
-                             NamespaceDetails *d,
-                             int idxNo,
-                             const BSONObj& obj,
-                             DiskLoc recordLoc,
-                             const bool allowDups) {
-        IndexDetails &idx = d->idx(idxNo);
-        idx.getKeysFromObject(obj, keys);
-        if( keys.empty() )
-            return;
-        bool dupsAllowed = !idx.unique() || allowDups;
-        Ordering ordering = Ordering::make(idx.keyPattern());
-        
-        try {
-            // we can't do the two step method with multi keys as insertion of one key changes the indexes 
-            // structure.  however we can do the first key of the set so we go ahead and do that FWIW
-            inserter.addInsertionContinuation(
-                    idx.idxInterface().beginInsertIntoIndex(
-                            idxNo, idx, recordLoc, *keys.begin(), ordering, dupsAllowed));
-        }
-        catch (AssertionException& e) {
-            if( e.getCode() == 10287 && idxNo >= d->nIndexes ) {
-                DEV log() << "info: caught key already in index on bg indexing (ok)" << endl;
-            }
-            else {
-                throw;
-            }
-        }
-    }
-
     class IndexUpdateTest : public StartupTest {
     public:
         void run() {
diff --git a/src/mongo/db/index_update.h b/src/mongo/db/index_update.h
index e32e028931f..0e4b561c702 100644
--- a/src/mongo/db/index_update.h
+++ b/src/mongo/db/index_update.h
@@ -26,7 +26,8 @@ namespace mongo {
     class Record;
 
     // unindex all keys in index for this record. 
-    void unindexRecord(NamespaceDetails *d, Record *todelete, const DiskLoc& dl, bool noWarn = false);
+    void unindexRecord(NamespaceDetails *d, Record *todelete, const DiskLoc& dl,
+                       bool noWarn = false);
 
     // Build an index in the foreground
     // If background is false, uses fast index builder
@@ -39,16 +40,8 @@ namespace mongo {
     // add index keys for a newly inserted record 
     void indexRecord(const char *ns, NamespaceDetails *d, const BSONObj& obj, const DiskLoc &loc);
 
-    // Given an object, populate "inserter" with information necessary to update indexes.
-    void fetchIndexInserters(BSONObjSet & /*out*/keys,
-                             IndexInterface::IndexInserter &inserter,
-                             NamespaceDetails *d,
-                             int idxNo,
-                             const BSONObj& obj,
-                             DiskLoc recordLoc,
-                             const bool allowDups = false);
-
-    bool dropIndexes( NamespaceDetails *d, const char *ns, const char *name, string &errmsg, BSONObjBuilder &anObjBuilder, bool maydeleteIdIndex );
+    bool dropIndexes(NamespaceDetails *d, const char *ns, const char *name, string &errmsg,
+                     BSONObjBuilder &anObjBuilder, bool maydeleteIdIndex );
 
     /**
      * Add an _id index to namespace @param 'ns' if not already present.
@@ -65,32 +58,4 @@ namespace mongo {
     struct SortPhaseOne;
     class Timer;
 
-    /** Extract index keys from the @param 'ns' to the external sorter in @param 'phaseOne'. */
-    void addKeysToPhaseOne( const char* ns,
-                            const IndexDetails& idx,
-                            const BSONObj& order,
-                            SortPhaseOne* phaseOne,
-                            int64_t nrecords,
-                            ProgressMeter* progressMeter,
-                            bool mayInterrupt );
-
-    /** Popuate the index @param 'idx' using the keys contained in @param 'sorter'. */
-    template< class V >
-    void buildBottomUpPhases2And3( bool dupsAllowed,
-                                   IndexDetails& idx,
-                                   BSONObjExternalSorter& sorter,
-                                   bool dropDups,
-                                   set<DiskLoc>& dupsToDrop,
-                                   CurOp* op,
-                                   SortPhaseOne* phase1,
-                                   ProgressMeterHolder& pm,
-                                   Timer& t,
-                                   bool mayInterrupt );
-
-    /** Drop duplicate documents from the set @param 'dupsToDrop'. */
-    void doDropDups( const char* ns,
-                     NamespaceDetails* d,
-                     const set<DiskLoc>& dupsToDrop,
-                     bool mayInterrupt );
-
 } // namespace mongo
diff --git a/src/mongo/db/pdfile.cpp b/src/mongo/db/pdfile.cpp
index ee0f3817bf9..ac133c0c490 100644
--- a/src/mongo/db/pdfile.cpp
+++ b/src/mongo/db/pdfile.cpp
@@ -1337,15 +1337,15 @@ namespace mongo {
                 IndexDetails& idx = d->idx(idxNo);
                 if (ignoreUniqueIndex(idx))
                     continue;
-                BSONObjSet keys;
-                idx.getKeysFromObject(obj, keys);
-                BSONObj order = idx.keyPattern();
-                IndexInterface& ii = idx.idxInterface();
-                for ( BSONObjSet::iterator i=keys.begin(); i != keys.end(); i++ ) {
-                    // WARNING: findSingle may not be compound index safe.  this may need to change.  see notes in 
-                    // findSingle code.
-                    uassert( 12582, "duplicate key insert for unique index of capped collection",
-                             ii.findSingle(idx, idx.head, *i ).isNull() );
+                auto_ptr<IndexDescriptor> descriptor(CatalogHack::getDescriptor(d, idxNo));
+                auto_ptr<IndexAccessMethod> iam(CatalogHack::getIndex(descriptor.get()));
+                InsertDeleteOptions options;
+                options.logIfError = false;
+                options.dupsAllowed = false;
+                UpdateTicket ticket;
+                Status ret = iam->validateUpdate(BSONObj(), obj, DiskLoc(), options, &ticket);
+                if (ret != Status::OK()) {
+                    uasserted(12582, "duplicate key insert for unique index of capped collection");
                 }
             }
         }
diff --git a/src/mongo/db/prefetch.cpp b/src/mongo/db/prefetch.cpp
index 73bc3047757..fb345ae443d 100644
--- a/src/mongo/db/prefetch.cpp
+++ b/src/mongo/db/prefetch.cpp
@@ -20,6 +20,7 @@
 
 #include "mongo/db/dbhelpers.h"
 #include "mongo/db/diskloc.h"
+#include "mongo/db/index/catalog_hack.h"
 #include "mongo/db/index.h"
 #include "mongo/db/index_update.h"
 #include "mongo/db/jsobj.h"
@@ -103,7 +104,6 @@ namespace mongo {
 
     void prefetchIndexPages(NamespaceDetails *nsd, const BSONObj& obj) {
         DiskLoc unusedDl; // unused
-        IndexInterface::IndexInserter inserter;
         BSONObjSet unusedKeys;
         ReplSetImpl::IndexPrefetchConfig prefetchConfig = theReplSet->getIndexPrefetchConfig();
 
@@ -121,13 +121,9 @@ namespace mongo {
             int indexNo = nsd->findIdIndex();
             if (indexNo == -1) return;
             try {
-                fetchIndexInserters(/*out*/unusedKeys, 
-                                    inserter, 
-                                    nsd, 
-                                    indexNo, 
-                                    obj, 
-                                    unusedDl, 
-                                    /*allowDups*/true);
+                auto_ptr<IndexDescriptor> desc(CatalogHack::getDescriptor(nsd, indexNo));
+                auto_ptr<IndexAccessMethod> iam(CatalogHack::getIndex(desc.get()));
+                iam->touch(obj);
             }
             catch (const DBException& e) {
                 LOG(2) << "ignoring exception in prefetchIndexPages(): " << e.what() << endl;
@@ -143,13 +139,9 @@ namespace mongo {
                 TimerHolder timer( &prefetchIndexStats);
                 // This will page in all index pages for the given object.
                 try {
-                    fetchIndexInserters(/*out*/unusedKeys, 
-                                        inserter, 
-                                        nsd, 
-                                        indexNo, 
-                                        obj, 
-                                        unusedDl, 
-                                        /*allowDups*/true);
+                    auto_ptr<IndexDescriptor> desc(CatalogHack::getDescriptor(nsd, indexNo));
+                    auto_ptr<IndexAccessMethod> iam(CatalogHack::getIndex(desc.get()));
+                    iam->touch(obj);
                 }
                 catch (const DBException& e) {
                     LOG(2) << "ignoring exception in prefetchIndexPages(): " << e.what() << endl;
diff --git a/src/mongo/db/sort_phase_one.h b/src/mongo/db/sort_phase_one.h
index dccb30bf7ad..a88f2ae5d4f 100644
--- a/src/mongo/db/sort_phase_one.h
+++ b/src/mongo/db/sort_phase_one.h
@@ -32,19 +32,14 @@ namespace mongo {
         unsigned long long nkeys;
         bool multi; // multikey index
 
-        void addKeys(const IndexSpec& spec, const BSONObj& o, DiskLoc loc, bool mayInterrupt) {
-            BSONObjSet keys;
-            spec.getKeys(o, keys);
-            int k = 0;
-            for ( BSONObjSet::iterator i=keys.begin(); i != keys.end(); i++ ) {
-                if( ++k == 2 ) {
-                    multi = true;
-                }
-                sorter->add(*i, loc, mayInterrupt);
-                nkeys++;
+        void addKeys(const BSONObjSet& keys, const DiskLoc& loc, bool mayInterrupt) {
+            multi = multi || (keys.size() > 1);
+            for (BSONObjSet::iterator it = keys.begin(); it != keys.end(); ++it) {
+                sorter->add(*it, loc, mayInterrupt);
+                ++nkeys;
             }
-            n++;
+            ++n;
         }
     };
 
-}
+}  // namespace mongo
diff --git a/src/mongo/dbtests/btreetests.cpp b/src/mongo/dbtests/btreetests.cpp
index 433a38ade25..ce73de027f7 100644
--- a/src/mongo/dbtests/btreetests.cpp
+++ b/src/mongo/dbtests/btreetests.cpp
@@ -29,7 +29,6 @@
 #define BtreeBucket BtreeBucket<V0>
 #define btree btree<V0>
 #define btreemod btreemod<V0>
-#define Continuation IndexInsertionContinuationImpl<V0>
 #define testName "btree"
 #define BTVERSION 0
 namespace BtreeTests0 {
@@ -39,11 +38,9 @@ namespace BtreeTests0 {
 #undef BtreeBucket
 #undef btree
 #undef btreemod
-#undef Continuation
 #define BtreeBucket BtreeBucket<V1>
 #define btree btree<V1>
 #define btreemod btreemod<V1>
-#define Continuation IndexInsertionContinuationImpl<V1>
 #undef testName
 #define testName "btree1"
 #undef BTVERSION
@@ -51,11 +48,3 @@ namespace BtreeTests0 {
 namespace BtreeTests1 {
 #include "btreetests.inl"
 }
-
-#undef testName
-#define testName "btree1_twostep"
-#define TESTTWOSTEP 1
-
-namespace BtreeTests2 {
-#include "btreetests.inl"
-}
diff --git a/src/mongo/dbtests/btreetests.inl b/src/mongo/dbtests/btreetests.inl
index 510af5c08d0..d66dfc41e0a 100644
--- a/src/mongo/dbtests/btreetests.inl
+++ b/src/mongo/dbtests/btreetests.inl
@@ -67,18 +67,7 @@
         }
         void insert( BSONObj &key ) {
             const BtreeBucket *b = bt();
-
-#if defined(TESTTWOSTEP)
-            {
-                Continuation c(dl(), recordLoc(), key, Ordering::make(order()), id());
-                b->twoStepInsert(dl(), c, true);
-                c.doIndexInsertionWrites();
-            }
-#else
-            {
-                b->bt_insert( dl(), recordLoc(), key, Ordering::make(order()), true, id(), true );
-            }
-#endif
+            b->bt_insert( dl(), recordLoc(), key, Ordering::make(order()), true, id(), true );
             getDur().commitIfNeeded();
         }
         bool unindex( BSONObj &key ) {
diff --git a/src/mongo/dbtests/indexupdatetests.cpp b/src/mongo/dbtests/indexupdatetests.cpp
index cb5029e165a..5483b6c4f50 100644
--- a/src/mongo/dbtests/indexupdatetests.cpp
+++ b/src/mongo/dbtests/indexupdatetests.cpp
@@ -21,6 +21,7 @@
 #include "mongo/db/btree.h"
 #include "mongo/db/btreecursor.h"
 #include "mongo/db/dbhelpers.h"
+#include "mongo/db/index/btree_based_builder.h"
 #include "mongo/db/kill_current_op.h"
 #include "mongo/db/pdfile.h"
 #include "mongo/db/sort_phase_one.h"
@@ -91,7 +92,8 @@ namespace IndexUpdateTests {
                                                              nDocs,
                                                              nDocs));
             // Add keys to phaseOne.
-            addKeysToPhaseOne( _ns, id, BSON( "a" << 1 ), &phaseOne, nDocs, pm.get(), true );
+            BtreeBasedBuilder::addKeysToPhaseOne( nsdetails(_ns), _ns, id, BSON( "a" << 1 ), &phaseOne, nDocs, pm.get(), true,
+                                                 nsdetails(_ns)->idxNo(id) );
             // Keys for all documents were added to phaseOne.
             ASSERT_EQUALS( static_cast<uint64_t>( nDocs ), phaseOne.n );
         }
@@ -121,26 +123,27 @@ namespace IndexUpdateTests {
             cc().curop()->kill();
             if ( _mayInterrupt ) {
                 // Add keys to phaseOne.
-                ASSERT_THROWS( addKeysToPhaseOne( _ns,
+                ASSERT_THROWS( BtreeBasedBuilder::addKeysToPhaseOne( nsdetails(_ns), _ns,
                                                   id,
                                                   BSON( "a" << 1 ),
                                                   &phaseOne,
                                                   nDocs,
                                                   pm.get(),
-                                                  _mayInterrupt ),
+                                                  _mayInterrupt,
+                                                  nsdetails(_ns)->idxNo(id) ),
                                UserException );
                 // Not all keys were added to phaseOne due to the interrupt.
                 ASSERT( static_cast<uint64_t>( nDocs ) > phaseOne.n );
             }
             else {
                 // Add keys to phaseOne.
-                addKeysToPhaseOne( _ns,
+                BtreeBasedBuilder::addKeysToPhaseOne( nsdetails(_ns), _ns,
                                    id,
                                    BSON( "a" << 1 ),
                                    &phaseOne,
                                    nDocs,
                                    pm.get(),
-                                   _mayInterrupt );
+                                   _mayInterrupt, nsdetails(_ns)->idxNo(id) );
                 // All keys were added to phaseOne despite to the kill request, because
                 // mayInterrupt == false.
                 ASSERT_EQUALS( static_cast<uint64_t>( nDocs ), phaseOne.n );
@@ -304,7 +307,7 @@ namespace IndexUpdateTests {
             // Check the expected number of dups.
             ASSERT_EQUALS( static_cast<uint32_t>( nDocs / 4 * 3 ), dups.size() );
             // Drop the dups.
-            doDropDups( _ns, nsdetails( _ns ), dups, true );
+            BtreeBasedBuilder::doDropDups( _ns, nsdetails( _ns ), dups, true );
             // Check that the expected number of documents remain.
             ASSERT_EQUALS( static_cast<uint32_t>( nDocs / 4 ), _client.count( _ns ) );
         }
@@ -341,14 +344,14 @@ namespace IndexUpdateTests {
             cc().curop()->kill();
             if ( _mayInterrupt ) {
                 // doDropDups() aborts.
-                ASSERT_THROWS( doDropDups( _ns, nsdetails( _ns ), dups, _mayInterrupt ),
+                ASSERT_THROWS( BtreeBasedBuilder::doDropDups( _ns, nsdetails( _ns ), dups, _mayInterrupt ),
                                UserException );
                 // Not all dups are dropped.
                 ASSERT( static_cast<uint32_t>( nDocs / 4 ) < _client.count( _ns ) );
             }
             else {
                 // doDropDups() succeeds.
-                doDropDups( _ns, nsdetails( _ns ), dups, _mayInterrupt );
+                BtreeBasedBuilder::doDropDups( _ns, nsdetails( _ns ), dups, _mayInterrupt );
                 // The expected number of documents were dropped.
                 ASSERT_EQUALS( static_cast<uint32_t>( nDocs / 4 ), _client.count( _ns ) );
             }
diff --git a/src/mongo/dbtests/namespacetests.cpp b/src/mongo/dbtests/namespacetests.cpp
index 8a0d9aba0ad..58ebcce1392 100644
--- a/src/mongo/dbtests/namespacetests.cpp
+++ b/src/mongo/dbtests/namespacetests.cpp
@@ -24,6 +24,7 @@
 #include "../db/db.h"
 #include "../db/json.h"
 #include "mongo/db/hashindex.h"
+#include "mongo/db/index/btree_key_generator.h"
 #include "mongo/db/queryutil.h"
 
 #include "dbtests.h"
@@ -57,13 +58,38 @@ namespace NamespaceTests {
                 id_.info = theDataFileMgr.insert( ns(), bobj.objdata(), bobj.objsize() );
                 // head not needed for current tests
                 // idx_.head = BtreeBucket::addHead( id_ );
+
+                _keyPattern = key().getOwned();
+                // The key generation wants these values.
+                vector<const char*> fieldNames;
+                vector<BSONElement> fixed;
+
+                BSONObjIterator it(_keyPattern);
+                while (it.more()) {
+                    BSONElement elt = it.next();
+                    fieldNames.push_back(elt.fieldName());
+                    fixed.push_back(BSONElement());
+                }  
+
+                _keyGen.reset(new BtreeKeyGeneratorV1(fieldNames, fixed, sparse));
             }
+
+            scoped_ptr<BtreeKeyGenerator> _keyGen;
+            BSONObj _keyPattern;
+
             static const char* ns() {
                 return "unittests.indexdetailstests";
             }
+
             IndexDetails& id() {
                 return id_;
             }
+
+            // TODO: This is testing Btree key creation, not IndexDetails.
+            void getKeysFromObject(const BSONObj& obj, BSONObjSet& out) {
+                _keyGen->getKeys(obj, &out);
+            }
+
             virtual BSONObj key() const {
                 BSONObjBuilder k;
                 k.append( "a", 1 );
@@ -132,7 +158,7 @@ namespace NamespaceTests {
                 b.append( "a", 5 );
                 e.append( "", 5 );
                 BSONObjSet keys;
-                id().getKeysFromObject( b.done(), keys );
+                getKeysFromObject( b.done(), keys );
                 checkSize( 1, keys );
                 assertEquals( e.obj(), *keys.begin() );
             }
@@ -148,7 +174,7 @@ namespace NamespaceTests {
                 a.append( "c", "foo" );
                 e.append( "", 4 );
                 BSONObjSet keys;
-                id().getKeysFromObject( a.done(), keys );
+                getKeysFromObject( a.done(), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( e.obj(), *keys.begin() );
             }
@@ -166,7 +192,7 @@ namespace NamespaceTests {
                 b.append( "a", shortArray()) ;
 
                 BSONObjSet keys;
-                id().getKeysFromObject( b.done(), keys );
+                getKeysFromObject( b.done(), keys );
                 checkSize( 3, keys );
                 int j = 1;
                 for ( BSONObjSet::iterator i = keys.begin(); i != keys.end(); ++i, ++j ) {
@@ -186,7 +212,7 @@ namespace NamespaceTests {
                 b.append( "b", 2 );
 
                 BSONObjSet keys;
-                id().getKeysFromObject( b.done(), keys );
+                getKeysFromObject( b.done(), keys );
                 checkSize( 3, keys );
                 int j = 1;
                 for ( BSONObjSet::iterator i = keys.begin(); i != keys.end(); ++i, ++j ) {
@@ -211,7 +237,7 @@ namespace NamespaceTests {
                 b.append( "a", shortArray()) ;
 
                 BSONObjSet keys;
-                id().getKeysFromObject( b.done(), keys );
+                getKeysFromObject( b.done(), keys );
                 checkSize( 3, keys );
                 int j = 1;
                 for ( BSONObjSet::iterator i = keys.begin(); i != keys.end(); ++i, ++j ) {
@@ -240,7 +266,7 @@ namespace NamespaceTests {
                 a.append( "a", b.done() );
 
                 BSONObjSet keys;
-                id().getKeysFromObject( a.done(), keys );
+                getKeysFromObject( a.done(), keys );
                 checkSize( 3, keys );
                 int j = 1;
                 for ( BSONObjSet::iterator i = keys.begin(); i != keys.end(); ++i, ++j ) {
@@ -264,7 +290,7 @@ namespace NamespaceTests {
                 b.append( "b", shortArray() );
 
                 BSONObjSet keys;
-                ASSERT_THROWS( id().getKeysFromObject( b.done(), keys ),
+                ASSERT_THROWS( getKeysFromObject( b.done(), keys ),
                                   UserException );
             }
         private:
@@ -284,7 +310,7 @@ namespace NamespaceTests {
                 b.append( "a", elts );
 
                 BSONObjSet keys;
-                id().getKeysFromObject( b.done(), keys );
+                getKeysFromObject( b.done(), keys );
                 checkSize( 3, keys );
                 int j = 1;
                 for ( BSONObjSet::iterator i = keys.begin(); i != keys.end(); ++i, ++j ) {
@@ -311,7 +337,7 @@ namespace NamespaceTests {
                 b.append( "d", 99 );
 
                 BSONObjSet keys;
-                id().getKeysFromObject( b.done(), keys );
+                getKeysFromObject( b.done(), keys );
                 checkSize( 3, keys );
                 int j = 1;
                 for ( BSONObjSet::iterator i = keys.begin(); i != keys.end(); ++i, ++j ) {
@@ -345,7 +371,7 @@ namespace NamespaceTests {
                 BSONObj obj = b.obj();
                 
                 BSONObjSet keys;
-                id().getKeysFromObject( obj, keys );
+                getKeysFromObject( obj, keys );
                 checkSize( 4, keys );
                 BSONObjSet::iterator i = keys.begin();
                 assertEquals( nullObj(), *i++ ); // see SERVER-3377
@@ -374,7 +400,7 @@ namespace NamespaceTests {
                 b.append( "a", elts );
 
                 BSONObjSet keys;
-                id().getKeysFromObject( b.done(), keys );
+                getKeysFromObject( b.done(), keys );
                 checkSize( 1, keys );
                 assertEquals( nullObj(), *keys.begin() );
             }
@@ -389,7 +415,7 @@ namespace NamespaceTests {
             void run() {
                 create();
                 BSONObjSet keys;
-                id().getKeysFromObject( BSON( "b" << 1 ), keys );
+                getKeysFromObject( BSON( "b" << 1 ), keys );
                 checkSize( 1, keys );
                 assertEquals( nullObj(), *keys.begin() );
             }
@@ -404,7 +430,7 @@ namespace NamespaceTests {
             void run() {
                 create();
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:[1,2]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[1,2]}" ), keys );
                 checkSize( 1, keys );
                 assertEquals( nullObj(), *keys.begin() );
             }
@@ -421,14 +447,14 @@ namespace NamespaceTests {
 
                 {
                     BSONObjSet keys;
-                    id().getKeysFromObject( fromjson( "{x:'a',y:'b'}" ) , keys );
+                    getKeysFromObject( fromjson( "{x:'a',y:'b'}" ) , keys );
                     checkSize( 1 , keys );
                     assertEquals( BSON( "" << "a" << "" << "b" ) , *keys.begin() );
                 }
 
                 {
                     BSONObjSet keys;
-                    id().getKeysFromObject( fromjson( "{x:'a'}" ) , keys );
+                    getKeysFromObject( fromjson( "{x:'a'}" ) , keys );
                     checkSize( 1 , keys );
                     BSONObjBuilder b;
                     b.append( "" , "a" );
@@ -450,7 +476,7 @@ namespace NamespaceTests {
             void run() {
                 create();
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:[{b:[2]}]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[{b:[2]}]}" ), keys );
                 checkSize( 1, keys );
                 assertEquals( BSON( "" << 2 ), *keys.begin() );
             }
@@ -465,7 +491,7 @@ namespace NamespaceTests {
             void run() {
                 create();
                 BSONObjSet keys;
-                ASSERT_THROWS( id().getKeysFromObject( fromjson( "{a:[{b:[1],c:[2]}]}" ), keys ),
+                ASSERT_THROWS( getKeysFromObject( fromjson( "{a:[{b:[1],c:[2]}]}" ), keys ),
                                   UserException );
             }
         private:
@@ -479,7 +505,7 @@ namespace NamespaceTests {
             void run() {
                 create();
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:[{b:1},{c:2}]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[{b:1},{c:2}]}" ), keys );
                 checkSize( 2, keys );
                 BSONObjSet::iterator i = keys.begin();
                 {
@@ -507,7 +533,7 @@ namespace NamespaceTests {
             void run() {
                 create();
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:[{b:1},{b:[1,2,3]}]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[{b:1},{b:[1,2,3]}]}" ), keys );
                 checkSize( 3, keys );
             }
         private:
@@ -522,19 +548,19 @@ namespace NamespaceTests {
                 create();
 
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:[1,2]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[1,2]}" ), keys );
                 checkSize(2, keys );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:[1]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[1]}" ), keys );
                 checkSize(1, keys );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:null}" ), keys );
+                getKeysFromObject( fromjson( "{a:null}" ), keys );
                 checkSize(1, keys );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:[]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[]}" ), keys );
                 checkSize(1, keys );
                 ASSERT_EQUALS( Undefined, keys.begin()->firstElement().type() );
                 keys.clear();
@@ -547,7 +573,7 @@ namespace NamespaceTests {
              	create();   
                 
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:[1,2]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[1,2]}" ), keys );
                 checkSize(2, keys );
                 BSONObjSet::const_iterator i = keys.begin();
                 ASSERT_EQUALS( BSON( "" << 1 << "" << 1 ), *i );
@@ -568,7 +594,7 @@ namespace NamespaceTests {
              	create();   
 
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:[]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[]}" ), keys );
                 checkSize(1, keys );
                 ASSERT_EQUALS( fromjson( "{'':undefined,'':undefined}" ), *keys.begin() );
                 keys.clear();
@@ -586,20 +612,20 @@ namespace NamespaceTests {
                 create();
 
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:1,b:[1,2]}" ), keys );
+                getKeysFromObject( fromjson( "{a:1,b:[1,2]}" ), keys );
                 checkSize(2, keys );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:1,b:[1]}" ), keys );
+                getKeysFromObject( fromjson( "{a:1,b:[1]}" ), keys );
                 checkSize(1, keys );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:1,b:null}" ), keys );
+                getKeysFromObject( fromjson( "{a:1,b:null}" ), keys );
                 //cout << "YO : " << *(keys.begin()) << endl;
                 checkSize(1, keys );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:1,b:[]}" ), keys );
+                getKeysFromObject( fromjson( "{a:1,b:[]}" ), keys );
                 checkSize(1, keys );
                 //cout << "YO : " << *(keys.begin()) << endl;
                 BSONObjIterator i( *keys.begin() );
@@ -620,7 +646,7 @@ namespace NamespaceTests {
              	create();
                 
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:[]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':null}" ), *keys.begin() );
                 keys.clear();
@@ -635,7 +661,7 @@ namespace NamespaceTests {
              	create();
                 
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:[]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':null,'':null}" ), *keys.begin() );
                 keys.clear();
@@ -650,17 +676,17 @@ namespace NamespaceTests {
              	create();
                 
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:[]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':undefined,'':null}" ), *keys.begin() );
                 keys.clear();
                 
-                id().getKeysFromObject( fromjson( "{a:[{b:1}]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[{b:1}]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':{b:1},'':1}" ), *keys.begin() );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:[{b:[]}]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[{b:[]}]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':{b:[]},'':undefined}" ), *keys.begin() );
                 keys.clear();
@@ -675,7 +701,7 @@ namespace NamespaceTests {
              	create();
                 
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:[]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':null,'':undefined}" ), *keys.begin() );
                 keys.clear();
@@ -690,7 +716,7 @@ namespace NamespaceTests {
              	create( true );
                 
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:[]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':null,'':undefined}" ), *keys.begin() );
                 keys.clear();
@@ -705,15 +731,15 @@ namespace NamespaceTests {
              	create( true );
                 
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:1}" ), keys );
+                getKeysFromObject( fromjson( "{a:1}" ), keys );
                 checkSize( 0, keys );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:[]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[]}" ), keys );
                 checkSize( 0, keys );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:[{c:1}]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[{c:1}]}" ), keys );
                 checkSize( 0, keys );
                 keys.clear();
             }
@@ -727,15 +753,15 @@ namespace NamespaceTests {
              	create( true );
                 
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:1}" ), keys );
+                getKeysFromObject( fromjson( "{a:1}" ), keys );
                 checkSize( 0, keys );
                 keys.clear();
                 
-                id().getKeysFromObject( fromjson( "{a:[]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[]}" ), keys );
                 checkSize( 0, keys );
                 keys.clear();
                 
-                id().getKeysFromObject( fromjson( "{a:[{c:1}]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[{c:1}]}" ), keys );
                 checkSize( 0, keys );
                 keys.clear();
             }
@@ -749,17 +775,17 @@ namespace NamespaceTests {
              	create();
                 
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:[]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':null}" ), *keys.begin() );
                 keys.clear();
                 
-                id().getKeysFromObject( fromjson( "{a:[1]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[1]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':null}" ), *keys.begin() );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:[1,{b:1}]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[1,{b:1}]}" ), keys );
                 checkSize( 2, keys );
                 BSONObjSet::const_iterator c = keys.begin();
                 ASSERT_EQUALS( fromjson( "{'':null}" ), *c );
@@ -777,15 +803,15 @@ namespace NamespaceTests {
              	create( true );
                 
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:[]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[]}" ), keys );
                 checkSize( 0, keys );
                 keys.clear();
                 
-                id().getKeysFromObject( fromjson( "{a:[1]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[1]}" ), keys );
                 checkSize( 0, keys );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:[1,{b:1}]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[1,{b:1}]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':1}" ), *keys.begin() );
                 keys.clear();
@@ -800,29 +826,29 @@ namespace NamespaceTests {
              	create();
                 
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:[1]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[1]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( BSON( "" << 1 ), *keys.begin() );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:[[1]]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[[1]]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':[1]}" ), *keys.begin() );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:[[]]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[[]]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':undefined}" ), *keys.begin() );
                 keys.clear();
                 
-                id().getKeysFromObject( fromjson( "{a:{'0':1}}" ), keys );
+                getKeysFromObject( fromjson( "{a:{'0':1}}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( BSON( "" << 1 ), *keys.begin() );
                 keys.clear();
 
-                ASSERT_THROWS( id().getKeysFromObject( fromjson( "{a:[{'0':1}]}" ), keys ), UserException );
+                ASSERT_THROWS( getKeysFromObject( fromjson( "{a:[{'0':1}]}" ), keys ), UserException );
 
-                ASSERT_THROWS( id().getKeysFromObject( fromjson( "{a:[1,{'0':2}]}" ), keys ), UserException );
+                ASSERT_THROWS( getKeysFromObject( fromjson( "{a:[1,{'0':2}]}" ), keys ), UserException );
             }
         protected:
             BSONObj key() const { return BSON( "a.0" << 1 ); }
@@ -834,22 +860,22 @@ namespace NamespaceTests {
              	create();
                 
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:[[1]]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[[1]]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':1}" ), *keys.begin() );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:[[]]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[[]]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':null}" ), *keys.begin() );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:[]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':null}" ), *keys.begin() );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:[[[]]]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[[[]]]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':undefined}" ), *keys.begin() );
                 keys.clear();
@@ -864,37 +890,37 @@ namespace NamespaceTests {
              	create();
                 
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:[{b:1}]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[{b:1}]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':1}" ), *keys.begin() );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:[{b:[1]}]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[{b:[1]}]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':1}" ), *keys.begin() );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:[{b:[[1]]}]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[{b:[[1]]}]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':[1]}" ), *keys.begin() );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:[[{b:1}]]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[[{b:1}]]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':1}" ), *keys.begin() );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:[[{b:[1]}]]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[[{b:[1]}]]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':1}" ), *keys.begin() );
                 keys.clear();
 
-                id().getKeysFromObject( fromjson( "{a:[[{b:[[1]]}]]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[[{b:[[1]]}]]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':[1]}" ), *keys.begin() );
                 keys.clear();
                 
-                id().getKeysFromObject( fromjson( "{a:[[{b:[]}]]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[[{b:[]}]]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':undefined}" ), *keys.begin() );
                 keys.clear();
@@ -909,7 +935,7 @@ namespace NamespaceTests {
              	create();
                 
                 BSONObjSet keys;
-                id().getKeysFromObject( fromjson( "{a:[{b:[1]}]}" ), keys );
+                getKeysFromObject( fromjson( "{a:[{b:[1]}]}" ), keys );
                 checkSize( 1, keys );
                 ASSERT_EQUALS( fromjson( "{'':1}" ), *keys.begin() );
                 keys.clear();