SERVER-13635 Added tests for SortedDataInterface.

Expand set of generic SortedDataInterface tests.
Includes tests for the following functions:
  - SortedDataInterface::dupKeyCheck
  - SortedDataInterface::fullValidate
  - SortedDataInterface::getSpaceUsedBytes
  - SortedDataInterface::insert
  - SortedDataInterface::touch
  - SortedDataInterface::unindex
  - SortedDataInterface::Cursor::getDirection
  - SortedDataInterface::Cursor::isEOF
  - SortedDataInterface::Cursor::pointsToSamePlaceAs

Add tests for SortedDataInterface::Cursor::locate.

Add save/restore position tests.
Includes tests for the following functions:
  - SortedDataInterface::Cursor::restorePosition
  - SortedDataInterface::Cursor::savePosition

Add tests for SortedDataInterface::Cursor::advanceTo.
Only tests single-key indices, not those with compound keys.

Closes #804

Signed-off-by: Benety Goh <benety@mongodb.com>

16 files changed, 3972 insertions, 2 deletions

diff --git a/src/mongo/db/storage/SConscript b/src/mongo/db/storage/SConscript
index fbb4cbb8516..07bee5d0c8e 100644
--- a/src/mongo/db/storage/SConscript
+++ b/src/mongo/db/storage/SConscript
@@ -19,7 +19,20 @@ env.Library(
 env.Library(
     target='sorted_data_interface_test_harness',
     source=[
+        'sorted_data_interface_test_cursor.cpp',
+        'sorted_data_interface_test_cursor_advanceto.cpp',
+        'sorted_data_interface_test_cursor_locate.cpp',
+        'sorted_data_interface_test_cursor_position.cpp',
+        'sorted_data_interface_test_cursor_saverestore.cpp',
+        'sorted_data_interface_test_dupkeycheck.cpp',
+        'sorted_data_interface_test_fullvalidate.cpp',
         'sorted_data_interface_test_harness.cpp',
+        'sorted_data_interface_test_insert.cpp',
+        'sorted_data_interface_test_isempty.cpp',
+        'sorted_data_interface_test_rollback.cpp',
+        'sorted_data_interface_test_spaceused.cpp',
+        'sorted_data_interface_test_touch.cpp',
+        'sorted_data_interface_test_unindex.cpp',
         ],
     LIBDEPS=[]
     )
diff --git a/src/mongo/db/storage/sorted_data_interface_test_cursor.cpp b/src/mongo/db/storage/sorted_data_interface_test_cursor.cpp
new file mode 100644
index 00000000000..3a22f66099a
--- /dev/null
+++ b/src/mongo/db/storage/sorted_data_interface_test_cursor.cpp
@@ -0,0 +1,200 @@
+// sorted_data_interface_test_cursor.cpp
+
+/**
+ *    Copyright (C) 2014 MongoDB 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/storage/sorted_data_interface_test_harness.h"
+
+#include "mongo/db/storage/sorted_data_interface.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+
+    // Call getDirection() on a forward cursor and verify the result equals +1.
+    TEST( SortedDataInterface, GetCursorDirection ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+            ASSERT_EQUALS( 1, cursor->getDirection() );
+        }
+    }
+
+    // Call getDirection() on a reverse cursor and verify the result equals -1.
+    TEST( SortedDataInterface, GetCursorDirectionReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+            ASSERT_EQUALS( -1, cursor->getDirection() );
+        }
+    }
+
+    // Verify that a forward cursor is positioned at EOF when the index is empty.
+    TEST( SortedDataInterface, CursorIsEOFWhenEmpty ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( !cursor->locate( minKey, minDiskLoc ) );
+            ASSERT( cursor->isEOF() );
+
+            // Cursor at EOF should remain at EOF when advanced
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Verify that a reverse cursor is positioned at EOF when the index is empty.
+    TEST( SortedDataInterface, CursorIsEOFWhenEmptyReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( !cursor->locate( maxKey, maxDiskLoc ) );
+            ASSERT( cursor->isEOF() );
+
+            // Cursor at EOF should remain at EOF when advanced
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Call advance() on a forward cursor until it is exhausted.
+    // When a cursor positioned at EOF is advanced, it stays at EOF.
+    TEST( SortedDataInterface, ExhaustCursor ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        int nToInsert = 10;
+        for ( int i = 0; i < nToInsert; i++ ) {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                BSONObj key = BSON( "" << i );
+                DiskLoc loc( 42, i * 2 );
+                ASSERT_OK( sorted->insert( opCtx.get(), key, loc, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( nToInsert, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+            ASSERT( !cursor->locate( minKey, minDiskLoc ) );
+            for ( int i = 0; i < nToInsert; i++ ) {
+                ASSERT( !cursor->isEOF() );
+                ASSERT_EQUALS( BSON( "" << i ), cursor->getKey() );
+                ASSERT_EQUALS( DiskLoc( 42, i * 2 ), cursor->getDiskLoc() );
+                cursor->advance();
+            }
+            ASSERT( cursor->isEOF() );
+
+            // Cursor at EOF should remain at EOF when advanced
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Call advance() on a reverse cursor until it is exhausted.
+    // When a cursor positioned at EOF is advanced, it stays at EOF.
+    TEST( SortedDataInterface, ExhaustCursorReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        int nToInsert = 10;
+        for ( int i = 0; i < nToInsert; i++ ) {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                BSONObj key = BSON( "" << i );
+                DiskLoc loc( 42, i * 2 );
+                ASSERT_OK( sorted->insert( opCtx.get(), key, loc, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( nToInsert, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+            ASSERT( !cursor->locate( maxKey, maxDiskLoc ) );
+            for ( int i = nToInsert - 1; i >= 0; i-- ) {
+                ASSERT( !cursor->isEOF() );
+                ASSERT_EQUALS( BSON( "" << i ), cursor->getKey() );
+                ASSERT_EQUALS( DiskLoc( 42, i * 2 ), cursor->getDiskLoc() );
+                cursor->advance();
+            }
+            ASSERT( cursor->isEOF() );
+
+            // Cursor at EOF should remain at EOF when advanced
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+} // namespace mongo
diff --git a/src/mongo/db/storage/sorted_data_interface_test_cursor_advanceto.cpp b/src/mongo/db/storage/sorted_data_interface_test_cursor_advanceto.cpp
new file mode 100644
index 00000000000..ab395472e76
--- /dev/null
+++ b/src/mongo/db/storage/sorted_data_interface_test_cursor_advanceto.cpp
@@ -0,0 +1,934 @@
+// sorted_data_interface_test_cursor_advanceto.cpp
+
+/**
+ *    Copyright (C) 2014 MongoDB 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/storage/sorted_data_interface_test_harness.h"
+
+#include "mongo/db/storage/sorted_data_interface.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+
+    // Insert multiple single-field keys and advance to each of them
+    // using a forward cursor by specifying their exact key. When
+    // advanceTo() is called on a duplicate key, the cursor is
+    // positioned at the next occurrence of that key in ascending
+    // order by DiskLoc.
+    TEST( SortedDataInterface, AdvanceTo ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc2, true /* allow duplicates */ ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc3, true /* allow duplicates */ ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc4, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc5, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 5, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( cursor->locate( key1, loc1 ) );
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key1, 1, false, keyEnd, keyEndInclusive );
+                // SERVER-15489 forward cursor is positioned at first occurrence of key in index
+                //              when advanceTo() called on duplicate key
+                // ASSERT_EQUALS( key1, cursor->getKey() );
+                // ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+            }
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key2, 1, false, keyEnd, keyEndInclusive );
+                ASSERT_EQUALS( key2, cursor->getKey() );
+                ASSERT_EQUALS( loc4, cursor->getDiskLoc() );
+            }
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key3, 1, false, keyEnd, keyEndInclusive );
+                ASSERT_EQUALS( key3, cursor->getKey() );
+                ASSERT_EQUALS( loc5, cursor->getDiskLoc() );
+            }
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key4, 1, false, keyEnd, keyEndInclusive );
+                ASSERT( cursor->isEOF() );
+            }
+        }
+    }
+
+    // Insert multiple single-field keys and advance to each of them
+    // using a reverse cursor by specifying their exact key. When
+    // advanceTo() is called on a duplicate key, the cursor is
+    // positioned at the next occurrence of that key in descending
+    // order by DiskLoc.
+    TEST( SortedDataInterface, AdvanceToReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc2, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc3, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc4, true /* allow duplicates */ ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc5, true /* allow duplicates */ ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 5, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( cursor->locate( key3, loc5 ) );
+            ASSERT_EQUALS( key3, cursor->getKey() );
+            ASSERT_EQUALS( loc5, cursor->getDiskLoc() );
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key3, 1, false, keyEnd, keyEndInclusive );
+                // SERVER-15490 reverse cursor is positioned at last occurrence of key in index
+                //              when advanceTo() called on duplicate key
+                // ASSERT_EQUALS( key3, cursor->getKey() );
+                // ASSERT_EQUALS( loc4, cursor->getDiskLoc() );
+            }
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key2, 1, false, keyEnd, keyEndInclusive );
+                ASSERT_EQUALS( key2, cursor->getKey() );
+                ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+            }
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key1, 1, false, keyEnd, keyEndInclusive );
+                ASSERT_EQUALS( key1, cursor->getKey() );
+                ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+            }
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key0, 1, false, keyEnd, keyEndInclusive );
+                ASSERT( cursor->isEOF() );
+            }
+        }
+    }
+
+    // Insert two single-field keys and advance to the larger one using
+    // a forward cursor positioned at the smaller one, by specifying a key
+    // before the current position of the cursor.
+    TEST( SortedDataInterface, AdvanceToKeyBeforeCursorPosition ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc2, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 2, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( cursor->locate( key1, loc1 ) );
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key0, 1, false, keyEnd, keyEndInclusive );
+                // SERVER-15489 forward cursor is positioned at first key in index
+                //              when advanceTo() called with key smaller than any entry
+                // ASSERT_EQUALS( key2, cursor->getKey() );
+                // ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( cursor->locate( key1, loc1 ) );
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key0, 1, true, keyEnd, keyEndInclusive );
+                // SERVER-15489 forward cursor is positioned at first key in index
+                //              when advanceTo() called with key smaller than any entry
+                // ASSERT_EQUALS( key2, cursor->getKey() );
+                // ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+            }
+        }
+    }
+
+    // Insert two single-field keys and advance to the smaller one using
+    // a reverse cursor positioned at the larger one, by specifying a key
+    // after the current position of the cursor.
+    TEST( SortedDataInterface, AdvanceToKeyAfterCursorPositionReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc2, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 2, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( cursor->locate( key2, loc2 ) );
+            ASSERT_EQUALS( key2, cursor->getKey() );
+            ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key3, 1, false, keyEnd, keyEndInclusive );
+                // SERVER-15490 reverse cursor is positioned at last key in index
+                //              when advanceTo() called with key larger than any entry
+                // ASSERT_EQUALS( key1, cursor->getKey() );
+                // ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( cursor->locate( key2, loc2 ) );
+            ASSERT_EQUALS( key2, cursor->getKey() );
+            ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key3, 1, true, keyEnd, keyEndInclusive );
+                // SERVER-15490 reverse cursor is positioned at last key in index
+                //              when advanceTo() called with key larger than any entry
+                // ASSERT_EQUALS( key1, cursor->getKey() );
+                // ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+            }
+        }
+    }
+
+    // Insert a single-field key and advance to EOF using a forward cursor
+    // by specifying that exact key. When advanceTo() is called with the key
+    // where the cursor is positioned (and it is the last entry for that key),
+    // the cursor should advance to EOF regardless of whether it is in non-
+    // or inclusive mode.
+    TEST( SortedDataInterface, AdvanceToKeyAtCursorPosition ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 1, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( cursor->locate( key1, loc1 ) );
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                // SERVER-15483 forward cursor positioned at last entry in index should move
+                //              to EOF when advanceTo() is called with that particular key
+                // cursor->advanceTo( key1, 1, false, keyEnd, keyEndInclusive );
+                // ASSERT( cursor->isEOF() );
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( cursor->locate( key1, loc1 ) );
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key1, 1, true, keyEnd, keyEndInclusive );
+                ASSERT( cursor->isEOF() );
+            }
+        }
+    }
+
+    // Insert a single-field key and advance to EOF using a reverse cursor
+    // by specifying that exact key. When advanceTo() is called with the key
+    // where the cursor is positioned (and it is the first entry for that key),
+    // the cursor should advance to EOF regardless of whether it is in non-
+    // or inclusive mode.
+    TEST( SortedDataInterface, AdvanceToKeyAtCursorPositionReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 1, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( cursor->locate( key1, loc1 ) );
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                // SERVER-15483 reverse cursor positioned at first entry in index should move
+                //              to EOF when advanceTo() is called with that particular key
+                // cursor->advanceTo( key1, 1, false, keyEnd, keyEndInclusive );
+                // ASSERT( cursor->isEOF() );
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( cursor->locate( key1, loc1 ) );
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key1, 1, true, keyEnd, keyEndInclusive );
+                ASSERT( cursor->isEOF() );
+            }
+        }
+    }
+
+    // Insert multiple single-field keys and advance to each of them using
+    // a forward cursor by specifying a key that comes immediately before.
+    // When advanceTo() is called in non-inclusive mode, the cursor is
+    // positioned at the key that comes after the one specified.
+    TEST( SortedDataInterface, AdvanceToExclusive ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc2, true /* allow duplicates */ ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc3, true /* allow duplicates */ ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc4, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc5, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 5, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( cursor->locate( key1, loc1 ) );
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key1, 1, true, keyEnd, keyEndInclusive );
+                ASSERT_EQUALS( key2, cursor->getKey() );
+                ASSERT_EQUALS( loc4, cursor->getDiskLoc() );
+            }
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key2, 1, true, keyEnd, keyEndInclusive );
+                ASSERT_EQUALS( key3, cursor->getKey() );
+                ASSERT_EQUALS( loc5, cursor->getDiskLoc() );
+            }
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key3, 1, true, keyEnd, keyEndInclusive );
+                ASSERT( cursor->isEOF() );
+            }
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                // SERVER-15449 forward cursor positioned at EOF should stay at EOF
+                //              when advanceTo() is called
+                // cursor->advanceTo( key4, 1, true, keyEnd, keyEndInclusive );
+                // ASSERT( cursor->isEOF() );
+            }
+        }
+    }
+
+    // Insert multiple single-field keys and advance to each of them using
+    // a reverse cursor by specifying a key that comes immediately after.
+    // When advanceTo() is called in non-inclusive mode, the cursor is
+    // positioned at the key that comes before the one specified.
+    TEST( SortedDataInterface, AdvanceToExclusiveReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc2, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc3, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc4, true /* allow duplicates */ ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc5, true /* allow duplicates */ ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 5, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( cursor->locate( key3, loc5 ) );
+            ASSERT_EQUALS( key3, cursor->getKey() );
+            ASSERT_EQUALS( loc5, cursor->getDiskLoc() );
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key3, 1, true, keyEnd, keyEndInclusive );
+                ASSERT_EQUALS( key2, cursor->getKey() );
+                ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+            }
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key2, 1, true, keyEnd, keyEndInclusive );
+                ASSERT_EQUALS( key1, cursor->getKey() );
+                ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+            }
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                cursor->advanceTo( key1, 1, true, keyEnd, keyEndInclusive );
+                ASSERT( cursor->isEOF() );
+            }
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                // SERVER-15449 reverse cursor positioned at EOF should stay at EOF
+                //              when advanceTo() is called
+                // cursor->advanceTo( key0, 1, true, keyEnd, keyEndInclusive );
+                // ASSERT( cursor->isEOF() );
+            }
+        }
+    }
+
+    // Insert multiple, non-consecutive, single-field keys and advance to
+    // each of them using a forward cursor by specifying a key between their
+    // exact key and the current position of the cursor.
+    TEST( SortedDataInterface, AdvanceToIndirect ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        BSONObj unusedKey = key6; // larger than any inserted key
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc2, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key5, loc3, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 3, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( cursor->locate( key1, loc1 ) );
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                const BSONElement end0 = key2.firstElement();
+                keyEnd[0] = &end0;
+                keyEndInclusive[0] = true;
+
+                cursor->advanceTo( unusedKey, 0, false, keyEnd, keyEndInclusive );
+                ASSERT_EQUALS( key3, cursor->getKey() );
+                ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+            }
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                const BSONElement end0 = key4.firstElement();
+                keyEnd[0] = &end0;
+                keyEndInclusive[0] = true;
+
+                cursor->advanceTo( unusedKey, 0, false, keyEnd, keyEndInclusive );
+                ASSERT_EQUALS( key5, cursor->getKey() );
+                ASSERT_EQUALS( loc3, cursor->getDiskLoc() );
+            }
+        }
+    }
+
+    // Insert multiple, non-consecutive, single-field keys and advance to
+    // each of them using a reverse cursor by specifying a key between their
+    // exact key and the current position of the cursor.
+    TEST( SortedDataInterface, AdvanceToIndirectReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        BSONObj unusedKey = key0; // smaller than any inserted key
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc2, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key5, loc3, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 3, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( cursor->locate( key5, loc3 ) );
+            ASSERT_EQUALS( key5, cursor->getKey() );
+            ASSERT_EQUALS( loc3, cursor->getDiskLoc() );
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                const BSONElement end0 = key4.firstElement();
+                keyEnd[0] = &end0;
+                keyEndInclusive[0] = true;
+
+                cursor->advanceTo( unusedKey, 0, false, keyEnd, keyEndInclusive );
+                ASSERT_EQUALS( key3, cursor->getKey() );
+                ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+            }
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                const BSONElement end0 = key2.firstElement();
+                keyEnd[0] = &end0;
+                keyEndInclusive[0] = true;
+
+                cursor->advanceTo( unusedKey, 0, false, keyEnd, keyEndInclusive );
+                ASSERT_EQUALS( key1, cursor->getKey() );
+                ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+            }
+        }
+    }
+
+    // Insert multiple, non-consecutive, single-field keys and advance to
+    // each of them using a forward cursor by specifying a key between their
+    // exact key and the current position of the cursor. When advanceTo()
+    // is called in non-inclusive mode, the cursor is positioned at the key
+    // that comes after the one specified.
+    TEST( SortedDataInterface, AdvanceToIndirectExclusive ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        BSONObj unusedKey = key6; // larger than any inserted key
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc2, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key5, loc3, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 3, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( cursor->locate( key1, loc1 ) );
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                const BSONElement end0 = key2.firstElement();
+                keyEnd[0] = &end0;
+                keyEndInclusive[0] = false;
+
+                cursor->advanceTo( unusedKey, 0, false, keyEnd, keyEndInclusive );
+                ASSERT( !cursor->isEOF() );
+                ASSERT_EQUALS( key3, cursor->getKey() );
+                ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+            }
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                const BSONElement end0 = key4.firstElement();
+                keyEnd[0] = &end0;
+                keyEndInclusive[0] = false;
+
+                cursor->advanceTo( unusedKey, 0, false, keyEnd, keyEndInclusive );
+                ASSERT( !cursor->isEOF() );
+                ASSERT_EQUALS( key5, cursor->getKey() );
+                ASSERT_EQUALS( loc3, cursor->getDiskLoc() );
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( cursor->locate( key1, loc1 ) );
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                const BSONElement end0 = key3.firstElement();
+                keyEnd[0] = &end0;
+                keyEndInclusive[0] = false;
+
+                cursor->advanceTo( unusedKey, 0, false, keyEnd, keyEndInclusive );
+                ASSERT( !cursor->isEOF() );
+                ASSERT_EQUALS( key5, cursor->getKey() );
+                ASSERT_EQUALS( loc3, cursor->getDiskLoc() );
+            }
+        }
+    }
+
+    // Insert multiple, non-consecutive, single-field keys and advance to
+    // each of them using a reverse cursor by specifying a key between their
+    // exact key and the current position of the cursor. When advanceTo()
+    // is called in non-inclusive mode, the cursor is positioned at the key
+    // that comes before the one specified.
+    TEST( SortedDataInterface, AdvanceToIndirectExclusiveReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        BSONObj unusedKey = key0; // smaller than any inserted key
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc2, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key5, loc3, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 3, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( cursor->locate( key5, loc3 ) );
+            ASSERT_EQUALS( key5, cursor->getKey() );
+            ASSERT_EQUALS( loc3, cursor->getDiskLoc() );
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                const BSONElement end0 = key4.firstElement();
+                keyEnd[0] = &end0;
+                keyEndInclusive[0] = false;
+
+                cursor->advanceTo( unusedKey, 0, false, keyEnd, keyEndInclusive );
+                ASSERT( !cursor->isEOF() );
+                ASSERT_EQUALS( key3, cursor->getKey() );
+                ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+            }
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                const BSONElement end0 = key2.firstElement();
+                keyEnd[0] = &end0;
+                keyEndInclusive[0] = false;
+
+                cursor->advanceTo( unusedKey, 0, false, keyEnd, keyEndInclusive );
+                ASSERT( !cursor->isEOF() );
+                ASSERT_EQUALS( key1, cursor->getKey() );
+                ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( cursor->locate( key5, loc3 ) );
+            ASSERT_EQUALS( key5, cursor->getKey() );
+            ASSERT_EQUALS( loc3, cursor->getDiskLoc() );
+
+            {
+                vector<const BSONElement*> keyEnd( 1 );
+                vector<bool> keyEndInclusive( 1 );
+
+                const BSONElement end0 = key3.firstElement();
+                keyEnd[0] = &end0;
+                keyEndInclusive[0] = false;
+
+                cursor->advanceTo( unusedKey, 0, false, keyEnd, keyEndInclusive );
+                ASSERT( !cursor->isEOF() );
+                ASSERT_EQUALS( key1, cursor->getKey() );
+                ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+            }
+        }
+    }
+
+} // namespace mongo
diff --git a/src/mongo/db/storage/sorted_data_interface_test_cursor_locate.cpp b/src/mongo/db/storage/sorted_data_interface_test_cursor_locate.cpp
new file mode 100644
index 00000000000..ec0fbb2b969
--- /dev/null
+++ b/src/mongo/db/storage/sorted_data_interface_test_cursor_locate.cpp
@@ -0,0 +1,800 @@
+// sorted_data_interface_test_cursor_locate.cpp
+
+/**
+ *    Copyright (C) 2014 MongoDB 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/storage/sorted_data_interface_test_harness.h"
+
+#include "mongo/db/storage/sorted_data_interface.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+
+    // Insert a key and try to locate it using a forward cursor
+    // by specifying its exact key and DiskLoc.
+    TEST( SortedDataInterface, Locate ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+            ASSERT( !cursor->locate( key1, loc1 ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( cursor->locate( key1, loc1 ) );
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Insert a key and try to locate it using a reverse cursor
+    // by specifying its exact key and DiskLoc.
+    TEST( SortedDataInterface, LocateReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+            ASSERT( !cursor->locate( key1, loc1 ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( cursor->locate( key1, loc1 ) );
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Insert a compound key and try to locate it using a forward cursor
+    // by specifying its exact key and DiskLoc.
+    TEST( SortedDataInterface, LocateCompoundKey ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+            ASSERT( !cursor->locate( compoundKey1a, loc1 ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey1a, loc1, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( cursor->locate( compoundKey1a, loc1 ) );
+            ASSERT_EQUALS( compoundKey1a, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Insert a compound key and try to locate it using a reverse cursor
+    // by specifying its exact key and DiskLoc.
+    TEST( SortedDataInterface, LocateCompoundKeyReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+            ASSERT( !cursor->locate( compoundKey1a, loc1 ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey1a, loc1, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( cursor->locate( compoundKey1a, loc1 ) );
+            ASSERT_EQUALS( compoundKey1a, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Insert multiple keys and try to locate them using a forward cursor
+    // by specifying their exact key and DiskLoc.
+    TEST( SortedDataInterface, LocateMultiple ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+            ASSERT( !cursor->locate( key1, loc1 ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc2, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( cursor->locate( key1, loc1 ) );
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( key2, cursor->getKey() );
+            ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc3, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( cursor->locate( key2, loc2 ) );
+            ASSERT_EQUALS( key2, cursor->getKey() );
+            ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( key3, cursor->getKey() );
+            ASSERT_EQUALS( loc3, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+
+            ASSERT( cursor->locate( key1, loc1 ) );
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( key2, cursor->getKey() );
+            ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( key3, cursor->getKey() );
+            ASSERT_EQUALS( loc3, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Insert multiple keys and try to locate them using a reverse cursor
+    // by specifying their exact key and DiskLoc.
+    TEST( SortedDataInterface, LocateMultipleReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+            ASSERT( !cursor->locate( key3, loc1 ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc2, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( cursor->locate( key2, loc2 ) );
+            ASSERT_EQUALS( key2, cursor->getKey() );
+            ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc3, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( cursor->locate( key2, loc2 ) );
+            ASSERT_EQUALS( key2, cursor->getKey() );
+            ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+
+            ASSERT( cursor->locate( key3, loc3 ) );
+            ASSERT_EQUALS( key3, cursor->getKey() );
+            ASSERT_EQUALS( loc3, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( key2, cursor->getKey() );
+            ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Insert multiple compound keys and try to locate them using a forward cursor
+    // by specifying their exact key and DiskLoc.
+    TEST( SortedDataInterface, LocateMultipleCompoundKeys ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+            ASSERT( !cursor->locate( compoundKey1a, loc1 ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey1a, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey1b, loc2, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey2b, loc3, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( cursor->locate( compoundKey1a, loc1 ) );
+            ASSERT_EQUALS( compoundKey1a, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( compoundKey1b, cursor->getKey() );
+            ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( compoundKey2b, cursor->getKey() );
+            ASSERT_EQUALS( loc3, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey1c, loc4, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey3a, loc5, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( cursor->locate( compoundKey1a, loc1 ) );
+            ASSERT_EQUALS( compoundKey1a, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( compoundKey1b, cursor->getKey() );
+            ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( compoundKey1c, cursor->getKey() );
+            ASSERT_EQUALS( loc4, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( compoundKey2b, cursor->getKey() );
+            ASSERT_EQUALS( loc3, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( compoundKey3a, cursor->getKey() );
+            ASSERT_EQUALS( loc5, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Insert multiple compound keys and try to locate them using a reverse cursor
+    // by specifying their exact key and DiskLoc.
+    TEST( SortedDataInterface, LocateMultipleCompoundKeysReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+            ASSERT( !cursor->locate( compoundKey3a, loc1 ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey1a, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey1b, loc2, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey2b, loc3, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( cursor->locate( compoundKey2b, loc3 ) );
+            ASSERT_EQUALS( compoundKey2b, cursor->getKey() );
+            ASSERT_EQUALS( loc3, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( compoundKey1b, cursor->getKey() );
+            ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( compoundKey1a, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey1c, loc4, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey3a, loc5, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( cursor->locate( compoundKey3a, loc5 ) );
+            ASSERT_EQUALS( compoundKey3a, cursor->getKey() );
+            ASSERT_EQUALS( loc5, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( compoundKey2b, cursor->getKey() );
+            ASSERT_EQUALS( loc3, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( compoundKey1c, cursor->getKey() );
+            ASSERT_EQUALS( loc4, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( compoundKey1b, cursor->getKey() );
+            ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( compoundKey1a, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Insert multiple keys and try to locate them using a forward cursor
+    // by specifying either a smaller key or DiskLoc.
+    TEST( SortedDataInterface, LocateIndirect ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+            ASSERT( !cursor->locate( key1, loc1 ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc2, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( !cursor->locate( key1, maxDiskLoc ) );
+            ASSERT_EQUALS( key2, cursor->getKey() );
+            ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc3, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( !cursor->locate( key1, minDiskLoc ) );
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( key2, cursor->getKey() );
+            ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( key3, cursor->getKey() );
+            ASSERT_EQUALS( loc3, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Insert multiple keys and try to locate them using a reverse cursor
+    // by specifying either a larger key or DiskLoc.
+    TEST( SortedDataInterface, LocateIndirectReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+            ASSERT( !cursor->locate( key3, loc1 ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc2, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( !cursor->locate( key2, minDiskLoc ) );
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc3, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( !cursor->locate( key3, maxDiskLoc ) );
+            ASSERT_EQUALS( key3, cursor->getKey() );
+            ASSERT_EQUALS( loc3, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( key2, cursor->getKey() );
+            ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Insert multiple compound keys and try to locate them using a forward cursor
+    // by specifying either a smaller key or DiskLoc.
+    TEST( SortedDataInterface, LocateIndirectCompoundKeys ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+            ASSERT( !cursor->locate( compoundKey1a, loc1 ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey1a, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey1b, loc2, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey2b, loc3, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( !cursor->locate( compoundKey1a, maxDiskLoc ) );
+            ASSERT_EQUALS( compoundKey1b, cursor->getKey() );
+            ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( compoundKey2b, cursor->getKey() );
+            ASSERT_EQUALS( loc3, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey1c, loc4, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey3a, loc5, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( !cursor->locate( compoundKey2a, loc1 ) );
+            ASSERT_EQUALS( compoundKey2b, cursor->getKey() );
+            ASSERT_EQUALS( loc3, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( compoundKey3a, cursor->getKey() );
+            ASSERT_EQUALS( loc5, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Insert multiple compound keys and try to locate them using a reverse cursor
+    // by specifying either a larger key or DiskLoc.
+    TEST( SortedDataInterface, LocateIndirectCompoundKeysReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+            ASSERT( !cursor->locate( compoundKey3a, loc1 ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey1a, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey1b, loc2, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey2b, loc3, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( !cursor->locate( compoundKey2b, minDiskLoc ) );
+            ASSERT_EQUALS( compoundKey1b, cursor->getKey() );
+            ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( compoundKey1a, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey1c, loc4, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey3a, loc5, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( !cursor->locate( compoundKey1d, loc1 ) );
+            ASSERT_EQUALS( compoundKey1c, cursor->getKey() );
+            ASSERT_EQUALS( loc4, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( compoundKey1b, cursor->getKey() );
+            ASSERT_EQUALS( loc2, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT_EQUALS( compoundKey1a, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+
+            cursor->advance();
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Call locate on a forward cursor of an empty index and verify that the cursor
+    // is positioned at EOF.
+    TEST( SortedDataInterface, LocateEmpty ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( !cursor->locate( BSONObj(), minDiskLoc ) );
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Call locate on a reverse cursor of an empty index and verify that the cursor
+    // is positioned at EOF.
+    TEST( SortedDataInterface, LocateEmptyReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( !cursor->locate( BSONObj(), maxDiskLoc ) );
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+} // namespace mongo
diff --git a/src/mongo/db/storage/sorted_data_interface_test_cursor_position.cpp b/src/mongo/db/storage/sorted_data_interface_test_cursor_position.cpp
new file mode 100644
index 00000000000..ee1c6f46b04
--- /dev/null
+++ b/src/mongo/db/storage/sorted_data_interface_test_cursor_position.cpp
@@ -0,0 +1,469 @@
+// sorted_data_interface_test_cursor_position.cpp
+
+/**
+ *    Copyright (C) 2014 MongoDB 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/storage/sorted_data_interface_test_harness.h"
+
+#include "mongo/db/storage/sorted_data_interface.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+
+    // Verify that two forward cursors positioned at EOF are considered
+    // to point to the same place.
+    TEST( SortedDataInterface, CursorsPointToSamePlaceIfEOF ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor1( sorted->newCursor( opCtx.get(), 1 ) );
+            scoped_ptr<SortedDataInterface::Cursor> cursor2( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( !cursor1->locate( minKey, minDiskLoc ) );
+            ASSERT( !cursor2->locate( minKey, minDiskLoc ) );
+            ASSERT( cursor1->isEOF() );
+            ASSERT( cursor2->isEOF() );
+            ASSERT( cursor1->pointsToSamePlaceAs( *cursor2 ) );
+            ASSERT( cursor2->pointsToSamePlaceAs( *cursor1 ) );
+        }
+    }
+
+    // Verify that two reverse cursors positioned at EOF are considered
+    // to point to the same place.
+    TEST( SortedDataInterface, CursorsPointToSamePlaceIfEOFReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor1( sorted->newCursor( opCtx.get(), -1 ) );
+            scoped_ptr<SortedDataInterface::Cursor> cursor2( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( !cursor1->locate( maxKey, maxDiskLoc ) );
+            ASSERT( !cursor2->locate( maxKey, maxDiskLoc ) );
+            ASSERT( cursor1->isEOF() );
+            ASSERT( cursor2->isEOF() );
+            ASSERT( cursor1->pointsToSamePlaceAs( *cursor2 ) );
+            ASSERT( cursor2->pointsToSamePlaceAs( *cursor1 ) );
+        }
+    }
+
+    // Iterate two forward cursors simultaneously and verify they are considered
+    // to point to the same place.
+    TEST( SortedDataInterface, CursorsPointToSamePlace ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc2, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 2, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor1( sorted->newCursor( opCtx.get(), 1 ) );
+            scoped_ptr<SortedDataInterface::Cursor> cursor2( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( cursor1->locate( key1, loc1 ) );
+            ASSERT( cursor2->locate( key1, loc1 ) );
+            ASSERT( cursor1->pointsToSamePlaceAs( *cursor2 ) );
+            ASSERT( cursor2->pointsToSamePlaceAs( *cursor1 ) );
+
+            cursor1->advance();
+            cursor2->advance();
+            ASSERT( cursor1->pointsToSamePlaceAs( *cursor2 ) );
+            ASSERT( cursor2->pointsToSamePlaceAs( *cursor1 ) );
+
+            cursor1->advance();
+            cursor2->advance();
+            ASSERT( cursor1->pointsToSamePlaceAs( *cursor2 ) );
+            ASSERT( cursor2->pointsToSamePlaceAs( *cursor1 ) );
+        }
+    }
+
+    // Iterate two reverse cursors simultaneously and verify they are considered
+    // to point to the same place.
+    TEST( SortedDataInterface, CursorsPointToSamePlaceReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc2, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 2, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor1( sorted->newCursor( opCtx.get(), -1 ) );
+            scoped_ptr<SortedDataInterface::Cursor> cursor2( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( cursor1->locate( key2, loc2 ) );
+            ASSERT( cursor2->locate( key2, loc2 ) );
+            ASSERT( cursor1->pointsToSamePlaceAs( *cursor2 ) );
+            ASSERT( cursor2->pointsToSamePlaceAs( *cursor1 ) );
+
+            cursor1->advance();
+            cursor2->advance();
+            ASSERT( cursor1->pointsToSamePlaceAs( *cursor2 ) );
+            ASSERT( cursor2->pointsToSamePlaceAs( *cursor1 ) );
+
+            cursor1->advance();
+            cursor2->advance();
+            ASSERT( cursor1->pointsToSamePlaceAs( *cursor2 ) );
+            ASSERT( cursor2->pointsToSamePlaceAs( *cursor1 ) );
+        }
+    }
+
+    // Verify that two forward cursors positioned at different keys are not considered
+    // to point to the same place.
+    TEST( SortedDataInterface, CursorsPointToDifferentKeys ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc2, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 2, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor1( sorted->newCursor( opCtx.get(), 1 ) );
+            scoped_ptr<SortedDataInterface::Cursor> cursor2( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( cursor1->locate( key1, loc1 ) );
+            ASSERT( cursor2->locate( key2, loc2 ) );
+            ASSERT( !cursor1->pointsToSamePlaceAs( *cursor2 ) );
+            ASSERT( !cursor2->pointsToSamePlaceAs( *cursor1 ) );
+        }
+    }
+
+    // Verify that two reverse cursors positioned at different keys are not considered
+    // to point to the same place.
+    TEST( SortedDataInterface, CursorsPointToDifferentKeysReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc2, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 2, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor1( sorted->newCursor( opCtx.get(), -1 ) );
+            scoped_ptr<SortedDataInterface::Cursor> cursor2( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( cursor1->locate( key1, loc1 ) );
+            ASSERT( cursor2->locate( key2, loc2 ) );
+            ASSERT( !cursor1->pointsToSamePlaceAs( *cursor2 ) );
+            ASSERT( !cursor2->pointsToSamePlaceAs( *cursor1 ) );
+        }
+    }
+
+    // Verify that two forward cursors positioned at a duplicate key, but with
+    // different DiskLocs are not considered to point to the same place.
+    TEST( SortedDataInterface, CursorsPointToDifferentDiskLocs ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc2, true /* allow duplicates */ ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 2, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor1( sorted->newCursor( opCtx.get(), 1 ) );
+            scoped_ptr<SortedDataInterface::Cursor> cursor2( sorted->newCursor( opCtx.get(), 1 ) );
+
+            ASSERT( cursor1->locate( key1, loc1 ) );
+            ASSERT( cursor2->locate( key1, loc2 ) );
+            ASSERT( !cursor1->pointsToSamePlaceAs( *cursor2 ) );
+            ASSERT( !cursor2->pointsToSamePlaceAs( *cursor1 ) );
+        }
+    }
+
+    // Verify that two reverse cursors positioned at a duplicate key, but with
+    // different DiskLocs are not considered to point to the same place.
+    TEST( SortedDataInterface, CursorsPointToDifferentDiskLocsReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc2, true /* allow duplicates */ ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 2, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor1( sorted->newCursor( opCtx.get(), -1 ) );
+            scoped_ptr<SortedDataInterface::Cursor> cursor2( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( cursor1->locate( key1, loc1 ) );
+            ASSERT( cursor2->locate( key1, loc2 ) );
+            ASSERT( !cursor1->pointsToSamePlaceAs( *cursor2 ) );
+            ASSERT( !cursor2->pointsToSamePlaceAs( *cursor1 ) );
+        }
+    }
+
+    // Verify that a forward cursor and a reverse cursor positioned at the same key
+    // are considered to point to the same place.
+    TEST( SortedDataInterface, CursorPointsToSamePlaceRegardlessOfDirection ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc2, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc3, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 3, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor1( sorted->newCursor( opCtx.get(), 1 ) );
+            scoped_ptr<SortedDataInterface::Cursor> cursor2( sorted->newCursor( opCtx.get(), -1 ) );
+
+            ASSERT( cursor1->locate( key1, loc1 ) );
+            ASSERT( cursor2->locate( key3, loc3 ) );
+            ASSERT( !cursor1->pointsToSamePlaceAs( *cursor2 ) );
+            ASSERT( !cursor2->pointsToSamePlaceAs( *cursor1 ) );
+
+            cursor1->advance();
+            cursor2->advance();
+            // SERVER-15480 the reverse cursor is incorrectly casted to a
+            //              cursor of type Heap1BtreeImpl::ForwardCursor
+            // ASSERT( cursor1->pointsToSamePlaceAs( *cursor2 ) );
+            // SERVER-15480 the forward cursor is incorrectly casted to a
+            //              cursor of type Heap1BtreeImpl::ReverseCursor
+            // ASSERT( cursor2->pointsToSamePlaceAs( *cursor1 ) );
+
+            cursor1->advance();
+            cursor2->advance();
+            ASSERT( !cursor1->pointsToSamePlaceAs( *cursor2 ) );
+            ASSERT( !cursor2->pointsToSamePlaceAs( *cursor1 ) );
+        }
+    }
+
+    // Verify that a forward cursor always points to the same place as itself.
+    TEST( SortedDataInterface, CursorPointsToSamePlaceAsItself ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        int nToInsert = 10;
+        for ( int i = 0; i < nToInsert; i++ ) {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                BSONObj key = BSON( "" << i );
+                DiskLoc loc( 42, i * 2 );
+                ASSERT_OK( sorted->insert( opCtx.get(), key, loc, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( nToInsert, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+            ASSERT( !cursor->locate( minKey, minDiskLoc ) );
+            for ( int i = 0; i < nToInsert; i++ ) {
+                ASSERT( !cursor->isEOF() );
+                ASSERT( cursor->pointsToSamePlaceAs( *cursor ) );
+                cursor->advance();
+            }
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Verify that a reverse cursor always points to the same place as itself.
+    TEST( SortedDataInterface, CursorPointsToSamePlaceAsItselfReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        int nToInsert = 10;
+        for ( int i = 0; i < nToInsert; i++ ) {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                BSONObj key = BSON( "" << i );
+                DiskLoc loc( 42, i * 2 );
+                ASSERT_OK( sorted->insert( opCtx.get(), key, loc, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( nToInsert, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+            ASSERT( !cursor->locate( maxKey, maxDiskLoc ) );
+            for ( int i = nToInsert - 1; i >= 0; i-- ) {
+                ASSERT( !cursor->isEOF() );
+                ASSERT( cursor->pointsToSamePlaceAs( *cursor ) );
+                cursor->advance();
+            }
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+} // namespace mongo
diff --git a/src/mongo/db/storage/sorted_data_interface_test_cursor_saverestore.cpp b/src/mongo/db/storage/sorted_data_interface_test_cursor_saverestore.cpp
new file mode 100644
index 00000000000..0d283e44b5d
--- /dev/null
+++ b/src/mongo/db/storage/sorted_data_interface_test_cursor_saverestore.cpp
@@ -0,0 +1,290 @@
+// sorted_data_interface_test_cursor_saverestore.cpp
+
+/**
+ *    Copyright (C) 2014 MongoDB 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/storage/sorted_data_interface_test_harness.h"
+
+#include "mongo/db/storage/sorted_data_interface.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+
+    // Insert multiple keys and try to iterate through all of them
+    // using a forward cursor while calling savePosition() and
+    // restorePosition() in succession.
+    TEST( SortedDataInterface, SaveAndRestorePositionWhileIterateCursor ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        int nToInsert = 10;
+        for ( int i = 0; i < nToInsert; i++ ) {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                BSONObj key = BSON( "" << i );
+                DiskLoc loc( 42, i * 2 );
+                ASSERT_OK( sorted->insert( opCtx.get(), key, loc, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( nToInsert, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+            ASSERT( !cursor->locate( minKey, minDiskLoc ) );
+            for ( int i = 0; i < nToInsert; i++ ) {
+                ASSERT( !cursor->isEOF() );
+                ASSERT_EQUALS( BSON( "" << i ), cursor->getKey() );
+                ASSERT_EQUALS( DiskLoc( 42, i * 2 ), cursor->getDiskLoc() );
+                cursor->advance();
+                cursor->savePosition();
+                cursor->restorePosition( opCtx.get() );
+            }
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Insert multiple keys and try to iterate through all of them
+    // using a reverse cursor while calling savePosition() and
+    // restorePosition() in succession.
+    TEST( SortedDataInterface, SaveAndRestorePositionWhileIterateCursorReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        int nToInsert = 10;
+        for ( int i = 0; i < nToInsert; i++ ) {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                BSONObj key = BSON( "" << i );
+                DiskLoc loc( 42, i * 2 );
+                ASSERT_OK( sorted->insert( opCtx.get(), key, loc, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( nToInsert, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+            ASSERT( !cursor->locate( maxKey, maxDiskLoc ) );
+            for ( int i = nToInsert - 1; i >= 0; i-- ) {
+                ASSERT( !cursor->isEOF() );
+                ASSERT_EQUALS( BSON( "" << i ), cursor->getKey() );
+                ASSERT_EQUALS( DiskLoc( 42, i * 2 ), cursor->getDiskLoc() );
+                cursor->advance();
+                cursor->savePosition();
+                cursor->restorePosition( opCtx.get() );
+            }
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Insert the same key multiple times and try to iterate through each
+    // occurrence using a forward cursor while calling savePosition() and
+    // restorePosition() in succession. Verify that the DiskLoc is saved
+    // as part of the current position of the cursor.
+    TEST( SortedDataInterface, SaveAndRestorePositionWhileIterateCursorWithDupKeys ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        int nToInsert = 10;
+        for ( int i = 0; i < nToInsert; i++ ) {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                DiskLoc loc( 42, i * 2 );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc, true /* allow duplicates */ ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( nToInsert, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+            ASSERT( !cursor->locate( minKey, minDiskLoc ) );
+            for ( int i = 0; i < nToInsert; i++ ) {
+                ASSERT( !cursor->isEOF() );
+                ASSERT_EQUALS( key1, cursor->getKey() );
+                ASSERT_EQUALS( DiskLoc( 42, i * 2 ), cursor->getDiskLoc() );
+                cursor->advance();
+                cursor->savePosition();
+                cursor->restorePosition( opCtx.get() );
+            }
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Insert the same key multiple times and try to iterate through each
+    // occurrence using a reverse cursor while calling savePosition() and
+    // restorePosition() in succession. Verify that the DiskLoc is saved
+    // as part of the current position of the cursor.
+    TEST( SortedDataInterface, SaveAndRestorePositionWhileIterateCursorWithDupKeysReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        int nToInsert = 10;
+        for ( int i = 0; i < nToInsert; i++ ) {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                DiskLoc loc( 42, i * 2 );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc, true /* allow duplicates */ ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( nToInsert, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+            ASSERT( !cursor->locate( maxKey, maxDiskLoc ) );
+            for ( int i = nToInsert - 1; i >= 0; i-- ) {
+                ASSERT( !cursor->isEOF() );
+                ASSERT_EQUALS( key1, cursor->getKey() );
+                ASSERT_EQUALS( DiskLoc( 42, i * 2 ), cursor->getDiskLoc() );
+                cursor->advance();
+                cursor->savePosition();
+                cursor->restorePosition( opCtx.get() );
+            }
+            ASSERT( cursor->isEOF() );
+        }
+    }
+
+    // Call savePosition() on a forward cursor without ever calling restorePosition().
+    // May be useful to run this test under valgrind to verify there are no leaks.
+    TEST( SortedDataInterface, SavePositionWithoutRestore ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 1, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), 1 ) );
+            cursor->savePosition();
+
+            ASSERT( cursor->locate( key1, loc1 ) );
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+        }
+    }
+
+    // Call savePosition() on a reverse cursor without ever calling restorePosition().
+    // May be useful to run this test under valgrind to verify there are no leaks.
+    TEST( SortedDataInterface, SavePositionWithoutRestoreReversed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 1, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            scoped_ptr<SortedDataInterface::Cursor> cursor( sorted->newCursor( opCtx.get(), -1 ) );
+            cursor->savePosition();
+
+            ASSERT( cursor->locate( key1, loc1 ) );
+            ASSERT_EQUALS( key1, cursor->getKey() );
+            ASSERT_EQUALS( loc1, cursor->getDiskLoc() );
+        }
+    }
+
+} // namespace mongo
diff --git a/src/mongo/db/storage/sorted_data_interface_test_dupkeycheck.cpp b/src/mongo/db/storage/sorted_data_interface_test_dupkeycheck.cpp
new file mode 100644
index 00000000000..359f80e9950
--- /dev/null
+++ b/src/mongo/db/storage/sorted_data_interface_test_dupkeycheck.cpp
@@ -0,0 +1,166 @@
+// sorted_data_interface_test_dupkeycheck.cpp
+
+/**
+ *    Copyright (C) 2014 MongoDB 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/storage/sorted_data_interface_test_harness.h"
+
+#include "mongo/db/storage/sorted_data_interface.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+
+    // Insert a key and verify that dupKeyCheck() returns a non-OK status for
+    // the same key. When dupKeyCheck() is called with the exact (key, DiskLoc)
+    // pair that was inserted, it should still return an OK status.
+    TEST( SortedDataInterface, DupKeyCheckAfterInsert ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 1, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->dupKeyCheck( opCtx.get(), key1, loc1 ) );
+                ASSERT_NOT_OK( sorted->dupKeyCheck( opCtx.get(), key1, minDiskLoc ) );
+                uow.commit();
+            }
+        }
+    }
+
+    // Verify that dupKeyCheck() returns an OK status for a key that does
+    // not exist in the index.
+    TEST( SortedDataInterface, DupKeyCheckEmpty ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->dupKeyCheck( opCtx.get(), key1, loc1 ) );
+                uow.commit();
+            }
+        }
+    }
+
+    // Insert a key and verify that dupKeyCheck() acknowledges the duplicate key, even
+    // when the insert key is located at a DiskLoc that comes after the one specified.
+    TEST( SortedDataInterface, DupKeyCheckWhenDiskLocBefore ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 1, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_NOT_OK( sorted->dupKeyCheck( opCtx.get(), key1, minDiskLoc ) );
+                uow.commit();
+            }
+        }
+    }
+
+    // Insert a key and verify that dupKeyCheck() acknowledges the duplicate key, even
+    // when the insert key is located at a DiskLoc that comes before the one specified.
+    TEST( SortedDataInterface, DupKeyCheckWhenDiskLocAfter ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 1, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_NOT_OK( sorted->dupKeyCheck( opCtx.get(), key1, maxDiskLoc ) );
+                uow.commit();
+            }
+        }
+    }
+
+} // namespace mongo
diff --git a/src/mongo/db/storage/sorted_data_interface_test_fullvalidate.cpp b/src/mongo/db/storage/sorted_data_interface_test_fullvalidate.cpp
new file mode 100644
index 00000000000..454ff7fab2f
--- /dev/null
+++ b/src/mongo/db/storage/sorted_data_interface_test_fullvalidate.cpp
@@ -0,0 +1,75 @@
+// sorted_data_interface_test_fullvalidate.cpp
+
+/**
+ *    Copyright (C) 2014 MongoDB 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/storage/sorted_data_interface_test_harness.h"
+
+#include "mongo/db/storage/sorted_data_interface.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+
+    // Insert multiple keys and verify that fullValidate() either sets
+    // the `numKeysOut` as the number of entries in the index, or as -1.
+    TEST( SortedDataInterface, FullValidate ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        int nToInsert = 10;
+        for ( int i = 0; i < nToInsert; i++ ) {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                BSONObj key = BSON( "" << i );
+                DiskLoc loc( 42, i * 2 );
+                ASSERT_OK( sorted->insert( opCtx.get(), key, loc, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( nToInsert, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            long long numKeysOut;
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            sorted->fullValidate( opCtx.get(), &numKeysOut );
+            // fullValidate() can set numKeysOut as the number of existing keys or -1.
+            ASSERT( numKeysOut == nToInsert || numKeysOut == -1 );
+        }
+    }
+
+} // namespace mongo
diff --git a/src/mongo/db/storage/sorted_data_interface_test_harness.cpp b/src/mongo/db/storage/sorted_data_interface_test_harness.cpp
index b65b9540718..b493d1bc728 100644
--- a/src/mongo/db/storage/sorted_data_interface_test_harness.cpp
+++ b/src/mongo/db/storage/sorted_data_interface_test_harness.cpp
@@ -32,7 +32,6 @@
 
 #include "mongo/db/storage/sorted_data_interface.h"
 #include "mongo/unittest/unittest.h"
-#include "mongo/unittest/temp_dir.h"
 
 namespace mongo {
 
@@ -592,4 +591,4 @@ namespace mongo {
         }
     }
 
-}
+} // namespace mongo
diff --git a/src/mongo/db/storage/sorted_data_interface_test_harness.h b/src/mongo/db/storage/sorted_data_interface_test_harness.h
index 3f68a726ede..380770eb9f3 100644
--- a/src/mongo/db/storage/sorted_data_interface_test_harness.h
+++ b/src/mongo/db/storage/sorted_data_interface_test_harness.h
@@ -30,10 +30,41 @@
 
 #pragma once
 
+#include "mongo/bson/bsonobj.h"
+#include "mongo/bson/bsonmisc.h"
+#include "mongo/db/diskloc.h"
 #include "mongo/db/operation_context_noop.h"
 
 namespace mongo {
 
+    const BSONObj key0 = BSON( "" << 0 );
+    const BSONObj key1 = BSON( "" << 1 );
+    const BSONObj key2 = BSON( "" << 2 );
+    const BSONObj key3 = BSON( "" << 3 );
+    const BSONObj key4 = BSON( "" << 4 );
+    const BSONObj key5 = BSON( "" << 5 );
+    const BSONObj key6 = BSON( "" << 6 );
+
+    const BSONObj compoundKey1a = BSON( "" << 1 << "" << "a" );
+    const BSONObj compoundKey1b = BSON( "" << 1 << "" << "b" );
+    const BSONObj compoundKey1c = BSON( "" << 1 << "" << "c" );
+    const BSONObj compoundKey1d = BSON( "" << 1 << "" << "d" );
+    const BSONObj compoundKey2a = BSON( "" << 2 << "" << "a" );
+    const BSONObj compoundKey2b = BSON( "" << 2 << "" << "b" );
+    const BSONObj compoundKey2c = BSON( "" << 2 << "" << "c" );
+    const BSONObj compoundKey3a = BSON( "" << 3 << "" << "a" );
+    const BSONObj compoundKey3b = BSON( "" << 3 << "" << "b" );
+    const BSONObj compoundKey3c = BSON( "" << 3 << "" << "c" );
+
+    const DiskLoc loc1( 10, 42 );
+    const DiskLoc loc2( 10, 44 );
+    const DiskLoc loc3( 10, 46 );
+    const DiskLoc loc4( 10, 48 );
+    const DiskLoc loc5( 10, 50 );
+    const DiskLoc loc6( 10, 52 );
+    const DiskLoc loc7( 10, 54 );
+    const DiskLoc loc8( 10, 56 );
+
     class RecoveryUnit;
     class SortedDataInterface;
 
diff --git a/src/mongo/db/storage/sorted_data_interface_test_insert.cpp b/src/mongo/db/storage/sorted_data_interface_test_insert.cpp
new file mode 100644
index 00000000000..3813c46eb1d
--- /dev/null
+++ b/src/mongo/db/storage/sorted_data_interface_test_insert.cpp
@@ -0,0 +1,338 @@
+// sorted_data_interface_test_insert.cpp
+
+/**
+ *    Copyright (C) 2014 MongoDB 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/storage/sorted_data_interface_test_harness.h"
+
+#include "mongo/db/storage/sorted_data_interface.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+
+    // Insert a key and verify that the number of entries in the index equals 1.
+    TEST( SortedDataInterface, Insert ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 1, sorted->numEntries( opCtx.get() ) );
+        }
+    }
+
+    // Insert a compound key and verify that the number of entries in the index equals 1.
+    TEST( SortedDataInterface, InsertCompoundKey ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey1a, loc1, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 1, sorted->numEntries( opCtx.get() ) );
+        }
+    }
+
+    // Insert multiple, distinct keys at the same DiskLoc and verify that the
+    // number of entries in the index equals the number that were inserted, even
+    // when duplicates are not allowed.
+    TEST( SortedDataInterface, InsertSameDiskLoc ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc1, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 2, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc1, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 3, sorted->numEntries( opCtx.get() ) );
+        }
+    }
+
+    // Insert multiple, distinct keys at the same DiskLoc and verify that the
+    // number of entries in the index equals the number that were inserted, even
+    // when duplicates are allowed.
+    TEST( SortedDataInterface, InsertSameDiskLocWithDupsAllowed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc1, true /* allow duplicates */ ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 2, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc1, true /* allow duplicates */ ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 3, sorted->numEntries( opCtx.get() ) );
+        }
+    }
+
+    // Insert the same key multiple times and verify that only 1 entry exists
+    // in the index when duplicates are not allowed.
+    TEST( SortedDataInterface, InsertSameKey ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_NOT_OK( sorted->insert( opCtx.get(), key1, loc2, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 1, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_NOT_OK( sorted->insert( opCtx.get(), key1, loc2, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 1, sorted->numEntries( opCtx.get() ) );
+        }
+    }
+
+    // Insert the same key multiple times and verify that all entries exists
+    // in the index when duplicates are allowed.
+    TEST( SortedDataInterface, InsertSameKeyWithDupsAllowed ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc2, true /* allow duplicates */ ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 2, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc3, true /* allow duplicates */ ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 3, sorted->numEntries( opCtx.get() ) );
+        }
+    }
+
+    // Insert multiple keys and verify that the number of entries
+    // in the index equals the number that were inserted.
+    TEST( SortedDataInterface, InsertMultiple ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc2, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 2, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc3, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 3, sorted->numEntries( opCtx.get() ) );
+        }
+    }
+
+    // Insert multiple compound keys and verify that the number of entries
+    // in the index equals the number that were inserted.
+    TEST( SortedDataInterface, InsertMultipleCompoundKeys ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey1a, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey1b, loc2, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey2b, loc3, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 3, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey1c, loc4, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey3a, loc5, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 5, sorted->numEntries( opCtx.get() ) );
+        }
+    }
+
+} // namespace mongo
diff --git a/src/mongo/db/storage/sorted_data_interface_test_isempty.cpp b/src/mongo/db/storage/sorted_data_interface_test_isempty.cpp
new file mode 100644
index 00000000000..f1d64c176fb
--- /dev/null
+++ b/src/mongo/db/storage/sorted_data_interface_test_isempty.cpp
@@ -0,0 +1,79 @@
+// sorted_data_interface_test_isempty.cpp
+
+/**
+ *    Copyright (C) 2014 MongoDB 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/storage/sorted_data_interface_test_harness.h"
+
+#include "mongo/db/storage/sorted_data_interface.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+
+    // Verify that isEmpty() returns true when the index is empty,
+    // returns false when a key is inserted, and returns true again
+    // when that is unindex.
+    TEST( SortedDataInterface, IsEmpty ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( !sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT( sorted->unindex( opCtx.get(), key1, loc1 ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+    }
+
+} // namespace mongo
diff --git a/src/mongo/db/storage/sorted_data_interface_test_rollback.cpp b/src/mongo/db/storage/sorted_data_interface_test_rollback.cpp
new file mode 100644
index 00000000000..b0af87362ba
--- /dev/null
+++ b/src/mongo/db/storage/sorted_data_interface_test_rollback.cpp
@@ -0,0 +1,150 @@
+// sorted_data_interface_test_rollback.cpp
+
+/**
+ *    Copyright (C) 2014 MongoDB 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/storage/sorted_data_interface_test_harness.h"
+
+#include "mongo/db/storage/sorted_data_interface.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+
+    // Insert multiple keys and verify that omitting the commit()
+    // on the WriteUnitOfWork causes the changes to not become visible.
+    TEST( SortedDataInterface, InsertWithoutCommit ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                // no commit
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc2, false ) );
+                // no commit
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+    }
+
+    // Insert multiple keys, then unindex those same keys and verify that
+    // omitting the commit() on the WriteUnitOfWork causes the changes to
+    // not become visible.
+    TEST( SortedDataInterface, UnindexWithoutCommit ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc2, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 2, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT( sorted->unindex( opCtx.get(), key2, loc2 ) );
+                // no commit
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 2, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc3, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 3, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT( sorted->unindex( opCtx.get(), key1, loc1 ) );
+                ASSERT( sorted->unindex( opCtx.get(), key3, loc3 ) );
+                // no commit
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 3, sorted->numEntries( opCtx.get() ) );
+        }
+    }
+
+} // namespace mongo
diff --git a/src/mongo/db/storage/sorted_data_interface_test_spaceused.cpp b/src/mongo/db/storage/sorted_data_interface_test_spaceused.cpp
new file mode 100644
index 00000000000..518bb12ba75
--- /dev/null
+++ b/src/mongo/db/storage/sorted_data_interface_test_spaceused.cpp
@@ -0,0 +1,101 @@
+// sorted_data_interface_test_spaceused.cpp
+
+/**
+ *    Copyright (C) 2014 MongoDB 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/storage/sorted_data_interface_test_harness.h"
+
+#include "mongo/db/storage/sorted_data_interface.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+
+    // Verify that an empty index takes up no space.
+    TEST( SortedDataInterface, GetSpaceUsedBytesEmpty ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        // SERVER-15416 mmapv1 test harness does not use SimpleRecordStoreV1 as its record store
+        //              and HeapRecordStoreBtree::dataSize does not have an actual implementation
+        // {
+        //     scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+        //     ASSERT( sorted->getSpaceUsedBytes( opCtx.get() ) == 0 );
+        // }
+    }
+
+    // Verify that a nonempty index takes up some space.
+    TEST( SortedDataInterface, GetSpaceUsedBytesNonEmpty ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        int nToInsert = 10;
+        for ( int i = 0; i < nToInsert; i++ ) {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                BSONObj key = BSON( "" << i );
+                DiskLoc loc( 42, i * 2 );
+                ASSERT_OK( sorted->insert( opCtx.get(), key, loc, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( nToInsert, sorted->numEntries( opCtx.get() ) );
+        }
+
+        // SERVER-15416 mmapv1 test harness does not use SimpleRecordStoreV1 as its record store
+        //              and HeapRecordStoreBtree::dataSize does not have an actual implementation
+        // long long spaceUsedBytes;
+        // {
+        //     scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+        //     spaceUsedBytes = sorted->getSpaceUsedBytes( opCtx.get() );
+        //     ASSERT( spaceUsedBytes > 0 );
+        // }
+
+        // {
+        //     // getSpaceUsedBytes() returns the same value when called multiple times
+        //     // and there were not interleaved write operations.
+        //     scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+        //     ASSERT_EQUALS( spaceUsedBytes, sorted->getSpaceUsedBytes( opCtx.get() ) );
+        //     ASSERT_EQUALS( spaceUsedBytes, sorted->getSpaceUsedBytes( opCtx.get() ) );
+        // }
+    }
+
+} // namespace mongo
diff --git a/src/mongo/db/storage/sorted_data_interface_test_touch.cpp b/src/mongo/db/storage/sorted_data_interface_test_touch.cpp
new file mode 100644
index 00000000000..c1b10277ae0
--- /dev/null
+++ b/src/mongo/db/storage/sorted_data_interface_test_touch.cpp
@@ -0,0 +1,51 @@
+// sorted_data_interface_test_touch.cpp
+
+/**
+ *    Copyright (C) 2014 MongoDB 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/storage/sorted_data_interface_test_harness.h"
+
+#include "mongo/db/storage/sorted_data_interface.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+
+    // Verify that calling touch() returns an OK status.
+    TEST( SortedDataInterface, Touch ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            // XXX does not verify the index was brought into memory
+            //     (even if supported by storage engine)
+            ASSERT_OK( sorted->touch( opCtx.get() ) );
+        }
+    }
+
+} // namespace mongo
diff --git a/src/mongo/db/storage/sorted_data_interface_test_unindex.cpp b/src/mongo/db/storage/sorted_data_interface_test_unindex.cpp
new file mode 100644
index 00000000000..3797f15dca7
--- /dev/null
+++ b/src/mongo/db/storage/sorted_data_interface_test_unindex.cpp
@@ -0,0 +1,274 @@
+// sorted_data_interface_test_unindex.cpp
+
+/**
+ *    Copyright (C) 2014 MongoDB 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/storage/sorted_data_interface_test_harness.h"
+
+#include "mongo/db/storage/sorted_data_interface.h"
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+
+    // Insert a key and verify that it can be unindexed.
+    TEST( SortedDataInterface, Unindex ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 1, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT( sorted->unindex( opCtx.get(), key1, loc1 ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+    }
+
+    // Insert a compound key and verify that it can be unindexed.
+    TEST( SortedDataInterface, UnindexCompoundKey ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), compoundKey1a, loc1, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 1, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT( sorted->unindex( opCtx.get(), compoundKey1a, loc1 ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+    }
+
+    // Insert multiple, distinct keys and verify that they can be unindexed.
+    TEST( SortedDataInterface, UnindexMultipleDistinct ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key2, loc2, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 2, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT( sorted->unindex( opCtx.get(), key2, loc2 ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 1, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key3, loc3, false ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 2, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT( sorted->unindex( opCtx.get(), key1, loc1 ) );
+                ASSERT( sorted->unindex( opCtx.get(), key3, loc3 ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+    }
+
+    // Insert the same key multiple times and verify that each occurrence can be unindexed.
+    TEST( SortedDataInterface, UnindexMultipleSameKey ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc1, false ) );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc2, true /* allow duplicates */ ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 2, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT( sorted->unindex( opCtx.get(), key1, loc2 ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 1, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT_OK( sorted->insert( opCtx.get(), key1, loc3, true /* allow duplicates */ ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT_EQUALS( 2, sorted->numEntries( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT( sorted->unindex( opCtx.get(), key1, loc1 ) );
+                ASSERT( sorted->unindex( opCtx.get(), key1, loc3 ) );
+                uow.commit();
+            }
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+    }
+
+    // Call unindex() on a nonexistent key and verify the result is false.
+    TEST( SortedDataInterface, UnindexEmpty ) {
+        scoped_ptr<HarnessHelper> harnessHelper( newHarnessHelper() );
+        scoped_ptr<SortedDataInterface> sorted( harnessHelper->newSortedDataInterface() );
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            ASSERT( sorted->isEmpty( opCtx.get() ) );
+        }
+
+        {
+            scoped_ptr<OperationContext> opCtx( harnessHelper->newOperationContext() );
+            {
+                WriteUnitOfWork uow( opCtx.get() );
+                ASSERT( !sorted->unindex( opCtx.get(), key1, loc1 ) );
+                uow.commit();
+            }
+        }
+    }
+
+} // namespace mongo