SERVER-13084 btree navigation should use new impl

9 files changed, 72 insertions, 553 deletions

diff --git a/src/mongo/db/index/2d_access_method.h b/src/mongo/db/index/2d_access_method.h
index 95937967522..70c2ee247c0 100644
--- a/src/mongo/db/index/2d_access_method.h
+++ b/src/mongo/db/index/2d_access_method.h
@@ -67,7 +67,6 @@ namespace mongo {
     class TwoDAccessMethod : public BtreeBasedAccessMethod {
     public:
         using BtreeBasedAccessMethod::_descriptor;
-        using BtreeBasedAccessMethod::_interface;
 
         TwoDAccessMethod(IndexCatalogEntry* btreeState);
         virtual ~TwoDAccessMethod() { }
diff --git a/src/mongo/db/index/btree_access_method.cpp b/src/mongo/db/index/btree_access_method.cpp
index 37558a40bdf..de518142267 100644
--- a/src/mongo/db/index/btree_access_method.cpp
+++ b/src/mongo/db/index/btree_access_method.cpp
@@ -32,7 +32,6 @@
 
 #include "mongo/base/status.h"
 #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"
diff --git a/src/mongo/db/index/btree_access_method.h b/src/mongo/db/index/btree_access_method.h
index cfe971d57c6..dbe1a7980af 100644
--- a/src/mongo/db/index/btree_access_method.h
+++ b/src/mongo/db/index/btree_access_method.h
@@ -51,7 +51,6 @@ namespace mongo {
         // Every Btree-based index needs these.  We put them in the BtreeBasedAccessMethod
         // superclass and subclasses (like this) can use them.
         using BtreeBasedAccessMethod::_descriptor;
-        using BtreeBasedAccessMethod::_interface;
 
         BtreeAccessMethod(IndexCatalogEntry* btreeState );
         virtual ~BtreeAccessMethod() { }
diff --git a/src/mongo/db/index/btree_based_access_method.cpp b/src/mongo/db/index/btree_based_access_method.cpp
index 1a94ab52c76..11b4b92f9c2 100644
--- a/src/mongo/db/index/btree_based_access_method.cpp
+++ b/src/mongo/db/index/btree_based_access_method.cpp
@@ -35,7 +35,6 @@
 #include "mongo/db/curop.h"
 #include "mongo/db/extsort.h"
 #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/kill_current_op.h"
@@ -54,8 +53,6 @@ namespace mongo {
         : _btreeState(btreeState), _descriptor(btreeState->descriptor()) {
 
         verify(0 == _descriptor->version() || 1 == _descriptor->version());
-        _interface = BtreeInterface::interfaces[_descriptor->version()];
-
         _newInterface.reset(transition::BtreeInterface::getInterface(btreeState->headManager(),
                                                                      btreeState->recordStore(),
                                                                      btreeState->ordering(),
@@ -144,7 +141,8 @@ namespace mongo {
     }
 
     Status BtreeBasedAccessMethod::newCursor(IndexCursor **out) const {
-        *out = new BtreeIndexCursor(_btreeState, _btreeState->head(), _interface);
+        *out = new BtreeIndexCursor(_btreeState->head(),
+                                    _newInterface.get());
         return Status::OK();
     }
 
@@ -213,9 +211,10 @@ namespace mongo {
         BSONObjSet keys;
         getKeys(obj, &keys);
 
-        transition::BtreeInterface::BtreeLocation loc;
+        DiskLoc loc;
+        int keyPos;
         for (BSONObjSet::const_iterator i = keys.begin(); i != keys.end(); ++i) {
-            _newInterface->locate(*i, DiskLoc(), 1, &loc);
+            _newInterface->locate(*i, DiskLoc(), 1, &loc, &keyPos);
         }
 
         return Status::OK();
diff --git a/src/mongo/db/index/btree_based_access_method.h b/src/mongo/db/index/btree_based_access_method.h
index 363845dbad7..f75d63ed042 100644
--- a/src/mongo/db/index/btree_based_access_method.h
+++ b/src/mongo/db/index/btree_based_access_method.h
@@ -33,7 +33,6 @@
 #include "mongo/base/disallow_copying.h"
 #include "mongo/db/diskloc.h"
 #include "mongo/db/jsobj.h"
-#include "mongo/db/index/btree_interface.h"
 #include "mongo/db/index/index_access_method.h"
 #include "mongo/db/index/index_cursor.h"
 #include "mongo/db/index/index_descriptor.h"
@@ -113,9 +112,6 @@ namespace mongo {
         IndexCatalogEntry* _btreeState; // owned by IndexCatalogEntry
         const IndexDescriptor* _descriptor;
 
-        // There are 2 types of Btree disk formats.  We put them both behind one interface.
-        BtreeInterface* _interface;
-
     private:
         bool removeOneKey(const BSONObj& key, const DiskLoc& loc);
 
diff --git a/src/mongo/db/index/btree_index_cursor.cpp b/src/mongo/db/index/btree_index_cursor.cpp
index be1472241f3..91bc8e9849e 100644
--- a/src/mongo/db/index/btree_index_cursor.cpp
+++ b/src/mongo/db/index/btree_index_cursor.cpp
@@ -39,16 +39,15 @@
 
 namespace mongo {
 
+    // We keep a list of active cursors so that when a btree's bucket is deleted we notify the
+    // cursors that are pointing into that bucket.  This will go away with finer grained locking.
     unordered_set<BtreeIndexCursor*> BtreeIndexCursor::_activeCursors;
     SimpleMutex BtreeIndexCursor::_activeCursorsMutex("active_btree_index_cursors");
 
-    // Go forward by default.
-    BtreeIndexCursor::BtreeIndexCursor(const IndexCatalogEntry* btreeState,
-                                       const DiskLoc head,
-                                       BtreeInterface *interface)
+    BtreeIndexCursor::BtreeIndexCursor(const DiskLoc head,
+                                       transition::BtreeInterface* newInterface)
         : _direction(1),
-          _btreeState(btreeState),
-          _interface(interface),
+          _interface(newInterface),
           _bucket(head),
           _keyOffset(0) {
 
@@ -85,39 +84,20 @@ namespace mongo {
     }
 
     Status BtreeIndexCursor::seek(const BSONObj& position) {
-        _keyOffset = 0;
-
-        // Unused out parameter.
-        bool found;
-
-        _bucket = _interface->locate( _btreeState,
-                                      _btreeState->head(),
-                                      position,
-                                      _keyOffset,
-                                      found,
-                                      1 == _direction ? minDiskLoc : maxDiskLoc,
-                                      _direction);
-
-        skipUnusedKeys();
-
+        _interface->locate(position, 
+                           1 == _direction ? minDiskLoc : maxDiskLoc,
+                           _direction,
+                           &_bucket,
+                           &_keyOffset);
         return Status::OK();
     }
 
     void BtreeIndexCursor::seek(const BSONObj& position, bool afterKey) {
-        _keyOffset = 0;
-
-        // Unused out parameter.
-        bool found;
-
-        // Find our key.
-        _bucket = _interface->locate(_btreeState,
-                                     _btreeState->head(),
-                                     position,
-                                     _keyOffset,
-                                     found,
-                                     afterKey ? maxDiskLoc : minDiskLoc,
-                                     1);
-        skipUnusedKeys();
+        _interface->locate(position, 
+                           afterKey ? maxDiskLoc : minDiskLoc,
+                           1,
+                           &_bucket,
+                           &_keyOffset);
     }
 
     bool BtreeIndexCursor::pointsAt(const BtreeIndexCursor& other) {
@@ -131,151 +111,73 @@ namespace mongo {
 
     Status BtreeIndexCursor::seek(const vector<const BSONElement*>& position,
                                   const vector<bool>& inclusive) {
-        pair<DiskLoc, int> ignored;
 
-        // Bucket is modified by customLocate.  Seeks start @ the root, so we set _bucket to the
-        // root here.
-        _bucket = _btreeState->head();
-        _keyOffset = 0;
+        BSONObj emptyObj;
 
-        _interface->customLocate(_btreeState,
-                                 _bucket,
-                                 _keyOffset,
-                                 _emptyObj,
-                                 0, false,
+        _interface->customLocate(&_bucket,
+                                 &_keyOffset,
+                                 emptyObj,
+                                 0,
+                                 false,
                                  position,
                                  inclusive,
-                                 (int)_direction,
-                                 ignored);
-
-        skipUnusedKeys();
-
+                                 _direction);
         return Status::OK();
     }
 
-    Status BtreeIndexCursor::skip(const BSONObj &keyBegin, int keyBeginLen, bool afterKey,
+    Status BtreeIndexCursor::skip(const BSONObj &keyBegin,
+                                  int keyBeginLen,
+                                  bool afterKey,
                                   const vector<const BSONElement*>& keyEnd,
                                   const vector<bool>& keyEndInclusive) {
-        _interface->advanceTo(_btreeState,
-                              _bucket,
-                              _keyOffset,
+
+        _interface->advanceTo(&_bucket,
+                              &_keyOffset,
                               keyBegin,
                               keyBeginLen,
                               afterKey,
                               keyEnd,
                               keyEndInclusive,
-                              (int)_direction);
-
-        skipUnusedKeys();
+                              _direction);
         return Status::OK();
     }
 
     BSONObj BtreeIndexCursor::getKey() const {
         verify(!_bucket.isNull());
-        return _interface->keyAt(_btreeState, _bucket, _keyOffset);
+        return _interface->getKey(_bucket, _keyOffset);
     }
 
     DiskLoc BtreeIndexCursor::getValue() const {
         verify(!_bucket.isNull());
-        return _interface->recordAt(_btreeState, _bucket, _keyOffset);
+        return _interface->getDiskLoc(_bucket, _keyOffset);
     }
 
-    void BtreeIndexCursor::next() { advance("BtreeIndexCursor::next"); skipUnusedKeys(); }
+    void BtreeIndexCursor::next() {
+        advance();
+    }
 
     Status BtreeIndexCursor::savePosition() {
-        if (!isEOF()) {
-            _savedKey = getKey().getOwned();
-            _savedLoc = getValue();
-            return Status::OK();
-        } else {
+        if (isEOF()) {
             return Status(ErrorCodes::IllegalOperation, "Can't save position when EOF");
         }
-    }
-
-    Status BtreeIndexCursor::restorePosition() {
-        // _keyOffset could be -1 if the bucket was deleted.  When buckets are deleted, the
-        // Btree calls a clientcursor function that calls down to all BTree buckets.  Really,
-        // this deletion thing should be kept BTree-internal.
-        if (_keyOffset >= 0) {
-            verify(!_savedKey.isEmpty());
-
-            try {
-                if (isSavedPositionValid()) { return Status::OK(); }
-                if (_keyOffset > 0) {
-                    --_keyOffset;
-                    // "we check one key earlier too, in case a key was just deleted.  this is
-                    // important so that multi updates are reasonably fast." -- btreecursor.cpp
-                    if (isSavedPositionValid()) { return Status::OK(); }
-                }
-                // Object isn't at the saved position.  Fall through to calling seek.
-            } catch (UserException& e) { 
-                // deletedBucketCode is what keyAt throws if the bucket was deleted.  Not a
-                // problem...
-                if (BtreeInterface::deletedBucketCode != e.getCode()) {
-                    return e.toStatus();
-                }
-                // Our bucket was deleted, so we look for the saved key.
-                DEV log() << "debug info: bucket was deleted" << endl;
-            }
-        }
-
-        // Our old position was invalidated (keyOfs was set to -1) or our saved position
-        // is no longer valid, so we must re-find.
-        RARELY log() << "key seems to have moved in the index, refinding. "
-            << _bucket.toString() << endl;
-
-        bool found;
-
-        // Why don't we just call seek?  Because we want to pass _savedLoc.
-        _bucket = _interface->locate(_btreeState,
-                                     _btreeState->head(),
-                                     _savedKey,
-                                     _keyOffset,
-                                     found,
-                                     _savedLoc,
-                                     _direction);
-
-        skipUnusedKeys();
 
+        _interface->savePosition(_bucket, _keyOffset, &_savedData);
         return Status::OK();
     }
 
-    string BtreeIndexCursor::toString() { return "I AM A BTREE INDEX CURSOR!\n"; }
-
-    void BtreeIndexCursor::skipUnusedKeys() {
-        int skipped = 0;
-
-        while (!isEOF() && !_interface->keyIsUsed(_btreeState, _bucket, _keyOffset)) {
-            advance("BtreeIndexCursor::skipUnusedKeys");
-            ++skipped;
-        }
-
-        if (skipped > 10) {
-            OCCASIONALLY log() << "btree unused skipped: " << skipped << endl;
-        }
+    Status BtreeIndexCursor::restorePosition() {
+        _interface->restorePosition(_savedData, _direction, &_bucket, &_keyOffset);
+        return Status::OK();
     }
 
-    bool BtreeIndexCursor::isSavedPositionValid() {
-        // We saved the key.  If it's in the same position we saved it from...
-        if (_interface->keyAt(_btreeState, _bucket, _keyOffset).binaryEqual(_savedKey)) {
-            // And the record it points to is the same record...
-            if (_interface->recordAt(_btreeState, _bucket, _keyOffset) == _savedLoc) {
-                // Success!  We found it.  However!
-                if (!_interface->keyIsUsed(_btreeState, _bucket, _keyOffset)) {
-                    // We could have been deleted but still exist as a "vacant" key, so skip
-                    // over any unused keys.
-                    skipUnusedKeys();
-                }
-                return true;
-            }
-        }
-
-        return false;
+    string BtreeIndexCursor::toString() {
+        // TODO: is this ever called?
+        return "I AM A BTREE INDEX CURSOR!\n";
     }
 
     // Move to the next/prev. key.  Used by normal getNext and also skipping unused keys.
-    void BtreeIndexCursor::advance(const char* caller) {
-        _bucket = _interface->advance(_btreeState, _bucket, _keyOffset, _direction, caller);
+    void BtreeIndexCursor::advance() {
+        _interface->advance(&_bucket, &_keyOffset, _direction);
     }
 
 }  // namespace mongo
diff --git a/src/mongo/db/index/btree_index_cursor.h b/src/mongo/db/index/btree_index_cursor.h
index 73a7923095e..2f9ab2ae494 100644
--- a/src/mongo/db/index/btree_index_cursor.h
+++ b/src/mongo/db/index/btree_index_cursor.h
@@ -33,9 +33,9 @@
 #include "mongo/base/status.h"
 #include "mongo/db/diskloc.h"
 #include "mongo/db/jsobj.h"
-#include "mongo/db/index/btree_interface.h"
 #include "mongo/db/index/index_cursor.h"
 #include "mongo/db/index/index_descriptor.h"
+#include "mongo/db/structure/btree/btree_interface.h"
 
 namespace mongo {
 
@@ -66,7 +66,9 @@ namespace mongo {
          */
         void seek(const BSONObj& position, bool afterKey);
 
-        Status skip(const BSONObj &keyBegin, int keyBeginLen, bool afterKey,
+        Status skip(const BSONObj& keyBegin,
+                    int keyBeginLen,
+                    bool afterKey,
                     const vector<const BSONElement*>& keyEnd,
                     const vector<bool>& keyEndInclusive);
 
@@ -91,42 +93,42 @@ namespace mongo {
         // We keep the constructor private and only allow the AM to create us.
         friend class BtreeBasedAccessMethod;
 
-        // For handling bucket deletion.
-        static unordered_set<BtreeIndexCursor*> _activeCursors;
-        static SimpleMutex _activeCursorsMutex;
-
         /**
-         * btreeState is the ICE of the Btree that we're going to traverse.
          * head is the head of the Btree.
          * interface is an abstraction to hide the fact that we have two types of Btrees.
          *
-         * Go forward by default.
+         * 'this' will forward by default.  Call setOptions to change this.
+         * XXX: put options in ctor(?)
          *
          * Intentionally private, we're friends with the only class allowed to call it.
          */
-        BtreeIndexCursor(const IndexCatalogEntry* btreeState,
-                         const DiskLoc head,
-                         BtreeInterface *interface);
-
-        void skipUnusedKeys();
+        BtreeIndexCursor(const DiskLoc head,
+                         transition::BtreeInterface* newInterface);
 
         bool isSavedPositionValid();
 
-        // Move to the next/prev. key.  Used by normal getNext and also skipping unused keys.
-        void advance(const char* caller);
+        /**
+         * Move to the next (or previous depending on the direction) key.  Used by normal getNext
+         * and also skipping unused keys.
+         */
+        void advance();
+
+        // For handling bucket deletion.
+        static unordered_set<BtreeIndexCursor*> _activeCursors;
+        static SimpleMutex _activeCursorsMutex;
 
         // For saving/restoring position.
-        BSONObj _savedKey;
-        DiskLoc _savedLoc;
-
-        BSONObj _emptyObj;
+        transition::BtreeInterface::SavedPositionData _savedData;
 
         int _direction;
-        const IndexCatalogEntry* _btreeState; // not-owned
-        BtreeInterface* _interface;
 
+        // Not owned here.
+        transition::BtreeInterface* _interface;
+
+        // TODO: Have some kind of BtreeInterface::BtreePosition to encapsulate this.
         // What are we looking at RIGHT NOW?  We look at a bucket.
         DiskLoc _bucket;
+
         // And we look at an offset in the bucket.
         int _keyOffset;
     };
diff --git a/src/mongo/db/index/btree_interface.cpp b/src/mongo/db/index/btree_interface.cpp
deleted file mode 100644
index cd06449d107..00000000000
--- a/src/mongo/db/index/btree_interface.cpp
+++ /dev/null
@@ -1,225 +0,0 @@
-/**
- *    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/catalog/index_catalog_entry.h"
-#include "mongo/db/index/btree_interface.h"
-#include "mongo/db/pdfile.h"
-#include "mongo/db/structure/btree/btree.h"
-#include "mongo/db/structure/record_store.h"
-
-namespace mongo {
-
-    template <class Version>
-    class BtreeInterfaceImpl : public BtreeInterface {
-    public:
-        virtual ~BtreeInterfaceImpl() { }
-
-        const BtreeBucket<Version>* getHeadBucket( const IndexCatalogEntry* entry ) const {
-            return getBucket( entry->head() );
-        }
-
-        const BtreeBucket<Version>* getBucket( const IndexCatalogEntry* entry,
-                                               const DiskLoc& loc ) const {
-            Record* record = entry->recordStore()->recordFor( loc );
-            return BtreeBucket<Version>::asVersion( record );
-        }
-
-        virtual int bt_insert(IndexCatalogEntry* btreeState,
-                              const DiskLoc thisLoc,
-                              const DiskLoc recordLoc,
-                              const BSONObj& key,
-                              bool dupsallowed,
-                              bool toplevel) {
-            // FYI: toplevel has a default value of true in btree.h
-            return getBucket( btreeState, thisLoc )->bt_insert(btreeState,
-                                                                      thisLoc,
-                                                                      recordLoc,
-                                                                      key,
-                                                                      dupsallowed,
-                                                                      toplevel);
-        }
-
-        virtual bool unindex(IndexCatalogEntry* btreeState,
-                             const DiskLoc thisLoc,
-                             const BSONObj& key,
-                             const DiskLoc recordLoc) {
-            return getBucket( btreeState, thisLoc )->unindex(btreeState,
-                                                                    thisLoc,
-                                                                    key,
-                                                                    recordLoc);
-        }
-
-        virtual DiskLoc locate(const IndexCatalogEntry* btreeState,
-                               const DiskLoc& thisLoc,
-                               const BSONObj& key,
-                               int& pos,
-                               bool& found,
-                               const DiskLoc& recordLoc,
-                               int direction) const {
-            // FYI: direction has a default of 1
-            return getBucket( btreeState, thisLoc )->locate(btreeState,
-                                                                   thisLoc,
-                                                                   key,
-                                                                   pos,
-                                                                   found,
-                                                                   recordLoc,
-                                                                   direction);
-        }
-
-        virtual bool wouldCreateDup(const IndexCatalogEntry* btreeState,
-                                    const DiskLoc& thisLoc,
-                                    const BSONObj& key,
-                                    const DiskLoc& self) const {
-            typename Version::KeyOwned ownedVersion(key);
-            return getBucket( btreeState, thisLoc )->wouldCreateDup(btreeState,
-                                                                           thisLoc,
-                                                                           ownedVersion,
-                                                                           self);
-        }
-
-        virtual void customLocate(const IndexCatalogEntry* btreeState,
-                                  DiskLoc& locInOut,
-                                  int& keyOfs,
-                                  const BSONObj& keyBegin,
-                                  int keyBeginLen, bool afterVersion,
-                                  const vector<const BSONElement*>& keyEnd,
-                                  const vector<bool>& keyEndInclusive,
-                                  int direction,
-                                  pair<DiskLoc, int>& bestParent) const {
-            return BtreeBucket<Version>::customLocate(btreeState,
-                                                      locInOut,
-                                                      keyOfs,
-                                                      keyBegin,
-                                                      keyBeginLen, afterVersion,
-                                                      keyEnd,
-                                                      keyEndInclusive,
-                                                      direction,
-                                                      bestParent);
-        }
-
-        virtual void advanceTo(const IndexCatalogEntry* btreeState,
-                               DiskLoc &thisLoc,
-                               int &keyOfs,
-                               const BSONObj &keyBegin,
-                               int keyBeginLen,
-                               bool afterVersion,
-                               const vector<const BSONElement*>& keyEnd,
-                               const vector<bool>& keyEndInclusive,
-                               int direction) const {
-            return getBucket( btreeState, thisLoc )->advanceTo(btreeState,
-                                                                      thisLoc,
-                                                                      keyOfs,
-                                                                      keyBegin,
-                                                                      keyBeginLen,
-                                                                      afterVersion,
-                                                                      keyEnd,
-                                                                      keyEndInclusive,
-                                                                      direction);
-        }
-
-
-        virtual int nKeys(const IndexCatalogEntry* btreeState,
-                          DiskLoc bucket ) {
-            return getBucket(btreeState,bucket)->nKeys();
-        }
-
-
-        virtual bool keyIsUsed(const IndexCatalogEntry* btreeState,
-                               DiskLoc bucket, int keyOffset) const {
-            return getBucket(btreeState,bucket)->k(keyOffset).isUsed();
-        }
-
-        virtual BSONObj keyAt(const IndexCatalogEntry* btreeState,
-                              DiskLoc bucket, int keyOffset) const {
-            verify(!bucket.isNull());
-            const BtreeBucket<Version> *b = getBucket(btreeState,bucket);
-            int n = b->getN();
-            if (n == b->INVALID_N_SENTINEL) {
-                throw UserException(deletedBucketCode, "keyAt bucket deleted");
-            }
-            dassert( n >= 0 && n < 10000 );
-            return keyOffset >= n ? BSONObj() : b->keyNode(keyOffset).key.toBson();
-        }
-
-        virtual DiskLoc recordAt(const IndexCatalogEntry* btreeState,
-                                 DiskLoc bucket, int keyOffset) const {
-            const BtreeBucket<Version> *b = getBucket(btreeState,bucket);
-            return b->keyNode(keyOffset).recordLoc;
-        }
-
-        virtual void keyAndRecordAt(const IndexCatalogEntry* btreeState,
-                                    DiskLoc bucket, int keyOffset, BSONObj* keyOut,
-                                    DiskLoc* recordOut) const {
-            verify(!bucket.isNull());
-            const BtreeBucket<Version> *b = getBucket(btreeState,bucket);
-
-            int n = b->getN();
-
-            // If n is 0xffff the bucket was deleted.
-            if (keyOffset < 0 || keyOffset >= n || n == 0xffff || !b->isUsed(keyOffset)) {
-                return;
-            }
-
-            if (keyOffset >= n) {
-                *keyOut = BSONObj();
-                *recordOut = DiskLoc();
-            } else {
-                *keyOut = b->keyNode(keyOffset).key.toBson();
-                *recordOut = b->keyNode(keyOffset).recordLoc;
-            }
-        }
-
-        virtual string dupKeyError(const IndexCatalogEntry* btreeState,
-                                   DiskLoc bucket,
-                                   const BSONObj& keyObj) const {
-            typename Version::KeyOwned key(keyObj);
-            return getBucket( btreeState, bucket )->dupKeyError(btreeState->descriptor(),
-                                                                key);
-        }
-
-        virtual DiskLoc advance(const IndexCatalogEntry* btreeState,
-                                const DiskLoc& thisLoc,
-                                int& keyOfs,
-                                int direction,
-                                const char* caller) const {
-            return getBucket( btreeState, thisLoc )->advance(thisLoc, keyOfs, direction, caller);
-        }
-
-        virtual long long fullValidate(const IndexCatalogEntry* btreeState,
-                                       const DiskLoc& thisLoc,
-                                       const BSONObj& keyPattern) {
-            return getBucket( btreeState, thisLoc )->fullValidate(thisLoc, keyPattern);
-        }
-    };
-
-    BtreeInterfaceImpl<V0> interface_v0;
-    BtreeInterfaceImpl<V1> interface_v1;
-    BtreeInterface* BtreeInterface::interfaces[] = { &interface_v0, &interface_v1 };
-
-}  // namespace mongo
-
diff --git a/src/mongo/db/index/btree_interface.h b/src/mongo/db/index/btree_interface.h
deleted file mode 100644
index 1c24015590e..00000000000
--- a/src/mongo/db/index/btree_interface.h
+++ /dev/null
@@ -1,152 +0,0 @@
-/**
-*    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.
-*/
-
-#pragma once
-
-#include "mongo/db/diskloc.h"
-#include "mongo/db/jsobj.h"
-
-namespace mongo {
-
-    class IndexCatalogEntry;
-
-    /**
-     * We have two Btree on-disk formats which support identical operations.  We hide this as much
-     * as possible by having one implementation of this interface per format.
-     *
-     * For documentation on all of the methods here, look at mongo/db/structure/btree/btree.h
-     */
-    class BtreeInterface {
-    public:
-        virtual ~BtreeInterface() { }
-
-        static BtreeInterface *interfaces[];
-
-        // This is the # of the exception that is thrown if we're trying to access a bucket that
-        // was deleted.  Calling code needs to be able to recognize this and possibly ignore it.
-        static const int deletedBucketCode = 16738;
-
-        virtual int bt_insert(IndexCatalogEntry* btreeState,
-                              const DiskLoc thisLoc,
-                              const DiskLoc recordLoc,
-                              const BSONObj& key,
-                              bool dupsallowed,
-                              bool toplevel = true) = 0;
-
-        virtual bool unindex(IndexCatalogEntry* btreeState,
-                             const DiskLoc thisLoc,
-                             const BSONObj& key,
-                             const DiskLoc recordLoc) = 0;
-
-        virtual DiskLoc locate(const IndexCatalogEntry* btreeState,
-                               const DiskLoc& thisLoc,
-                               const BSONObj& key,
-                               int& pos, // out
-                               bool& found, // out
-                               const DiskLoc& recordLoc, // out
-                               int direction = 1) const = 0;
-
-        virtual bool wouldCreateDup(const IndexCatalogEntry* btreeState,
-                                    const DiskLoc& thisLoc,
-                                    const BSONObj& key,
-                                    const DiskLoc& self) const = 0;
-
-        virtual void customLocate(const IndexCatalogEntry* btreeState,
-                                  DiskLoc& locInOut,
-                                  int& keyOfs,
-                                  const BSONObj& keyBegin,
-                                  int keyBeginLen, bool afterKey,
-                                  const vector<const BSONElement*>& keyEnd,
-                                  const vector<bool>& keyEndInclusive,
-                                  int direction,
-                                  pair<DiskLoc, int>& bestParent) const = 0 ;
-
-        virtual void advanceTo(const IndexCatalogEntry* btreeState,
-                               DiskLoc &thisLoc,
-                               int &keyOfs,
-                               const BSONObj &keyBegin,
-                               int keyBeginLen,
-                               bool afterKey,
-                               const vector<const BSONElement*>& keyEnd,
-                               const vector<bool>& keyEndInclusive,
-                               int direction) const = 0;
-
-        virtual string dupKeyError(const IndexCatalogEntry* btreeState,
-                                   DiskLoc bucket,
-                                   const BSONObj& keyObj) const =0;
-
-        virtual DiskLoc advance(const IndexCatalogEntry* btreeState,
-                                const DiskLoc& thisLoc,
-                                int& keyOfs,
-                                int direction,
-                                const char* caller) const = 0;
-
-        virtual long long fullValidate(const IndexCatalogEntry* btreeState,
-                                       const DiskLoc& thisLoc,
-                                       const BSONObj& keyPattern) = 0;
-
-        /**
-         * These methods are here so that the BtreeCursor doesn't need to do any templating for the
-         * two on-disk formats.
-         */
-
-        /**
-         * Returns number of total keys just in provided bucket
-         * (not recursive)
-         */
-        virtual int nKeys(const IndexCatalogEntry* btreeState,
-                          DiskLoc bucket ) = 0;
-
-        /**
-         * Is the key at (bucket, keyOffset) being used or not?
-         * Some keys are marked as not used and skipped.
-         */
-        virtual bool keyIsUsed(const IndexCatalogEntry* btreeState,
-                               DiskLoc bucket, int keyOffset) const = 0;
-
-        /**
-         * Get the BSON representation of the key at (bucket, keyOffset).
-         */
-        virtual BSONObj keyAt(const IndexCatalogEntry* btreeState,
-                              DiskLoc bucket, int keyOffset) const = 0;
-
-        /**
-         * Get the DiskLoc that the key at (bucket, keyOffset) points at.
-         */
-        virtual DiskLoc recordAt(const IndexCatalogEntry* btreeState,
-                                 DiskLoc bucket, int keyOffset) const = 0;
-
-        /**
-         * keyAt and recordAt at the same time.
-         */
-        virtual void keyAndRecordAt(const IndexCatalogEntry* btreeState,
-                                    DiskLoc bucket, int keyOffset, BSONObj* keyOut,
-                                    DiskLoc* recordOut) const = 0;
-    };
-
-}  // namespace mongo