SERVER-13084 btree navigation should use new impl

13 files changed, 739 insertions, 590 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
diff --git a/src/mongo/db/structure/btree/btree_interface.cpp b/src/mongo/db/structure/btree/btree_interface.cpp
index 6774e33e437..a7fc44f6e77 100644
--- a/src/mongo/db/structure/btree/btree_interface.cpp
+++ b/src/mongo/db/structure/btree/btree_interface.cpp
@@ -60,9 +60,10 @@ namespace transition {
         virtual bool locate(const BSONObj& key,
                             const DiskLoc& loc,
                             const int direction,
-                            BtreeLocation* locOut) {
+                            DiskLoc* bucketOut,
+                            int* keyPosOut) {
 
-            return _btree->locate(key, loc, direction, &locOut->pos, &locOut->bucket);
+            return _btree->locate(key, loc, direction, keyPosOut, bucketOut);
         }
 
         virtual Status dupKeyCheck(const BSONObj& key, const DiskLoc& loc) {
@@ -73,6 +74,72 @@ namespace transition {
             return _btree->isEmpty();
         }
 
+        virtual void customLocate(DiskLoc* locInOut,
+                                 int* keyOfsInOut,
+                                 const BSONObj& keyBegin,
+                                 int keyBeginLen,
+                                 bool afterKey,
+                                 const vector<const BSONElement*>& keyEnd,
+                                 const vector<bool>& keyEndInclusive,
+                                 int direction) {
+
+            _btree->customLocate(locInOut,
+                                 keyOfsInOut,
+                                 keyBegin,
+                                 keyBeginLen,
+                                 afterKey, 
+                                 keyEnd,
+                                 keyEndInclusive,
+                                 direction);
+        }
+
+        void advanceTo(DiskLoc* thisLocInOut,
+                       int* keyOfsInOut,
+                       const BSONObj &keyBegin,
+                       int keyBeginLen,
+                       bool afterKey,
+                       const vector<const BSONElement*>& keyEnd,
+                       const vector<bool>& keyEndInclusive,
+                       int direction) const {
+
+            _btree->advanceTo(thisLocInOut,
+                              keyOfsInOut,
+                              keyBegin,
+                              keyBeginLen,
+                              afterKey,
+                              keyEnd,
+                              keyEndInclusive,
+                              direction);
+        }
+
+        virtual BSONObj getKey(const DiskLoc& bucket, const int keyOffset) {
+            return _btree->getKey(bucket, keyOffset);
+        }
+
+        virtual DiskLoc getDiskLoc(const DiskLoc& bucket, const int keyOffset) {
+            return _btree->getDiskLoc(bucket, keyOffset);
+        }
+
+        virtual void advance(DiskLoc* bucketInOut, int* posInOut, int direction) {
+            _btree->advance(bucketInOut, posInOut, direction);
+        }
+
+        virtual void savePosition(const DiskLoc& bucket,
+                                  const int keyOffset,
+                                  SavedPositionData* savedOut) {
+
+            savedOut->key = getKey(bucket, keyOffset).getOwned();
+            savedOut->loc = getDiskLoc(bucket, keyOffset);
+        }
+
+        virtual void restorePosition(const SavedPositionData& saved,
+                                     int direction,
+                                     DiskLoc* bucketInOut,
+                                     int* keyOffsetInOut) {
+
+            _btree->restorePosition(saved.key, saved.loc, direction, bucketInOut, keyOffsetInOut);
+        }
+
     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 5244110dd03..9b5d32fcca2 100644
--- a/src/mongo/db/structure/btree/btree_interface.h
+++ b/src/mongo/db/structure/btree/btree_interface.h
@@ -40,20 +40,18 @@ namespace transition {
     /**
      * This is the interface for interacting with the Btree.  The index access and catalog layers
      * should use this.
+     *
+     * TODO: do we want to hide the fact that (DiskLoc, int) identify an entry?
      */
     class BtreeInterface {
     public:
-        virtual ~BtreeInterface() { }
-
-        /**
-         * Represents a location in the Btree.
-         */
-        struct BtreeLocation {
-            // XXX: can these be private?
-            DiskLoc bucket;
-            int pos;
+        struct SavedPositionData {
+            BSONObj key;
+            DiskLoc loc;
         };
 
+        virtual ~BtreeInterface() { }
+
         /**
          * Interact with the Btree through the BtreeInterface.
          *
@@ -66,25 +64,78 @@ namespace transition {
                                             const Ordering& ordering,
                                             int version);
 
+        //
+        // Data changes
+        //
+
         virtual Status insert(const BSONObj& key, const DiskLoc& loc, bool dupsAllowed) = 0;
 
         virtual bool unindex(const BSONObj& key, const DiskLoc& loc) = 0;
 
-        virtual bool locate(const BSONObj& key,
-                            const DiskLoc& loc,
-                            const int direction,
-                            BtreeLocation* locOut) = 0;
+        // TODO: Hide this by exposing an update method?
+        virtual Status dupKeyCheck(const BSONObj& key, const DiskLoc& loc) = 0;
+
+        //
+        // Information about the tree
+        //
 
         // TODO: expose full set of args for testing?
         virtual void fullValidate(long long* numKeysOut) = 0;
 
         virtual bool isEmpty() = 0;
 
+        //
+        // Navigation
+        //
+
+        virtual bool locate(const BSONObj& key,
+                            const DiskLoc& loc,
+                            const int direction,
+                            DiskLoc* bucketOut,
+                            int* keyPosOut) = 0;
+
+        virtual void advanceTo(DiskLoc* thisLocInOut,
+                               int* keyOfsInOut,
+                               const BSONObj &keyBegin,
+                               int keyBeginLen,
+                               bool afterKey,
+                               const vector<const BSONElement*>& keyEnd,
+                               const vector<bool>& keyEndInclusive,
+                               int direction) const = 0;
+
+        /**
+         * Locate a key with fields comprised of a combination of keyBegin fields and keyEnd fields.
+         */
+        virtual void customLocate(DiskLoc* locInOut,
+                                  int* keyOfsInOut,
+                                  const BSONObj& keyBegin,
+                                  int keyBeginLen,
+                                  bool afterVersion,
+                                  const vector<const BSONElement*>& keyEnd,
+                                  const vector<bool>& keyEndInclusive,
+                                  int direction) = 0;
+
         /**
          * Return OK if it's not
          * Otherwise return a status that can be displayed 
          */
-        virtual Status dupKeyCheck(const BSONObj& key, const DiskLoc& loc) = 0;
+        virtual BSONObj getKey(const DiskLoc& bucket, const int keyOffset) = 0;
+
+        virtual DiskLoc getDiskLoc(const DiskLoc& bucket, const int keyOffset) = 0;
+
+        virtual void advance(DiskLoc* bucketInOut, int* posInOut, int direction) = 0;
+
+        //
+        // Saving and restoring state
+        //
+        virtual void savePosition(const DiskLoc& bucket,
+                                  const int keyOffset,
+                                  SavedPositionData* savedOut) = 0;
+
+        virtual void restorePosition(const SavedPositionData& saved,
+                                     int direction,
+                                     DiskLoc* bucketOut,
+                                     int* keyOffsetOut) = 0;
     };
 
 }  // namespace transition
diff --git a/src/mongo/db/structure/btree/btree_logic.cpp b/src/mongo/db/structure/btree/btree_logic.cpp
index e522247695b..f3784fd90ca 100644
--- a/src/mongo/db/structure/btree/btree_logic.cpp
+++ b/src/mongo/db/structure/btree/btree_logic.cpp
@@ -451,16 +451,351 @@ namespace transition {
         _packReadyForMod(bucket, refpos );
     }
 
+    template <class BtreeLayout>
+    void BtreeLogic<BtreeLayout>::customLocate(DiskLoc* locInOut,
+                                               int* keyOfsInOut,
+                                               const BSONObj& keyBegin,
+                                               int keyBeginLen,
+                                               bool afterKey,
+                                               const vector<const BSONElement*>& keyEnd,
+                                               const vector<bool>& keyEndInclusive,
+                                               int direction) const {
+        pair<DiskLoc, int> unused;
+
+        customLocate(locInOut,
+                     keyOfsInOut,
+                     keyBegin,
+                     keyBeginLen,
+                     afterKey, 
+                     keyEnd,
+                     keyEndInclusive,
+                     direction,
+                     unused);
+
+        skipUnusedKeys(locInOut, keyOfsInOut, direction);
+    }
+
+    template <class BtreeLayout>
+    void BtreeLogic<BtreeLayout>::advance(DiskLoc* bucketLocInOut,
+                                          int* posInOut,
+                                          int direction) const {
+
+        *bucketLocInOut = advance(*bucketLocInOut, posInOut, direction);
+        skipUnusedKeys(bucketLocInOut, posInOut, direction);
+    }
+
+    template <class BtreeLayout>
+    void BtreeLogic<BtreeLayout>::skipUnusedKeys(DiskLoc* loc, int* pos, int direction) const {
+        while (!loc->isNull() && !keyIsUsed(*loc, *pos)) {
+            *loc = advance(*loc, pos, direction);
+        }
+    }
+
+    template <class BtreeLayout>
+    void BtreeLogic<BtreeLayout>::advanceTo(DiskLoc* thisLocInOut,
+                                            int* keyOfsInOut,
+                                            const BSONObj &keyBegin,
+                                            int keyBeginLen,
+                                            bool afterKey,
+                                            const vector<const BSONElement*>& keyEnd,
+                                            const vector<bool>& keyEndInclusive,
+                                            int direction) const {
+
+        advanceToImpl(thisLocInOut,
+                      keyOfsInOut,
+                      keyBegin,
+                      keyBeginLen,
+                      afterKey,
+                      keyEnd,
+                      keyEndInclusive,
+                      direction);
+
+        skipUnusedKeys(thisLocInOut, keyOfsInOut, direction);
+    }
+
+    template <class BtreeLayout>
+    void BtreeLogic<BtreeLayout>::advanceToImpl(DiskLoc* thisLocInOut,
+                                                int* keyOfsInOut,
+                                                const BSONObj &keyBegin,
+                                                int keyBeginLen,
+                                                bool afterKey,
+                                                const vector<const BSONElement*>& keyEnd,
+                                                const vector<bool>& keyEndInclusive,
+                                                int direction) const {
+
+        BucketType* bucket = getBucket(*thisLocInOut);
+
+        int l, h;
+        bool dontGoUp;
+
+        if (direction > 0) {
+            l = *keyOfsInOut;
+            h = bucket->n - 1;
+            int cmpResult = customBSONCmp(getFullKey(bucket, h).data.toBson(),
+                                          keyBegin,
+                                          keyBeginLen,
+                                          afterKey,
+                                          keyEnd,
+                                          keyEndInclusive,
+                                          _ordering,
+                                          direction);
+            dontGoUp = (cmpResult >= 0);
+        }
+        else {
+            l = 0;
+            h = *keyOfsInOut;
+            int cmpResult = customBSONCmp(getFullKey(bucket, l).data.toBson(),
+                                          keyBegin,
+                                          keyBeginLen,
+                                          afterKey,
+                                          keyEnd,
+                                          keyEndInclusive,
+                                          _ordering,
+                                          direction);
+            dontGoUp = (cmpResult <= 0);
+        }
+
+        pair<DiskLoc, int> bestParent;
+
+        if (dontGoUp) {
+            // this comparison result assures h > l
+            if (!customFind(l,
+                            h,
+                            keyBegin,
+                            keyBeginLen,
+                            afterKey,
+                            keyEnd,
+                            keyEndInclusive,
+                            _ordering,
+                            direction,
+                            thisLocInOut,
+                            keyOfsInOut,
+                            bestParent)) {
+                return;
+            }
+        }
+        else {
+            // go up parents until rightmost/leftmost node is >=/<= target or at top
+            while (!bucket->parent.isNull()) {
+                *thisLocInOut = bucket->parent;
+                bucket = getBucket(*thisLocInOut);
+
+                if (direction > 0) {
+                    if (customBSONCmp(getFullKey(bucket, bucket->n - 1).data.toBson(),
+                                      keyBegin,
+                                      keyBeginLen,
+                                      afterKey,
+                                      keyEnd,
+                                      keyEndInclusive,
+                                      _ordering,
+                                      direction) >= 0 ) {
+                        break;
+                    }
+                }
+                else {
+                    if (customBSONCmp(getFullKey(bucket, 0).data.toBson(),
+                                      keyBegin,
+                                      keyBeginLen,
+                                      afterKey,
+                                      keyEnd,
+                                      keyEndInclusive,
+                                      _ordering,
+                                      direction) <= 0) {
+                        break;
+                    }
+                }
+            }
+        }
+
+        customLocate(thisLocInOut,
+                     keyOfsInOut,
+                     keyBegin,
+                     keyBeginLen,
+                     afterKey,
+                     keyEnd,
+                     keyEndInclusive,
+                     direction,
+                     bestParent);
+    }
+
+    template <class BtreeLayout>
+    void BtreeLogic<BtreeLayout>::customLocate(DiskLoc* locInOut,
+                                               int* keyOfsInOut,
+                                               const BSONObj& keyBegin,
+                                               int keyBeginLen,
+                                               bool afterKey,
+                                               const vector<const BSONElement*>& keyEnd,
+                                               const vector<bool>& keyEndInclusive,
+                                               int direction,
+                                               pair<DiskLoc, int>& bestParent) const {
+
+        BucketType* bucket = getBucket(*locInOut);
+
+        if (0 == bucket->n) {
+            *locInOut = DiskLoc();
+            return;
+        }
+
+        // go down until find smallest/biggest >=/<= target
+        for (;;) {
+            int l = 0;
+            int h = bucket->n - 1;
+
+            // +direction: 0, -direction: h
+            int z = (direction > 0) ? 0 : h;
+
+            // leftmost/rightmost key may possibly be >=/<= search key
+            int res = customBSONCmp(getFullKey(bucket, z).data.toBson(),
+                                    keyBegin,
+                                    keyBeginLen,
+                                    afterKey,
+                                    keyEnd,
+                                    keyEndInclusive,
+                                    _ordering,
+                                    direction);
+
+
+            if (direction * res >= 0) {
+                DiskLoc next;
+                *keyOfsInOut = z;
+
+                if (direction > 0) {
+                    dassert(z == 0);
+                    next = getKeyHeader(bucket, 0).prevChildBucket;
+                }
+                else {
+                    next = bucket->nextChild;
+                }
+
+                if (!next.isNull()) {
+                    bestParent = pair<DiskLoc, int>(*locInOut, *keyOfsInOut);
+                    *locInOut = next;
+                    bucket = getBucket(*locInOut);
+                    continue;
+                }
+                else {
+                    return;
+                }
+            }
+
+            res = customBSONCmp(getFullKey(bucket, h - z).data.toBson(),
+                                keyBegin,
+                                keyBeginLen,
+                                afterKey,
+                                keyEnd,
+                                keyEndInclusive,
+                                _ordering,
+                                direction);
+
+            if (direction * res < 0) {
+                DiskLoc next;
+                if (direction > 0) {
+                    next = bucket->nextChild;
+                }
+                else {
+                    next = getKeyHeader(bucket, 0).prevChildBucket;
+                }
+
+                if (next.isNull()) {
+                    // if bestParent is null, we've hit the end and locInOut gets set to DiskLoc()
+                    *locInOut = bestParent.first;
+                    *keyOfsInOut = bestParent.second;
+                    return;
+                }
+                else {
+                    *locInOut = next;
+                    bucket = getBucket(*locInOut);
+                    continue;
+                }
+            }
+
+            if (!customFind(l,
+                            h,
+                            keyBegin,
+                            keyBeginLen,
+                            afterKey,
+                            keyEnd,
+                            keyEndInclusive,
+                            _ordering,
+                            direction,
+                            locInOut,
+                            keyOfsInOut,
+                            bestParent)) {
+                return;
+            }
+
+            bucket = getBucket(*locInOut);
+        }
+    }
+
+    template <class BtreeLayout>
+    bool BtreeLogic<BtreeLayout>::customFind(int low,
+                                             int high,
+                                             const BSONObj& keyBegin,
+                                             int keyBeginLen,
+                                             bool afterKey,
+                                             const vector<const BSONElement*>& keyEnd,
+                                             const vector<bool>& keyEndInclusive,
+                                             const Ordering& order,
+                                             int direction,
+                                             DiskLoc* thisLocInOut,
+                                             int* keyOfsInOut,
+                                             pair<DiskLoc, int>& bestParent) const {
+
+        const BucketType* bucket = getBucket(*thisLocInOut);
+
+        for (;;) {
+            if (low + 1 == high) {
+                *keyOfsInOut = (direction > 0) ? high : low;
+                DiskLoc next = getKeyHeader(bucket, high).prevChildBucket;
+                if (!next.isNull()) {
+                    bestParent = make_pair(*thisLocInOut, *keyOfsInOut);
+                    *thisLocInOut = next;
+                    return true;
+                }
+                else {
+                    return false;
+                }
+            }
+
+            int middle = low + (high - low) / 2;
+
+            int cmp = customBSONCmp(getFullKey(bucket, middle).data.toBson(),
+                                    keyBegin,
+                                    keyBeginLen,
+                                    afterKey,
+                                    keyEnd,
+                                    keyEndInclusive,
+                                    order,
+                                    direction);
+
+            if (cmp < 0) {
+                low = middle;
+            }
+            else if (cmp > 0) {
+                high = middle;
+            }
+            else {
+                if (direction < 0) {
+                    low = middle;
+                }
+                else {
+                    high = middle;
+                }
+            }
+        }
+    }
+
     // static
     template <class BtreeLayout>
     int BtreeLogic<BtreeLayout>::customBSONCmp(const BSONObj& l,
-                                                const BSONObj& rBegin,
-                                                int rBeginLen,
-                                                bool rSup,
-                                                const vector<const BSONElement*>& rEnd,
-                                                const vector<bool>& rEndInclusive,
-                                                const Ordering& o,
-                                                int direction) {
+                                               const BSONObj& rBegin,
+                                               int rBeginLen,
+                                               bool rSup,
+                                               const vector<const BSONElement*>& rEnd,
+                                               const vector<bool>& rEndInclusive,
+                                               const Ordering& o,
+                                               int direction) const {
         // XXX: make this readable
         BSONObjIterator ll( l );
         BSONObjIterator rr( rBegin );
@@ -501,7 +836,7 @@ namespace transition {
 
     template <class BtreeLayout>
     bool BtreeLogic<BtreeLayout>::exists(const KeyDataType& key) const {
-        int position;
+        int position = 0;
 
         // Find the DiskLoc 
         bool found;
@@ -686,6 +1021,60 @@ namespace transition {
     }
 
     template <class BtreeLayout>
+    void BtreeLogic<BtreeLayout>::restorePosition(const BSONObj& savedKey,
+                                                  const DiskLoc& savedLoc,
+                                                  int direction,
+                                                  DiskLoc* bucketLocInOut,
+                                                  int* keyOffsetInOut) const {
+
+        // _keyOffset is -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.  This'll go away with finer grained locking: we
+        // can hold on to a bucket for as long as we need it.
+        if (-1 == *keyOffsetInOut) {
+            locate(savedKey, savedLoc, direction, keyOffsetInOut, bucketLocInOut);
+            return;
+        }
+
+        invariant(*keyOffsetInOut >= 0);
+
+        BucketType* bucket = getBucket(*bucketLocInOut);
+        invariant(bucket);
+        invariant(BtreeLayout::INVALID_N_SENTINEL != bucket->n);
+
+        if (keyIsAt(savedKey, savedLoc, bucket, *keyOffsetInOut)) {
+            skipUnusedKeys(bucketLocInOut, keyOffsetInOut, direction);
+            return;
+        }
+
+        if (*keyOffsetInOut > 0) {
+            (*keyOffsetInOut)--;
+            if (keyIsAt(savedKey, savedLoc, bucket, *keyOffsetInOut)) {
+                skipUnusedKeys(bucketLocInOut, keyOffsetInOut, direction);
+                return;
+            }
+        }
+
+        locate(savedKey, savedLoc, direction, keyOffsetInOut, bucketLocInOut);
+    }
+
+    template <class BtreeLayout>
+    bool BtreeLogic<BtreeLayout>::keyIsAt(const BSONObj& savedKey,
+                                          const DiskLoc& savedLoc,
+                                          BucketType* bucket,
+                                          int keyPos) const {
+        if (keyPos >= bucket->n) {
+            return false;
+        }
+
+        FullKey key = getFullKey(bucket, keyPos);
+        if (!key.data.toBson().binaryEqual(savedKey)) {
+            return false;
+        }
+        return key.header.recordLoc == savedLoc;
+    }
+
+    template <class BtreeLayout>
     void BtreeLogic<BtreeLayout>::delKeyAtPos(BucketType* bucket,
                                                const DiskLoc bucketLoc,
                                                int p) {
@@ -1277,6 +1666,35 @@ namespace transition {
     }
 
     template <class BtreeLayout>
+    DiskLoc BtreeLogic<BtreeLayout>::getDiskLoc(const DiskLoc& bucketLoc, const int keyOffset) {
+        invariant(!bucketLoc.isNull());
+        BucketType* bucket = getBucket(bucketLoc);
+        return getKeyHeader(bucket, keyOffset).recordLoc;
+    }
+
+    template <class BtreeLayout>
+    BSONObj BtreeLogic<BtreeLayout>::getKey(const DiskLoc& bucketLoc, const int keyOffset) {
+        invariant(!bucketLoc.isNull());
+        BucketType* bucket = getBucket(bucketLoc);
+        int n = bucket->n;
+        invariant(n != BtreeLayout::INVALID_N_SENTINEL);
+        invariant(n >= 0);
+        invariant(n < 10000);
+        invariant(n != 0xffff);
+
+        invariant(keyOffset >= 0);
+        invariant(keyOffset < n);
+
+        // XXX: should we really return an empty obj if keyOffset>=n?
+        if (keyOffset >= n) {
+            return BSONObj();
+        }
+        else {
+            return getFullKey(bucket, keyOffset).data.toBson();
+        }
+    }
+
+    template <class BtreeLayout>
     long long BtreeLogic<BtreeLayout>::fullValidate(long long *unusedCount,
                                                      bool strict,
                                                      bool dumpBuckets,
@@ -1551,14 +1969,31 @@ namespace transition {
     }
 
     template <class BtreeLayout>
+    bool BtreeLogic<BtreeLayout>::keyIsUsed(const DiskLoc& loc, const int& pos) const {
+        return getKeyHeader(getBucket(loc), pos).isUsed();
+    }
+
+    template <class BtreeLayout>
     bool BtreeLogic<BtreeLayout>::locate(const BSONObj& key,
                                          const DiskLoc& recordLoc,
                                          const int direction,
                                          int* posOut,
                                          DiskLoc* bucketLocOut) const {
+        // Clear out any data.
+        *posOut = 0;
+        *bucketLocOut = DiskLoc();
+
         bool found = false;
         KeyDataOwnedType owned(key);
+
         *bucketLocOut = locate(getRootLoc(), owned, posOut, &found, recordLoc, direction);
+
+        if (!found) {
+            return false;
+        }
+
+        skipUnusedKeys(bucketLocOut, posOut, direction);
+
         return found;
     }
 
diff --git a/src/mongo/db/structure/btree/btree_logic.h b/src/mongo/db/structure/btree/btree_logic.h
index a3dbc2a2580..acbdaa545ae 100644
--- a/src/mongo/db/structure/btree/btree_logic.h
+++ b/src/mongo/db/structure/btree/btree_logic.h
@@ -81,14 +81,14 @@ namespace transition {
                     int* posOut,
                     DiskLoc* bucketLocOut) const;
 
+        void advance(DiskLoc* bucketLocInOut, int* posInOut, int direction) const;
+
         bool exists(const KeyDataType& key) const;
 
         bool unindex(const BSONObj& key, const DiskLoc& recordLoc);
 
         bool isEmpty() const;
 
-        DiskLoc advance(const DiskLoc& bucketLoc, int* posInOut, int direction) const;
-
         Status find(BucketType* bucket,
                     const KeyDataType& key,
                     const DiskLoc& recordLoc,
@@ -101,6 +101,44 @@ namespace transition {
                                bool dumpBuckets,
                                unsigned depth);
 
+        DiskLoc getDiskLoc(const DiskLoc& bucketLoc, const int keyOffset);
+
+        BSONObj getKey(const DiskLoc& bucketLoc, const int keyOffset);
+
+        //
+        // Composite key navigation methods
+        //
+
+        void customLocate(DiskLoc* locInOut,
+                          int* keyOfsInOut,
+                          const BSONObj& keyBegin,
+                          int keyBeginLen,
+                          bool afterKey,
+                          const vector<const BSONElement*>& keyEnd,
+                          const vector<bool>& keyEndInclusive,
+                          int direction) const;
+
+        void advanceTo(DiskLoc* thisLocInOut,
+                       int* keyOfsInOut,
+                       const BSONObj &keyBegin,
+                       int keyBeginLen,
+                       bool afterKey,
+                       const vector<const BSONElement*>& keyEnd,
+                       const vector<bool>& keyEndInclusive,
+                       int direction) const;
+
+        void restorePosition(const BSONObj& savedKey,
+                             const DiskLoc& savedLoc,
+                             int direction,
+                             DiskLoc* bucketInOut,
+                             int* keyOffsetInOut) const;
+
+        bool keyIsAt(const BSONObj& savedKey,
+                     const DiskLoc& savedLoc,
+                     BucketType* bucket,
+                     int keyPos) const;
+                     
+
     private:
         /**
          * This is an in memory wrapper for the variable length data associated with a
@@ -164,23 +202,16 @@ namespace transition {
 
         static void popBack(BucketType* bucket, DiskLoc* recordLocOut, KeyDataType *keyDataOut);
 
-        bool basicInsert(BucketType* bucket,
-                         const DiskLoc bucketLoc,
-                         int& keypos,
-                         const KeyDataType& key,
-                         const DiskLoc recordLoc);
-
         static bool mayDropKey(BucketType* bucket, int index, int refPos);
 
         static int packedDataSize(BucketType* bucket, int refPos);
 
         static void setPacked(BucketType* bucket);
+
         static void setNotPacked(BucketType* bucket);
 
         static BucketType* btreemod(BucketType* bucket);
 
-        void _pack(BucketType* bucket, const DiskLoc thisLoc, int &refPos);
-
         static int splitPos(BucketType* bucket, int keypos);
 
         static void reserveKeysFront(BucketType* bucket, int nAdd);
@@ -191,8 +222,6 @@ namespace transition {
                            const KeyDataType &key,
                            const DiskLoc prevChildBucket);
 
-        void dropFront(BucketType* bucket, int nDrop, int &refpos);
-
         static bool isHead(BucketType* bucket);
 
         static void dump(BucketType* bucket, int depth = 0);
@@ -204,8 +233,56 @@ namespace transition {
         // information).
         //
 
+        bool basicInsert(BucketType* bucket,
+                         const DiskLoc bucketLoc,
+                         int& keypos,
+                         const KeyDataType& key,
+                         const DiskLoc recordLoc);
+
+        void dropFront(BucketType* bucket, int nDrop, int& refpos);
+
+        void _pack(BucketType* bucket, const DiskLoc thisLoc, int &refPos);
+
+        void customLocate(DiskLoc* locInOut,
+                          int* keyOfsInOut,
+                          const BSONObj& keyBegin,
+                          int keyBeginLen,
+                          bool afterKey,
+                          const vector<const BSONElement*>& keyEnd,
+                          const vector<bool>& keyEndInclusive,
+                          int direction,
+                          pair<DiskLoc, int>& bestParent) const;
+
+        bool customFind(int low,
+                        int high,
+                        const BSONObj& keyBegin,
+                        int keyBeginLen,
+                        bool afterKey,
+                        const vector<const BSONElement*>& keyEnd,
+                        const vector<bool>& keyEndInclusive,
+                        const Ordering& order,
+                        int direction,
+                        DiskLoc* thisLocInOut,
+                        int* keyOfsInOut,
+                        pair<DiskLoc, int>& bestParent) const;
+
+        void advanceToImpl(DiskLoc* thisLocInOut,
+                           int* keyOfsInOut,
+                           const BSONObj &keyBegin,
+                           int keyBeginLen,
+                           bool afterKey,
+                           const vector<const BSONElement*>& keyEnd,
+                           const vector<bool>& keyEndInclusive,
+                           int direction) const;
+
         bool wouldCreateDup(const KeyDataType& key, const DiskLoc self) const;
 
+        bool keyIsUsed(const DiskLoc& loc, const int& pos) const;
+
+        void skipUnusedKeys(DiskLoc* loc, int* pos, int direction) const;
+
+        DiskLoc advance(const DiskLoc& bucketLoc, int* posInOut, int direction) const;
+
         DiskLoc locate(const DiskLoc& bucketLoc,
                        const KeyDataType& key,
                        int* posOut,
@@ -322,7 +399,7 @@ namespace transition {
                           const vector<const BSONElement*>& rEnd,
                           const vector<bool>& rEndInclusive,
                           const Ordering& o,
-                          int direction);
+                          int direction) const;
 
         // TODO needs 'this' for _ordering for sanity check
         bool _pushBack(BucketType* bucket,