SERVER-13084 migrate builder to new iface, some clean-up

21 files changed, 696 insertions, 647 deletions

diff --git a/src/mongo/SConscript b/src/mongo/SConscript
index 11e26346b10..6d0485feced 100644
--- a/src/mongo/SConscript
+++ b/src/mongo/SConscript
@@ -539,7 +539,6 @@ serverOnlyFiles = [ "db/curop.cpp",
                     "db/lockstat.cpp",
                     "db/lockstate.cpp",
                     "db/structure/btree/key.cpp",
-                    "db/structure/btree/btreebuilder.cpp",
                     "util/logfile.cpp",
                     "util/alignedbuilder.cpp",
                     "util/elapsed_tracker.cpp",
@@ -594,6 +593,7 @@ serverOnlyFiles = [ "db/curop.cpp",
                     "db/index/2d_access_method.cpp",
                     "db/index/btree_access_method.cpp",
                     "db/index/btree_based_access_method.cpp",
+                    "db/index/btree_based_bulk_access_method.cpp",
                     "db/index/btree_index_cursor.cpp",
                     "db/index/index_descriptor.cpp",
                     "db/index/fts_access_method.cpp",
diff --git a/src/mongo/db/catalog/index_create.cpp b/src/mongo/db/catalog/index_create.cpp
index 44e1fa157c8..f71b107e984 100644
--- a/src/mongo/db/catalog/index_create.cpp
+++ b/src/mongo/db/catalog/index_create.cpp
@@ -34,20 +34,19 @@
 #include "mongo/client/dbclientinterface.h"
 #include "mongo/db/audit.h"
 #include "mongo/db/background.h"
-#include "mongo/db/structure/btree/btreebuilder.h"
+#include "mongo/db/catalog/collection.h"
 #include "mongo/db/clientcursor.h"
 #include "mongo/db/curop.h"
 #include "mongo/db/extsort.h"
-#include "mongo/db/structure/catalog/index_details.h"
 #include "mongo/db/kill_current_op.h"
-#include "mongo/db/structure/catalog/namespace_details.h"
 #include "mongo/db/pdfile_private.h"
 #include "mongo/db/query/internal_plans.h"
 #include "mongo/db/query/runner_yield_policy.h"
 #include "mongo/db/repl/is_master.h"
 #include "mongo/db/repl/oplog.h"
 #include "mongo/db/repl/rs.h"
-#include "mongo/db/catalog/collection.h"
+#include "mongo/db/structure/catalog/index_details.h"
+#include "mongo/db/structure/catalog/namespace_details.h"
 #include "mongo/util/processinfo.h"
 #include "mongo/util/progress_meter.h"
 
@@ -79,14 +78,13 @@ namespace mongo {
     unsigned long long addExistingToIndex( Collection* collection,
                                            const IndexDescriptor* descriptor,
                                            IndexAccessMethod* accessMethod,
-                                           bool shouldYield ) {
+                                           bool shouldYield) {
 
         string ns = collection->ns().ns(); // our copy for sanity
 
         bool dupsAllowed = !descriptor->unique();
         bool dropDups = descriptor->dropDups();
 
-
         string curopMessage;
         {
             stringstream ss;
@@ -264,6 +262,13 @@ namespace mongo {
             Status status = btreeState->accessMethod()->commitBulk( bulk,
                                                                     mayInterrupt,
                                                                     &dupsToDrop );
+
+            // Code above us expects a uassert in case of dupkey errors.
+            if (ErrorCodes::DuplicateKey == status.code()) {
+                uassertStatusOK(status);
+            }
+
+            // Any other errors are probably bad and deserve a massert.
             massert( 17398,
                      str::stream() << "commitBulk failed: " << status.toString(),
                      status.isOK() );
diff --git a/src/mongo/db/index/btree_access_method.h b/src/mongo/db/index/btree_access_method.h
index dbe1a7980af..d40bc013767 100644
--- a/src/mongo/db/index/btree_access_method.h
+++ b/src/mongo/db/index/btree_access_method.h
@@ -31,10 +31,9 @@
 #include <boost/scoped_ptr.hpp>
 
 #include "mongo/base/status.h"
-#include "mongo/db/structure/btree/btree.h"
-#include "mongo/db/index/index_access_method.h"
-#include "mongo/db/index/btree_key_generator.h"
 #include "mongo/db/index/btree_based_access_method.h"
+#include "mongo/db/index/btree_key_generator.h"
+#include "mongo/db/index/index_access_method.h"
 #include "mongo/db/jsobj.h"
 
 namespace mongo {
diff --git a/src/mongo/db/index/btree_based_access_method.cpp b/src/mongo/db/index/btree_based_access_method.cpp
index 11b4b92f9c2..ebd933cb0ac 100644
--- a/src/mongo/db/index/btree_based_access_method.cpp
+++ b/src/mongo/db/index/btree_based_access_method.cpp
@@ -34,6 +34,7 @@
 #include "mongo/base/status.h"
 #include "mongo/db/curop.h"
 #include "mongo/db/extsort.h"
+#include "mongo/db/index/btree_based_bulk_access_method.h"
 #include "mongo/db/index/btree_index_cursor.h"
 #include "mongo/db/jsobj.h"
 #include "mongo/db/keypattern.h"
@@ -42,8 +43,6 @@
 #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/db/structure/btree/btreebuilder.h"
 #include "mongo/db/structure/btree/btree_interface.h"
 #include "mongo/util/progress_meter.h"
 
@@ -189,22 +188,7 @@ namespace mongo {
     }
 
     Status BtreeBasedAccessMethod::initializeAsEmpty() {
-        if ( !_btreeState->head().isNull() )
-            return Status( ErrorCodes::InternalError, "index already initialized" );
-
-        DiskLoc newHead;
-        if ( 0 == _descriptor->version() ) {
-            newHead = BtreeBucket<V0>::addBucket( _btreeState );
-        }
-        else if ( 1 == _descriptor->version() ) {
-            newHead = BtreeBucket<V1>::addBucket( _btreeState );
-        }
-        else {
-            return Status( ErrorCodes::InternalError, "invalid index number" );
-        }
-        _btreeState->setHead( newHead );
-
-        return Status::OK();
+        return _newInterface->initAsEmpty();
     }
 
     Status BtreeBasedAccessMethod::touch(const BSONObj& obj) {
@@ -220,23 +204,26 @@ namespace mongo {
         return Status::OK();
     }
 
-    DiskLoc BtreeBasedAccessMethod::findSingle( const BSONObj& key ) const {
-        DiskLoc head = _btreeState->head();
-        Record* record = _btreeState->recordStore()->recordFor( head );
+    DiskLoc BtreeBasedAccessMethod::findSingle(const BSONObj& key) const {
+        DiskLoc bucket;
+        int pos;
+
+        _newInterface->locate(key, minDiskLoc, 1, &bucket, &pos);
 
-        if ( 0 == _descriptor->version() ) {
-            return BtreeBucket<V0>::asVersion( record )->findSingle( _btreeState,
-                                                                     _btreeState->head(),
-                                                                     key );
+        // A null bucket means the key wasn't found (nor was anything found after it).
+        if (bucket.isNull()) {
+            return DiskLoc();
         }
-        if ( 1 == _descriptor->version() ) {
-            return BtreeBucket<V1>::asVersion( record )->findSingle( _btreeState,
-                                                                     _btreeState->head(),
-                                                                     key );
+
+        // We found something but it could be a key after 'key'.  Examine what we're pointing at.
+        if (0 != key.woCompare(_newInterface->getKey(bucket, pos), BSONObj(), false)) {
+            // If the keys don't match, return "not found."
+            return DiskLoc();
         }
-        verify( 0 );
-    }
 
+        // Return the DiskLoc found.
+        return _newInterface->getDiskLoc(bucket, pos);
+    }
 
     Status BtreeBasedAccessMethod::validate(int64_t* numKeys) {
         // XXX: long long vs int64_t
@@ -284,7 +271,7 @@ namespace mongo {
 
     Status BtreeBasedAccessMethod::update(const UpdateTicket& ticket, int64_t* numUpdated) {
         if (!ticket._isValid) {
-            return Status(ErrorCodes::InternalError, "Invalid updateticket in update");
+            return Status(ErrorCodes::InternalError, "Invalid UpdateTicket in update");
         }
 
         BtreeBasedPrivateUpdateData* data =
@@ -307,255 +294,25 @@ namespace mongo {
         return Status::OK();
     }
 
-    // -------
-
-    class BtreeBulk : public IndexAccessMethod {
-    public:
-        BtreeBulk( BtreeBasedAccessMethod* real ) {
-            _real = real;
-        }
-
-        ~BtreeBulk() {}
-
-        virtual Status insert(const BSONObj& obj,
-                              const DiskLoc& loc,
-                              const InsertDeleteOptions& options,
-                              int64_t* numInserted) {
-            BSONObjSet keys;
-            _real->getKeys(obj, &keys);
-            _phase1.addKeys(keys, loc, false);
-            if ( numInserted )
-                *numInserted += keys.size();
-            return Status::OK();
-        }
-
-        virtual Status remove(const BSONObj& obj,
-                              const DiskLoc& loc,
-                              const InsertDeleteOptions& options,
-                              int64_t* numDeleted) {
-            return _notAllowed();
-        }
-
-        virtual Status validateUpdate(const BSONObj& from,
-                                      const BSONObj& to,
-                                      const DiskLoc& loc,
-                                      const InsertDeleteOptions& options,
-                                      UpdateTicket* ticket) {
-            return _notAllowed();
-        }
-
-        virtual Status update(const UpdateTicket& ticket, int64_t* numUpdated) {
-            return _notAllowed();
-        }
-
-        virtual Status newCursor(IndexCursor **out) const {
-            return _notAllowed();
-        }
-
-        virtual Status initializeAsEmpty() {
-            return _notAllowed();
-        }
-
-        virtual IndexAccessMethod* initiateBulk() {
-            return NULL;
-        }
-
-        virtual Status commitBulk( IndexAccessMethod* bulk,
-                                   bool mayInterrupt,
-                                   std::set<DiskLoc>* dups ) {
-            verify( this == bulk );
-            return Status::OK();
-        }
-
-        virtual Status touch(const BSONObj& obj) {
-            return _notAllowed();
-        }
-
-        virtual Status validate(int64_t* numKeys) {
-            return _notAllowed();
-        }
-
-        // -------
-
-        template< class V >
-        void commit( set<DiskLoc>* dupsToDrop,
-                     CurOp* op,
-                     bool mayInterrupt ) {
-
-            Timer timer;
-
-            IndexCatalogEntry* entry = _real->_btreeState;
-
-            bool dupsAllowed = !entry->descriptor()->unique() ||
-                ignoreUniqueIndex(entry->descriptor());
-            bool dropDups = entry->descriptor()->dropDups() || inDBRepair;
-
-            BtreeBuilder<V> btBuilder(dupsAllowed, entry);
-
-            BSONObj keyLast;
-            scoped_ptr<BSONObjExternalSorter::Iterator> i( _phase1.sorter->iterator() );
-
-            // verifies that pm and op refer to the same ProgressMeter
-            ProgressMeter& pm = op->setMessage("Index Bulk Build: (2/3) btree bottom up",
-                                               "Index: (2/3) BTree Bottom Up Progress",
-                                               _phase1.nkeys,
-                                               10);
-
-            while( i->more() ) {
-                RARELY if ( mayInterrupt ) killCurrentOp.checkForInterrupt();
-                ExternalSortDatum 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 (ErrorCodes::isInterruption(
-                            DBException::convertExceptionCode(e.getCode()))) {
-                        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.
-                    */
-                    if ( dupsToDrop ) {
-                        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 Bulk Build: (3/3) btree-middle",
-                           "Index: (3/3) BTree Middle Progress");
-            LOG(timer.seconds() > 10 ? 0 : 1 ) << "\t done building bottom layer, going to commit";
-            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;
-            }
-        }
-
-        // -------
-
-        Status _notAllowed() const {
-            return Status( ErrorCodes::InternalError, "cannot use bulk for this yet" );
-        }
-
-        BtreeBasedAccessMethod* _real; // now owned here
-        SortPhaseOne _phase1;
-    };
-
-    int oldCompare(const BSONObj& l,const BSONObj& r, const Ordering &o); // key.cpp
-
-    class BtreeExternalSortComparisonV0 : public ExternalSortComparison {
-    public:
-        BtreeExternalSortComparisonV0(const BSONObj& ordering)
-            : _ordering(Ordering::make(ordering)){
-        }
-
-        virtual ~BtreeExternalSortComparisonV0() { }
-
-        virtual int compare(const ExternalSortDatum& l, const ExternalSortDatum& r) const {
-            int x = oldCompare(l.first, r.first, _ordering);
-            if (x) { return x; }
-            return l.second.compare(r.second);
-        }
-    private:
-        const Ordering _ordering;
-    };
-
-    class BtreeExternalSortComparisonV1 : public ExternalSortComparison {
-    public:
-        BtreeExternalSortComparisonV1(const BSONObj& ordering)
-            : _ordering(Ordering::make(ordering)) {
-        }
-
-        virtual ~BtreeExternalSortComparisonV1() { }
-
-        virtual int compare(const ExternalSortDatum& l, const ExternalSortDatum& r) const {
-            int x = l.first.woCompare(r.first, _ordering, /*considerfieldname*/false);
-            if (x) { return x; }
-            return l.second.compare(r.second);
-        }
-    private:
-        const Ordering _ordering;
-    };
-
-    ExternalSortComparison* BtreeBasedAccessMethod::getComparison(int version,
-                                                                  const BSONObj& keyPattern) {
-
-        if ( 0 == version ) {
-            return new BtreeExternalSortComparisonV0( keyPattern );
-        }
-        else if ( 1 == version ) {
-            return new BtreeExternalSortComparisonV1( keyPattern );
-        }
-        verify( 0 );
-        return NULL;
-    }
-
     IndexAccessMethod* BtreeBasedAccessMethod::initiateBulk() {
+        // If there's already data in the index, don't do anything.
         if (!_newInterface->isEmpty()) {
             return NULL;
         }
 
-        auto_ptr<BtreeBulk> bulk( new BtreeBulk( this ) );
-        bulk->_phase1.sortCmp.reset( getComparison( _descriptor->version(),
-                                                    _descriptor->keyPattern() ) );
-
-        bulk->_phase1.sorter.reset( new BSONObjExternalSorter(bulk->_phase1.sortCmp.get()) );
-        bulk->_phase1.sorter->hintNumObjects( _btreeState->collection()->numRecords() );
-
-        return bulk.release();
+        return new BtreeBasedBulkAccessMethod(
+            this, _newInterface.get(), _descriptor, _btreeState->collection()->numRecords());
     }
 
-    Status BtreeBasedAccessMethod::commitBulk( IndexAccessMethod* bulkRaw,
-                                               bool mayInterrupt,
-                                               set<DiskLoc>* dupsToDrop ) {
-
+    Status BtreeBasedAccessMethod::commitBulk(IndexAccessMethod* bulkRaw,
+                                              bool mayInterrupt,
+                                              set<DiskLoc>* dupsToDrop) {
         if (!_newInterface->isEmpty()) {
-            return Status( ErrorCodes::InternalError, "trying to commit, but has data already" );
-        }
-
-        {
-            DiskLoc oldHead = _btreeState->head();
-            _btreeState->setHead( DiskLoc() );
-            _btreeState->recordStore()->deleteRecord( oldHead );
+            return Status(ErrorCodes::InternalError, "trying to commit but has data already");
         }
 
-        string ns = _btreeState->collection()->ns().ns();
-
-        BtreeBulk* bulk = static_cast<BtreeBulk*>( bulkRaw );
-        if ( bulk->_phase1.multi )
-            _btreeState->setMultikey();
-
-        bulk->_phase1.sorter->sort( false );
-
-        if ( _descriptor->version() == 0 )
-            bulk->commit<V0>( dupsToDrop, cc().curop(), mayInterrupt );
-        else if ( _descriptor->version() == 1 )
-            bulk->commit<V1>( dupsToDrop, cc().curop(), mayInterrupt );
-        else
-            return Status( ErrorCodes::InternalError, "bad btree version" );
-
-        return Status::OK();
+        BtreeBasedBulkAccessMethod* bulk = static_cast<BtreeBasedBulkAccessMethod*>(bulkRaw);
+        return bulk->commit(dupsToDrop, cc().curop(), mayInterrupt);
     }
 
-
 }  // namespace mongo
diff --git a/src/mongo/db/index/btree_based_access_method.h b/src/mongo/db/index/btree_based_access_method.h
index f75d63ed042..5d5dab921dc 100644
--- a/src/mongo/db/index/btree_based_access_method.h
+++ b/src/mongo/db/index/btree_based_access_method.h
@@ -40,7 +40,6 @@
 
 namespace mongo {
 
-    class BtreeBulk;
     class ExternalSortComparison;
 
     /**
@@ -96,13 +95,9 @@ namespace mongo {
         // XXX: consider migrating callers to use IndexCursor instead
         virtual DiskLoc findSingle( const BSONObj& key ) const;
 
-        // exposed for testing, used for bulk commit
-        static ExternalSortComparison* getComparison(int version,
-                                                     const BSONObj& keyPattern);
-
     protected:
         // Friends who need getKeys.
-        friend class BtreeBulk;
+        friend class BtreeBasedBulkAccessMethod;
 
         // See below for body.
         class BtreeBasedPrivateUpdateData;
diff --git a/src/mongo/db/index/btree_based_bulk_access_method.cpp b/src/mongo/db/index/btree_based_bulk_access_method.cpp
new file mode 100644
index 00000000000..b812c4d5999
--- /dev/null
+++ b/src/mongo/db/index/btree_based_bulk_access_method.cpp
@@ -0,0 +1,210 @@
+/**
+*    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/>.
+*
+*    As a special exception, the copyright holders give permission to link the
+*    code of portions of this program with the OpenSSL library under certain
+*    conditions as described in each individual source file and distribute
+*    linked combinations including the program with the OpenSSL library. You
+*    must comply with the GNU Affero General Public License in all respects for
+*    all of the code used other than as permitted herein. If you modify file(s)
+*    with this exception, you may extend this exception to your version of the
+*    file(s), but you are not obligated to do so. If you do not wish to do so,
+*    delete this exception statement from your version. If you delete this
+*    exception statement from all source files in the program, then also delete
+*    it in the license file.
+*/
+
+#include "mongo/db/index/btree_based_bulk_access_method.h"
+
+#include "mongo/db/kill_current_op.h"
+#include "mongo/db/pdfile_private.h"  // This is for inDBRepair.
+#include "mongo/db/repl/rs.h"         // This is for ignoreUniqueIndex.
+#include "mongo/util/progress_meter.h"
+
+namespace mongo {
+
+    //
+    // Comparison for external sorter interface
+    //
+
+    // Defined in db/structure/btree/key.cpp
+    // XXX TODO: rename to something more descriptive, etc. etc.
+    int oldCompare(const BSONObj& l,const BSONObj& r, const Ordering &o);
+
+    class BtreeExternalSortComparisonV0 : public ExternalSortComparison {
+    public:
+        BtreeExternalSortComparisonV0(const BSONObj& ordering)
+            : _ordering(Ordering::make(ordering)){
+        }
+
+        virtual ~BtreeExternalSortComparisonV0() { }
+
+        virtual int compare(const ExternalSortDatum& l, const ExternalSortDatum& r) const {
+            int x = oldCompare(l.first, r.first, _ordering);
+            if (x) { return x; }
+            return l.second.compare(r.second);
+        }
+    private:
+        const Ordering _ordering;
+    };
+
+    class BtreeExternalSortComparisonV1 : public ExternalSortComparison {
+    public:
+        BtreeExternalSortComparisonV1(const BSONObj& ordering)
+            : _ordering(Ordering::make(ordering)) {
+        }
+
+        virtual ~BtreeExternalSortComparisonV1() { }
+
+        virtual int compare(const ExternalSortDatum& l, const ExternalSortDatum& r) const {
+            int x = l.first.woCompare(r.first, _ordering, /*considerfieldname*/false);
+            if (x) { return x; }
+            return l.second.compare(r.second);
+        }
+    private:
+        const Ordering _ordering;
+    };
+
+    // static
+    ExternalSortComparison* BtreeBasedBulkAccessMethod::getComparison(int version, const BSONObj& keyPattern) {
+        if (0 == version) {
+            return new BtreeExternalSortComparisonV0(keyPattern);
+        }
+        else if (1 == version) {
+            return new BtreeExternalSortComparisonV1(keyPattern);
+        }
+        verify( 0 );
+        return NULL;
+    }
+
+    BtreeBasedBulkAccessMethod::BtreeBasedBulkAccessMethod(BtreeBasedAccessMethod* real,
+                         transition::BtreeInterface* interface,
+                         const IndexDescriptor* descriptor,
+                         int numRecords) {
+
+        _real = real;
+        _interface = interface;
+
+        _docsInserted = 0;
+        _keysInserted = 0;
+        _isMultiKey = false;
+
+        _sortCmp.reset(getComparison(descriptor->version(), descriptor->keyPattern()));
+        _sorter.reset(new BSONObjExternalSorter(_sortCmp.get()));
+        _sorter->hintNumObjects(numRecords);
+    }
+
+    Status BtreeBasedBulkAccessMethod::insert(const BSONObj& obj,
+                             const DiskLoc& loc,
+                             const InsertDeleteOptions& options,
+                             int64_t* numInserted) {
+        BSONObjSet keys;
+        _real->getKeys(obj, &keys);
+
+        _isMultiKey = _isMultiKey || (keys.size() > 1);
+
+        for (BSONObjSet::iterator it = keys.begin(); it != keys.end(); ++it) {
+            // False is for mayInterrupt.
+            _sorter->add(*it, loc, false);
+            _keysInserted++;
+        }
+
+        _docsInserted++;
+
+        if (NULL != numInserted) {
+            *numInserted += keys.size();
+        }
+
+        return Status::OK();
+    }
+
+    Status BtreeBasedBulkAccessMethod::commit(set<DiskLoc>* dupsToDrop, CurOp* op, bool mayInterrupt) {
+        DiskLoc oldHead = _real->_btreeState->head();
+        // XXX: do we expect the tree to be empty but have a head set?  Looks like so from old code.
+        invariant(!oldHead.isNull());
+        _real->_btreeState->setHead(DiskLoc());
+        _real->_btreeState->recordStore()->deleteRecord(oldHead);
+
+        if (_isMultiKey) {
+            _real->_btreeState->setMultikey();
+        }
+
+        _sorter->sort(false);
+
+        Timer timer;
+        IndexCatalogEntry* entry = _real->_btreeState;
+
+        bool dupsAllowed = !entry->descriptor()->unique()
+                           || ignoreUniqueIndex(entry->descriptor());
+
+        bool dropDups = entry->descriptor()->dropDups() || inDBRepair;
+
+        scoped_ptr<BSONObjExternalSorter::Iterator> i(_sorter->iterator());
+
+        // verifies that pm and op refer to the same ProgressMeter
+        ProgressMeter& pm = op->setMessage("Index Bulk Build: (2/3) btree bottom up",
+                                           "Index: (2/3) BTree Bottom Up Progress",
+                                           _keysInserted,
+                                           10);
+
+        scoped_ptr<transition::BtreeBuilderInterface> builder;
+        builder.reset(_interface->getBulkBuilder(dupsAllowed));
+
+        while (i->more()) {
+            // Get the next datum and add it to the builder.
+            ExternalSortDatum d = i->next();
+            Status status = builder->addKey(d.first, d.second);
+
+            if (!status.isOK()) {
+                if (ErrorCodes::DuplicateKey != status.code()) {
+                    return status;
+                }
+
+                // If we're here it's a duplicate key.
+                if (dropDups) {
+                    static const size_t kMaxDupsToStore = 1000000;
+                    dupsToDrop->insert(d.second);
+                    if (dupsToDrop->size() > kMaxDupsToStore) {
+                        return Status(ErrorCodes::InternalError,
+                                      "Too many dups on index build with dropDups = true");
+                    }
+                }
+                else if (!dupsAllowed) {
+                    return status;
+                }
+            }
+
+            // If we're here either it's a dup and we're cool with it or the addKey went just
+            // fine.
+            pm.hit();
+        }
+
+        pm.finished();
+
+        op->setMessage("Index Bulk Build: (3/3) btree-middle",
+                       "Index: (3/3) BTree Middle Progress");
+
+        LOG(timer.seconds() > 10 ? 0 : 1 ) << "\t done building bottom layer, going to commit";
+
+        unsigned long long keysCommit = builder->commit(mayInterrupt);
+
+        if (!dropDups && (keysCommit != _keysInserted)) {
+            warning() << "not all entries were added to the index, probably some "
+                      << "keys were too large" << endl;
+        }
+        return Status::OK();
+    }
+
+}  // namespace mongo
diff --git a/src/mongo/db/index/btree_based_bulk_access_method.h b/src/mongo/db/index/btree_based_bulk_access_method.h
new file mode 100644
index 00000000000..16e72cfc60f
--- /dev/null
+++ b/src/mongo/db/index/btree_based_bulk_access_method.h
@@ -0,0 +1,140 @@
+/**
+*    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/>.
+*
+*    As a special exception, the copyright holders give permission to link the
+*    code of portions of this program with the OpenSSL library under certain
+*    conditions as described in each individual source file and distribute
+*    linked combinations including the program with the OpenSSL library. You
+*    must comply with the GNU Affero General Public License in all respects for
+*    all of the code used other than as permitted herein. If you modify file(s)
+*    with this exception, you may extend this exception to your version of the
+*    file(s), but you are not obligated to do so. If you do not wish to do so,
+*    delete this exception statement from your version. If you delete this
+*    exception statement from all source files in the program, then also delete
+*    it in the license file.
+*/
+
+#include <set>
+#include <vector>
+
+#include "mongo/base/error_codes.h"
+#include "mongo/base/status.h"
+#include "mongo/db/curop.h"
+#include "mongo/db/extsort.h"
+#include "mongo/db/index/btree_based_access_method.h"
+#include "mongo/db/index/index_access_method.h"
+#include "mongo/db/index/index_descriptor.h"
+#include "mongo/db/jsobj.h"
+#include "mongo/db/structure/btree/btree_interface.h"
+
+namespace mongo {
+
+    class BtreeBasedBulkAccessMethod : public IndexAccessMethod {
+    public:
+        BtreeBasedBulkAccessMethod(BtreeBasedAccessMethod* real,
+                                   transition::BtreeInterface* interface,
+                                   const IndexDescriptor* descriptor,
+                                   int numRecords);
+
+        ~BtreeBasedBulkAccessMethod() {}
+
+        virtual Status insert(const BSONObj& obj,
+                              const DiskLoc& loc,
+                              const InsertDeleteOptions& options,
+                              int64_t* numInserted);
+
+        Status commit(std::set<DiskLoc>* dupsToDrop, CurOp* op, bool mayInterrupt);
+
+        // Exposed for testing.
+        static ExternalSortComparison* getComparison(int version, const BSONObj& keyPattern);
+
+        //
+        // Stuff below here is a no-op of one form or another.
+        //
+
+        virtual Status commitBulk(IndexAccessMethod* bulk,
+                                  bool mayInterrupt,
+                                  std::set<DiskLoc>* dups) {
+            verify(this == bulk);
+            return Status::OK();
+        }
+
+        virtual Status touch(const BSONObj& obj) {
+            return _notAllowed();
+        }
+
+        virtual Status validate(int64_t* numKeys) {
+            return _notAllowed();
+        }
+
+        virtual Status remove(const BSONObj& obj,
+                              const DiskLoc& loc,
+                              const InsertDeleteOptions& options,
+                              int64_t* numDeleted) {
+            return _notAllowed();
+        }
+
+        virtual Status validateUpdate(const BSONObj& from,
+                                      const BSONObj& to,
+                                      const DiskLoc& loc,
+                                      const InsertDeleteOptions& options,
+                                      UpdateTicket* ticket) {
+            return _notAllowed();
+        }
+
+        virtual Status update(const UpdateTicket& ticket, int64_t* numUpdated) {
+            return _notAllowed();
+        }
+
+        virtual Status newCursor(IndexCursor **out) const {
+            return _notAllowed();
+        }
+
+        virtual Status initializeAsEmpty() {
+            return _notAllowed();
+        }
+
+        virtual IndexAccessMethod* initiateBulk() {
+            return NULL;
+        }
+
+    private:
+        Status _notAllowed() const {
+            return Status(ErrorCodes::InternalError, "cannot use bulk for this yet");
+        }
+
+        // Not owned here.
+        BtreeBasedAccessMethod* _real;
+
+        // Not owned here.
+        transition::BtreeInterface* _interface;
+
+        // The external sorter.
+        boost::scoped_ptr<BSONObjExternalSorter> _sorter;
+
+        // A comparison object required by the sorter.
+        boost::scoped_ptr<ExternalSortComparison> _sortCmp;
+
+        // How many docs are we indexing?
+        unsigned long long _docsInserted;
+
+        // And how many keys?
+        unsigned long long _keysInserted;
+
+        // Does any document have >1 key?
+        bool _isMultiKey;
+    };
+
+}  // namespace mongo
diff --git a/src/mongo/db/index/hash_access_method.cpp b/src/mongo/db/index/hash_access_method.cpp
index 34729a1cf77..7457c68c085 100644
--- a/src/mongo/db/index/hash_access_method.cpp
+++ b/src/mongo/db/index/hash_access_method.cpp
@@ -26,7 +26,6 @@
 *    it in the license file.
 */
 
-#include "mongo/db/structure/btree/btree.h"
 #include "mongo/db/hasher.h"
 #include "mongo/db/index/expression_keys_private.h"
 #include "mongo/db/index/expression_params.h"
diff --git a/src/mongo/db/pdfile.cpp b/src/mongo/db/pdfile.cpp
index 4cc0552ebc0..e02008ae18c 100644
--- a/src/mongo/db/pdfile.cpp
+++ b/src/mongo/db/pdfile.cpp
@@ -69,7 +69,6 @@ _ disallow system* manipulations from the database.
 #include "mongo/db/ops/delete.h"
 #include "mongo/db/repair_database.h"
 #include "mongo/db/repl/is_master.h"
-#include "mongo/db/sort_phase_one.h"
 #include "mongo/db/repl/oplog.h"
 #include "mongo/db/storage_options.h"
 #include "mongo/db/catalog/collection.h"
diff --git a/src/mongo/db/query/idhack_runner.cpp b/src/mongo/db/query/idhack_runner.cpp
index e4cc486d35d..c57aee98ec2 100644
--- a/src/mongo/db/query/idhack_runner.cpp
+++ b/src/mongo/db/query/idhack_runner.cpp
@@ -29,7 +29,7 @@
 #include "mongo/db/query/idhack_runner.h"
 
 #include "mongo/client/dbclientinterface.h"
-#include "mongo/db/structure/btree/btree.h"
+#include "mongo/db/catalog/collection.h"
 #include "mongo/db/catalog/index_catalog.h"
 #include "mongo/db/diskloc.h"
 #include "mongo/db/index/btree_access_method.h"
@@ -39,7 +39,7 @@
 #include "mongo/db/query/canonical_query.h"
 #include "mongo/db/query/type_explain.h"
 #include "mongo/db/query/plan_executor.h"
-#include "mongo/db/catalog/collection.h"
+#include "mongo/db/storage/record.h"
 #include "mongo/s/d_logic.h"
 
 namespace {
diff --git a/src/mongo/db/sort_phase_one.h b/src/mongo/db/sort_phase_one.h
deleted file mode 100644
index a0aade9a731..00000000000
--- a/src/mongo/db/sort_phase_one.h
+++ /dev/null
@@ -1,59 +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/>.
-*
-*    As a special exception, the copyright holders give permission to link the
-*    code of portions of this program with the OpenSSL library under certain
-*    conditions as described in each individual source file and distribute
-*    linked combinations including the program with the OpenSSL library. You
-*    must comply with the GNU Affero General Public License in all respects for
-*    all of the code used other than as permitted herein. If you modify file(s)
-*    with this exception, you may extend this exception to your version of the
-*    file(s), but you are not obligated to do so. If you do not wish to do so,
-*    delete this exception statement from your version. If you delete this
-*    exception statement from all source files in the program, then also delete
-*    it in the license file.
-*/
-
-#pragma once
-
-#include "mongo/db/extsort.h"
-
-namespace mongo {
-
-    /** for bottom up fastbuildindex (where we presort keys) */
-    struct SortPhaseOne {
-        SortPhaseOne() {
-            n = 0;
-            nkeys = 0;
-            multi = false;
-        }
-        shared_ptr<BSONObjExternalSorter> sorter;
-        shared_ptr<ExternalSortComparison> sortCmp;
-
-        unsigned long long n; // # of records
-        unsigned long long nkeys;
-        bool multi; // multikey index
-
-        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;
-        }
-    };
-
-}  // namespace mongo
diff --git a/src/mongo/db/structure/btree/btree.cpp b/src/mongo/db/structure/btree/btree.cpp
index 0f7f8089155..4537f73d8d9 100644
--- a/src/mongo/db/structure/btree/btree.cpp
+++ b/src/mongo/db/structure/btree/btree.cpp
@@ -33,7 +33,6 @@
 #include "mongo/db/structure/btree/btree.h"
 
 #include "mongo/db/structure/btree/btree_stats.h"
-#include "mongo/db/structure/btree/btreebuilder.h"
 #include "mongo/db/client.h"
 #include "mongo/db/clientcursor.h"
 #include "mongo/db/curop-inl.h"
diff --git a/src/mongo/db/structure/btree/btree_interface.cpp b/src/mongo/db/structure/btree/btree_interface.cpp
index a7fc44f6e77..397ef12c453 100644
--- a/src/mongo/db/structure/btree/btree_interface.cpp
+++ b/src/mongo/db/structure/btree/btree_interface.cpp
@@ -34,6 +34,26 @@ namespace mongo {
 namespace transition {
 
     template <class OnDiskFormat>
+    class BtreeBuilderInterfaceImpl : public BtreeBuilderInterface {
+    public:
+        BtreeBuilderInterfaceImpl(typename BtreeLogic<OnDiskFormat>::Builder* builder)
+            : _builder(builder) { }
+
+        virtual ~BtreeBuilderInterfaceImpl() { }
+
+        Status addKey(const BSONObj& key, const DiskLoc& loc) {
+            return _builder->addKey(key, loc);
+        }
+
+        unsigned long long commit(bool mayInterrupt) {
+            return _builder->commit(mayInterrupt);
+        }
+
+    private:
+        typename BtreeLogic<OnDiskFormat>::Builder* _builder;
+    };
+
+    template <class OnDiskFormat>
     class BtreeInterfaceImpl : public BtreeInterface {
     public:
         BtreeInterfaceImpl(HeadManager* headManager,
@@ -45,6 +65,10 @@ namespace transition {
 
         virtual ~BtreeInterfaceImpl() { }
 
+        virtual BtreeBuilderInterface* getBulkBuilder(bool dupsAllowed) {
+            return new BtreeBuilderInterfaceImpl<OnDiskFormat>(_btree->newBuilder(dupsAllowed));
+        }
+
         virtual Status insert(const BSONObj& key, const DiskLoc& loc, bool dupsAllowed) {
             return _btree->insert(key, loc, dupsAllowed);
         }
@@ -140,6 +164,10 @@ namespace transition {
             _btree->restorePosition(saved.key, saved.loc, direction, bucketInOut, keyOffsetInOut);
         }
 
+        virtual Status initAsEmpty() {
+            return _btree->initAsEmpty();
+        }
+
     private:
         scoped_ptr<BtreeLogic<OnDiskFormat> > _btree;
     };
diff --git a/src/mongo/db/structure/btree/btree_interface.h b/src/mongo/db/structure/btree/btree_interface.h
index 9b5d32fcca2..3073867b494 100644
--- a/src/mongo/db/structure/btree/btree_interface.h
+++ b/src/mongo/db/structure/btree/btree_interface.h
@@ -38,6 +38,30 @@ namespace mongo {
 namespace transition {
 
     /**
+     * A version-hiding wrapper around the bulk builder for the Btree.
+     */
+    class BtreeBuilderInterface {
+    public:
+        virtual ~BtreeBuilderInterface() { }
+
+        /**
+         * Adds 'key' to intermediate storage.
+         *
+         * 'key' must be > or >= the last key passed to this function (depends on _dupsAllowed).  If
+         * this is violated an error Status (ErrorCodes::InternalError) will be returned.
+         */
+        virtual Status addKey(const BSONObj& key, const DiskLoc& loc) = 0;
+
+        /**
+         * commit work.  if not called, destructor will clean up partially completed work
+         *  (in case exception has happened).
+         *
+         * Returns number of keys added.
+         */
+        virtual unsigned long long commit(bool mayInterrupt) = 0;
+    };
+
+    /**
      * This is the interface for interacting with the Btree.  The index access and catalog layers
      * should use this.
      *
@@ -68,6 +92,12 @@ namespace transition {
         // Data changes
         //
 
+        /**
+         * Caller owns returned pointer.
+         * 'this' must outlive the returned pointer.
+         */
+        virtual BtreeBuilderInterface* getBulkBuilder(bool dupsAllowed) = 0;
+
         virtual Status insert(const BSONObj& key, const DiskLoc& loc, bool dupsAllowed) = 0;
 
         virtual bool unindex(const BSONObj& key, const DiskLoc& loc) = 0;
@@ -136,6 +166,12 @@ namespace transition {
                                      int direction,
                                      DiskLoc* bucketOut,
                                      int* keyOffsetOut) = 0;
+
+        //
+        // Index creation
+        //
+
+        virtual Status initAsEmpty() = 0;
     };
 
 }  // namespace transition
diff --git a/src/mongo/db/structure/btree/btree_logic.cpp b/src/mongo/db/structure/btree/btree_logic.cpp
index bbc437cd85d..b9fd42319d0 100644
--- a/src/mongo/db/structure/btree/btree_logic.cpp
+++ b/src/mongo/db/structure/btree/btree_logic.cpp
@@ -28,18 +28,180 @@
 
 
 #include "mongo/db/diskloc.h"
-#include "mongo/db/storage/mmap_v1/dur.h"
-#include "mongo/db/storage/mmap_v1/dur_commitjob.h"
 #include "mongo/db/index/btree_index_cursor.h"  // for aboutToDeleteBucket
 #include "mongo/db/jsobj.h"
+#include "mongo/db/kill_current_op.h"
+#include "mongo/db/storage/mmap_v1/dur.h"
+#include "mongo/db/storage/mmap_v1/dur_commitjob.h"
 #include "mongo/db/storage/record.h"
-#include "mongo/db/structure/record_store.h"
 #include "mongo/db/structure/btree/btree_logic.h"
 #include "mongo/db/structure/btree/key.h"
+#include "mongo/db/structure/record_store.h"
 
 namespace mongo {
 namespace transition {
 
+    //
+    // Public Builder logic
+    //
+
+    template <class BtreeLayout>
+    typename BtreeLogic<BtreeLayout>::Builder*
+    BtreeLogic<BtreeLayout>::newBuilder(bool dupsAllowed) {
+        return new Builder(this, dupsAllowed);
+    }
+
+    template <class BtreeLayout>
+    BtreeLogic<BtreeLayout>::Builder::Builder(BtreeLogic* logic, bool dupsAllowed)
+        : _logic(logic),
+          _dupsAllowed(dupsAllowed),
+          _numAdded(0) {
+
+        _first = _cur = _logic->addBucket();
+        _b = _getModifiableBucket(_cur);
+        _committed = false;
+    }
+
+    template <class BtreeLayout>
+    Status BtreeLogic<BtreeLayout>::Builder::addKey(const BSONObj& keyObj, const DiskLoc& loc) {
+        auto_ptr<KeyDataOwnedType> key(new KeyDataOwnedType(keyObj));
+
+        if (key->dataSize() > BtreeLayout::KeyMax) {
+            string msg = str::stream() << "Btree::insert: key too large to index, failing "
+                                       << _logic->_recordStore->name()
+                                       << ' ' << key->dataSize() << ' ' << key->toString();
+            problem() << msg << endl;
+            return Status(ErrorCodes::KeyTooLong, msg);
+        }
+
+        // If we have a previous key to compare to...
+        if (_numAdded > 0) {
+            int cmp = _keyLast->woCompare(*key, _logic->_ordering);
+
+            // This shouldn't happen ever.  We expect keys in sorted order.
+            if (cmp > 0) {
+                return Status(ErrorCodes::InternalError, "Bad key order in btree builder");
+            }
+
+            // This could easily happen..
+            if (!_dupsAllowed && (cmp == 0)) {
+                return Status(ErrorCodes::DuplicateKey, _logic->dupKeyError(*_keyLast));
+            }
+        }
+
+        if (!_logic->_pushBack(_b, loc, *key, DiskLoc())) {
+            // bucket was full
+            newBucket();
+            _logic->pushBack(_b, loc, *key, DiskLoc());
+        }
+
+        _keyLast = key;
+        _numAdded++;
+        mayCommitProgressDurably();
+        return Status::OK();
+    }
+
+    template <class BtreeLayout>
+    unsigned long long BtreeLogic<BtreeLayout>::Builder::commit(bool mayInterrupt) {
+        buildNextLevel(_first, mayInterrupt);
+        _committed = true;
+        return _numAdded;
+    }
+
+    //
+    // Private Builder logic
+    //
+
+    template <class BtreeLayout>
+    void BtreeLogic<BtreeLayout>::Builder::newBucket() {
+        DiskLoc newBucketLoc = _logic->addBucket();
+        _b->parent = newBucketLoc;
+        _cur = newBucketLoc;
+        _b = _getModifiableBucket(_cur);
+    }
+
+    template <class BtreeLayout>
+    void BtreeLogic<BtreeLayout>::Builder::buildNextLevel(DiskLoc loc, bool mayInterrupt) {
+        for (;;) {
+            if (_getBucket(loc)->parent.isNull()) {
+                // only 1 bucket at this level. we are done.
+                _logic->_headManager->setHead(loc);
+                break;
+            }
+
+            DiskLoc upLoc = _logic->addBucket();
+            DiskLoc upStart = upLoc;
+            BucketType* up = _getModifiableBucket(upLoc);
+
+            DiskLoc xloc = loc;
+            while (!xloc.isNull()) {
+                if (getDur().commitIfNeeded()) {
+                    _b = _getModifiableBucket(_cur);
+                    up = _getModifiableBucket(upLoc);
+                }
+
+                if (mayInterrupt) {
+                    killCurrentOp.checkForInterrupt();
+                }
+
+                BucketType* x = _getModifiableBucket(xloc);
+                KeyDataType k;
+                DiskLoc r;
+                _logic->popBack(x, &r, &k);
+                bool keepX = (x->n != 0);
+                DiskLoc keepLoc = keepX ? xloc : x->nextChild;
+
+                if (!_logic->_pushBack(up, r, k, keepLoc)) {
+                    // current bucket full
+                    DiskLoc n = _logic->addBucket();
+                    up->parent = n;
+                    upLoc = n;
+                    up = _getModifiableBucket(upLoc);
+                    _logic->pushBack(up, r, k, keepLoc);
+                }
+
+                DiskLoc nextLoc = x->parent;
+                if (keepX) {
+                    x->parent = upLoc;
+                }
+                else {
+                    if (!x->nextChild.isNull()) {
+                        DiskLoc ll = x->nextChild;
+                        _getModifiableBucket(ll)->parent = upLoc;
+                    }
+                    _logic->deallocBucket(x, xloc);
+                }
+                xloc = nextLoc;
+            }
+
+            loc = upStart;
+            mayCommitProgressDurably();
+        }
+    }
+
+    template <class BtreeLayout>
+    void BtreeLogic<BtreeLayout>::Builder::mayCommitProgressDurably() {
+        if (getDur().commitIfNeeded()) {
+            _b = _getModifiableBucket(_cur);
+        }
+    }
+
+    template <class BtreeLayout>
+    typename BtreeLogic<BtreeLayout>::BucketType*
+    BtreeLogic<BtreeLayout>::Builder::_getModifiableBucket(DiskLoc loc) {
+        return _logic->btreemod(_logic->getBucket(loc));
+    }
+
+    template <class BtreeLayout>
+    typename BtreeLogic<BtreeLayout>::BucketType*
+    BtreeLogic<BtreeLayout>::Builder::_getBucket(DiskLoc loc) {
+        return _logic->getBucket(loc);
+    }
+
+    //
+    // BtreeLogic logic
+    //
+
     // static
     template <class BtreeLayout>
     typename BtreeLogic<BtreeLayout>::FullKey
@@ -175,8 +337,8 @@ namespace transition {
 
     template <class BtreeLayout>
     void BtreeLogic<BtreeLayout>::popBack(BucketType* bucket,
-                                           DiskLoc* recordLocOut,
-                                           KeyDataType *keyDataOut) {
+                                          DiskLoc* recordLocOut,
+                                          KeyDataType *keyDataOut) {
 
         massert(17435,  "n==0 in btree popBack()", bucket->n > 0 );
 
@@ -1632,6 +1794,16 @@ namespace transition {
     };
 
     template <class BtreeLayout>
+    Status BtreeLogic<BtreeLayout>::initAsEmpty() {
+        if (!_headManager->getHead().isNull()) {
+            return Status(ErrorCodes::InternalError, "index already initialized");
+        }
+
+        _headManager->setHead(addBucket());
+        return Status::OK();
+    }
+
+    template <class BtreeLayout>
     DiskLoc BtreeLogic<BtreeLayout>::addBucket() {
         DummyDocWriter docWriter(BtreeLayout::BucketSize);
         StatusWith<DiskLoc> loc = _recordStore->insertRecord(&docWriter, 0);
diff --git a/src/mongo/db/structure/btree/btree_logic.h b/src/mongo/db/structure/btree/btree_logic.h
index 4238d07d443..c5808b17ce3 100644
--- a/src/mongo/db/structure/btree/btree_logic.h
+++ b/src/mongo/db/structure/btree/btree_logic.h
@@ -71,6 +71,48 @@ namespace transition {
         // Public-facing
         //
 
+        class Builder {
+        public:
+            typedef typename BtreeLayout::KeyOwnedType KeyDataOwnedType;
+            typedef typename BtreeLayout::KeyType KeyDataType;
+
+            Status addKey(const BSONObj& key, const DiskLoc& loc);
+
+            // XXX: status, outparam for # keys?
+            unsigned long long commit(bool mayInterrupt);
+
+        private:
+            friend class BtreeLogic;
+
+            Builder(BtreeLogic* logic, bool dupsAllowed);
+
+            // Direct ports of functionality
+            void newBucket();
+            void buildNextLevel(DiskLoc loc, bool mayInterrupt);
+            void mayCommitProgressDurably();
+            BucketType* _getModifiableBucket(DiskLoc loc);
+            BucketType* _getBucket(DiskLoc loc);
+            // Direct ports of functionality
+
+            // Not owned.
+            BtreeLogic* _logic;
+
+            // Direct port of names.
+            DiskLoc _cur;
+            DiskLoc _first;
+            BucketType* _b;
+            bool _committed;
+            bool _dupsAllowed;
+            long long _numAdded;
+            auto_ptr<KeyDataOwnedType> _keyLast;
+        };
+
+        /**
+         * Caller owns the returned pointer.
+         * 'this' must outlive the returned pointer.
+         */
+        Builder* newBuilder(bool dupsAllowed);
+
         Status dupKeyCheck(const BSONObj& key, const DiskLoc& loc) const;
 
         Status insert(const BSONObj& rawKey, const DiskLoc& value, bool dupsAllowed);
@@ -137,9 +179,19 @@ namespace transition {
                      const DiskLoc& savedLoc,
                      BucketType* bucket,
                      int keyPos) const;
-                     
+
+        //
+        // Creation and deletion
+        //
+
+        /**
+         * Returns OK if the index was uninitialized before, error status otherwise.
+         */
+        Status initAsEmpty();
 
     private:
+        friend class BtreeLogic::Builder;
+
         /**
          * This is an in memory wrapper for the variable length data associated with a
          * KeyHeaderType.  It points to on-disk data but is not itself on-disk data.
diff --git a/src/mongo/db/structure/btree/btreebuilder.cpp b/src/mongo/db/structure/btree/btreebuilder.cpp
deleted file mode 100644
index fe750ecb234..00000000000
--- a/src/mongo/db/structure/btree/btreebuilder.cpp
+++ /dev/null
@@ -1,197 +0,0 @@
-// btreebuilder.cpp
-
-/**
-*    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/>.
-*
-*    As a special exception, the copyright holders give permission to link the
-*    code of portions of this program with the OpenSSL library under certain
-*    conditions as described in each individual source file and distribute
-*    linked combinations including the program with the OpenSSL library. You
-*    must comply with the GNU Affero General Public License in all respects for
-*    all of the code used other than as permitted herein. If you modify file(s)
-*    with this exception, you may extend this exception to your version of the
-*    file(s), but you are not obligated to do so. If you do not wish to do so,
-*    delete this exception statement from your version. If you delete this
-*    exception statement from all source files in the program, then also delete
-*    it in the license file.
-*/
-
-#include "mongo/pch.h"
-
-#include "mongo/db/structure/btree/btreebuilder.h"
-
-#include "mongo/db/client.h"
-#include "mongo/db/clientcursor.h"
-#include "mongo/db/curop-inl.h"
-#include "mongo/db/db.h"
-#include "mongo/db/dbhelpers.h"
-#include "mongo/db/storage/mmap_v1/dur_commitjob.h"
-#include "mongo/db/json.h"
-#include "mongo/db/kill_current_op.h"
-#include "mongo/db/pdfile.h"
-#include "mongo/db/repl/is_master.h"
-#include "mongo/db/stats/counters.h"
-#include "mongo/db/structure/btree/btree.h"
-
-namespace mongo {
-
-    void keyTooLongAssert( int code, const string& msg );
-
-    /* --- BtreeBuilder --- */
-
-    template<class V>
-    BtreeBuilder<V>::BtreeBuilder(bool dupsAllowed, IndexCatalogEntry* btreeState ):
-        _dupsAllowed(dupsAllowed),
-        _btreeState(btreeState),
-        _numAdded(0) {
-        first = cur = BtreeBucket<V>::addBucket(btreeState);
-        b = _getModifiableBucket( cur );
-        committed = false;
-    }
-
-    template<class V>
-    BtreeBucket<V>* BtreeBuilder<V>::_getModifiableBucket( DiskLoc loc ) {
-        return BtreeBucket<V>::asVersionMod( _btreeState->recordStore()->recordFor( loc ) );
-    }
-
-    template<class V>
-    const BtreeBucket<V>* BtreeBuilder<V>::_getBucket( DiskLoc loc ) {
-        return BtreeBucket<V>::asVersion( _btreeState->recordStore()->recordFor( loc ) );
-    }
-
-    template<class V>
-    void BtreeBuilder<V>::newBucket() {
-        DiskLoc L = BtreeBucket<V>::addBucket(_btreeState);
-        b->setTempNext(L);
-        cur = L;
-        b = _getModifiableBucket( cur );
-    }
-
-    template<class V>
-    void BtreeBuilder<V>::mayCommitProgressDurably() {
-        if ( getDur().commitIfNeeded() ) {
-            b = _getModifiableBucket( cur );
-        }
-    }
-
-    template<class V>
-    void BtreeBuilder<V>::addKey(BSONObj& _key, DiskLoc loc) {
-        auto_ptr< KeyOwned > key( new KeyOwned(_key) );
-        if ( key->dataSize() > BtreeBucket<V>::KeyMax ) {
-            string msg = str::stream() << "Btree::insert: key too large to index, failing "
-                                       << _btreeState->descriptor()->indexNamespace()
-                                       << ' ' << key->dataSize() << ' ' << key->toString();
-            problem() << msg << endl;
-            keyTooLongAssert( 17282, msg );
-            return;
-        }
-
-        if( !_dupsAllowed ) {
-            if( _numAdded > 0 ) {
-                int cmp = keyLast->woCompare(*key, _btreeState->ordering());
-                massert( 10288 ,  "bad key order in BtreeBuilder - server internal error", cmp <= 0 );
-                if( cmp == 0 ) {
-                    //if( !dupsAllowed )
-                    uasserted( ASSERT_ID_DUPKEY, BtreeBucket<V>::dupKeyError( _btreeState->descriptor(),
-                                                                              *keyLast ) );
-                }
-            }
-        }
-
-        if ( ! b->_pushBack(loc, *key, _btreeState->ordering(), DiskLoc()) ) {
-            // bucket was full
-            newBucket();
-            b->pushBack(loc, *key, _btreeState->ordering(), DiskLoc());
-        }
-        keyLast = key;
-        _numAdded++;
-        mayCommitProgressDurably();
-    }
-
-    template<class V>
-    void BtreeBuilder<V>::buildNextLevel(DiskLoc loc, bool mayInterrupt) {
-        int levels = 1;
-        while( 1 ) {
-            if( _getBucket(loc)->tempNext().isNull() ) {
-                // only 1 bucket at this level. we are done.
-                _btreeState->setHead( loc );
-                break;
-            }
-            levels++;
-
-            DiskLoc upLoc = BtreeBucket<V>::addBucket(_btreeState);
-            DiskLoc upStart = upLoc;
-            BtreeBucket<V> *up = _getModifiableBucket( upLoc );
-
-            DiskLoc xloc = loc;
-            while( !xloc.isNull() ) {
-
-                if ( getDur().commitIfNeeded() ) {
-                    b = _getModifiableBucket( cur );
-                    up = _getModifiableBucket( upLoc );
-                }
-                RARELY if ( mayInterrupt ) killCurrentOp.checkForInterrupt();
-
-                BtreeBucket<V> *x = _getModifiableBucket( xloc );
-                Key k;
-                DiskLoc r;
-                x->popBack(r,k);
-                bool keepX = ( x->n != 0 );
-                DiskLoc keepLoc = keepX ? xloc : x->nextChild;
-
-                if ( ! up->_pushBack(r, k, _btreeState->ordering(), keepLoc) ) {
-                    // current bucket full
-                    DiskLoc n = BtreeBucket<V>::addBucket(_btreeState);
-                    up->setTempNext(n);
-                    upLoc = n;
-                    up = _getModifiableBucket( upLoc );
-                    up->pushBack(r, k, _btreeState->ordering(), keepLoc);
-                }
-
-                DiskLoc nextLoc = x->tempNext(); // get next in chain at current level
-                if ( keepX ) {
-                    x->parent = upLoc;
-                }
-                else {
-                    if ( !x->nextChild.isNull() ) {
-                        DiskLoc ll = x->nextChild;
-                        _getModifiableBucket(ll)->parent = upLoc;
-                        //(x->nextChild.btreemod<V>())->parent = upLoc;
-                    }
-                    x->deallocBucket( _btreeState, xloc );
-                }
-                xloc = nextLoc;
-            }
-
-            loc = upStart;
-            mayCommitProgressDurably();
-        }
-
-        if( levels > 1 ) {
-            LOG(2) << "btree levels: " << levels << endl;
-        }
-    }
-
-    /** when all addKeys are done, we then build the higher levels of the tree */
-    template<class V>
-    void BtreeBuilder<V>::commit(bool mayInterrupt) {
-        buildNextLevel(first, mayInterrupt);
-        committed = true;
-    }
-
-    template class BtreeBuilder<V0>;
-    template class BtreeBuilder<V1>;
-
-}
diff --git a/src/mongo/db/structure/btree/btreebuilder.h b/src/mongo/db/structure/btree/btreebuilder.h
deleted file mode 100644
index 833fbaabaff..00000000000
--- a/src/mongo/db/structure/btree/btreebuilder.h
+++ /dev/null
@@ -1,85 +0,0 @@
-/**
-*    Copyright (C) 2012 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/>.
-*
-*    As a special exception, the copyright holders give permission to link the
-*    code of portions of this program with the OpenSSL library under certain
-*    conditions as described in each individual source file and distribute
-*    linked combinations including the program with the OpenSSL library. You
-*    must comply with the GNU Affero General Public License in all respects for
-*    all of the code used other than as permitted herein. If you modify file(s)
-*    with this exception, you may extend this exception to your version of the
-*    file(s), but you are not obligated to do so. If you do not wish to do so,
-*    delete this exception statement from your version. If you delete this
-*    exception statement from all source files in the program, then also delete
-*    it in the license file.
-*/
-
-#pragma once
-
-#include "mongo/db/structure/btree/btree.h"
-
-namespace mongo {
-
-    class IndexCatalogEntry;
-
-    /**
-     * build btree from the bottom up
-     */
-    template< class V >
-    class BtreeBuilder {
-        typedef typename V::KeyOwned KeyOwned;
-        typedef typename V::Key Key;
-
-        bool _dupsAllowed;
-        IndexCatalogEntry* _btreeState;
-        /** Number of keys added to btree. */
-        unsigned long long _numAdded;
-
-        /** Last key passed to addKey(). */
-        auto_ptr< typename V::KeyOwned > keyLast;
-
-        /** true iff commit() completed successfully. */
-        bool committed;
-
-        DiskLoc cur, first;
-        BtreeBucket<V> *b;
-
-        void newBucket();
-        void buildNextLevel(DiskLoc loc, bool mayInterrupt);
-        void mayCommitProgressDurably();
-
-        BtreeBucket<V>* _getModifiableBucket( DiskLoc loc );
-        const BtreeBucket<V>* _getBucket( DiskLoc loc );
-
-
-    public:
-        BtreeBuilder(bool dupsAllowed, IndexCatalogEntry* idx);
-
-        /**
-         * Preconditions: 'key' is > or >= last key passed to this function (depends on _dupsAllowed)
-         * Postconditions: 'key' is added to intermediate storage.
-         */
-        void addKey(BSONObj& key, DiskLoc loc);
-
-        /**
-         * commit work.  if not called, destructor will clean up partially completed work
-         *  (in case exception has happened).
-         */
-        void commit(bool mayInterrupt);
-
-        unsigned long long getn() { return _numAdded; }
-    };
-
-}
diff --git a/src/mongo/dbtests/btreebuildertests.cpp b/src/mongo/dbtests/btreebuildertests.cpp
index fd7f49900ee..9ff1378ce4e 100644
--- a/src/mongo/dbtests/btreebuildertests.cpp
+++ b/src/mongo/dbtests/btreebuildertests.cpp
@@ -28,7 +28,7 @@
  *    then also delete it in the license file.
  */
 
-#include "mongo/db/structure/btree/btreebuilder.h"
+// #include "mongo/db/structure/btree/btreebuilder.h"
 
 #include "mongo/db/catalog/index_catalog.h"
 #include "mongo/db/pdfile.h"
diff --git a/src/mongo/dbtests/extsorttests.cpp b/src/mongo/dbtests/extsorttests.cpp
index dc807bdd28b..aec478aadc4 100644
--- a/src/mongo/dbtests/extsorttests.cpp
+++ b/src/mongo/dbtests/extsorttests.cpp
@@ -32,7 +32,7 @@
 
 #include "mongo/db/catalog/database.h"
 #include "mongo/db/extsort.h"
-#include "mongo/db/index/btree_based_access_method.h"
+#include "mongo/db/index/btree_based_bulk_access_method.h"
 #include "mongo/db/catalog/collection.h"
 #include "mongo/dbtests/dbtests.h"
 #include "mongo/platform/cstdint.h"
@@ -52,8 +52,8 @@ namespace ExtSortTests {
 
     static const char* const _ns = "unittests.extsort";
     DBDirectClient _client;
-    ExternalSortComparison* _arbitrarySort = BtreeBasedAccessMethod::getComparison(time(0)%2, BSONObj());
-    ExternalSortComparison* _aFirstSort = BtreeBasedAccessMethod::getComparison(0, BSON("a" << 1));
+    ExternalSortComparison* _arbitrarySort = BtreeBasedBulkAccessMethod::getComparison(time(0)%2, BSONObj());
+    ExternalSortComparison* _aFirstSort = BtreeBasedBulkAccessMethod::getComparison(0, BSON("a" << 1));
 
     /** Sort four values. */
     class SortFour {
@@ -320,7 +320,7 @@ namespace ExtSortTests {
             coll->insertDocument( b.obj(), true );
             // Create a sorter with a max file size of only 10k, to trigger a file flush after a
             // relatively small number of inserts.
-            auto_ptr<ExternalSortComparison> cmp(BtreeBasedAccessMethod::getComparison(0,
+            auto_ptr<ExternalSortComparison> cmp(BtreeBasedBulkAccessMethod::getComparison(0,
                 BSON("a" << 1)));
             BSONObjExternalSorter sorter(cmp.get(), 10 * 1024 );
             // Register a request to kill the current operation.
diff --git a/src/mongo/dbtests/indexupdatetests.cpp b/src/mongo/dbtests/indexupdatetests.cpp
index a1d594fb201..d28edbf2ab4 100644
--- a/src/mongo/dbtests/indexupdatetests.cpp
+++ b/src/mongo/dbtests/indexupdatetests.cpp
@@ -31,10 +31,9 @@
 #include "mongo/db/structure/btree/btree.h"
 #include "mongo/db/catalog/index_catalog.h"
 #include "mongo/db/dbhelpers.h"
-#include "mongo/db/index/btree_based_access_method.h"
+#include "mongo/db/index/btree_based_bulk_access_method.h"
 #include "mongo/db/index/index_descriptor.h"
 #include "mongo/db/kill_current_op.h"
-#include "mongo/db/sort_phase_one.h"
 #include "mongo/db/catalog/collection.h"
 #include "mongo/platform/cstdint.h"
 
@@ -44,7 +43,7 @@ namespace IndexUpdateTests {
 
     static const char* const _ns = "unittests.indexupdate";
     DBDirectClient _client;
-    ExternalSortComparison* _aFirstSort = BtreeBasedAccessMethod::getComparison(0, BSON("a" << 1));
+    ExternalSortComparison* _aFirstSort = BtreeBasedBulkAccessMethod::getComparison(0, BSON("a" << 1));
 
     /**
      * Test fixture for a write locked test using collection _ns.  Includes functionality to