Index: lsm-test/lsmtest.h
==================================================================
--- lsm-test/lsmtest.h
+++ lsm-test/lsmtest.h
@@ -44,10 +44,11 @@
 };
 struct DatabaseMethods {
   int (*xClose)(TestDb *);
   int (*xWrite)(TestDb *, void *, int , void *, int);
   int (*xDelete)(TestDb *, void *, int);
+  int (*xDeleteRange)(TestDb *, void *, int, void *, int);
   int (*xFetch)(TestDb *, void *, int, void **, int *);
   int (*xScan)(TestDb *, void *, int, void *, int, void *, int,
     void (*)(void *, void *, int , void *, int)
   );
   int (*xBegin)(TestDb *, int);
@@ -119,12 +120,14 @@
 char *testMallocPrintf(const char *zFormat, ...);
 char *testMallocVPrintf(const char *zFormat, va_list ap);
 int testGlobMatch(const char *zPattern, const char *zStr);
 
 void testScanCompare(TestDb *, TestDb *, int, void *, int, void *, int, int *);
+void testFetchCompare(TestDb *, TestDb *, void *, int, int *);
 
 void *testMalloc(int);
+void *testMallocCopy(void *pCopy, int nByte);
 void *testRealloc(void *, int);
 void testFree(void *);
 
 /* testio.c */
 int testVfsConfigureDb(TestDb *pDb);
@@ -192,13 +195,12 @@
 void testDeleteDatasource(TestDb *, Datasource *, int, int *);
 void testDeleteDatasourceRange(TestDb *, Datasource *, int, int, int *);
 
 
 /* test1.c */
-void test_data_1(TestDb *pDb, int *pRc);
-void test_data_2(TestDb *pDb, int *pRc);
-void test_data_3(const char *, const char *, int *pRc);
+void test_data_1(const char *, const char *, int *pRc);
+void test_data_2(const char *, const char *, int *pRc);
 void testDbContents(TestDb *, Datasource *, int, int, int, int, int, int *);
 void testCaseProgress(int, int, int, int *);
 int testCaseNDot(void);
 
 typedef struct CksumDb CksumDb;

Index: lsm-test/lsmtest1.c
==================================================================
--- lsm-test/lsmtest1.c
+++ lsm-test/lsmtest1.c
@@ -2,17 +2,12 @@
 #include "lsmtest.h"
 
 #define DATA_SEQUENTIAL TEST_DATASOURCE_SEQUENCE
 #define DATA_RANDOM     TEST_DATASOURCE_RANDOM
 
-typedef struct Datatest Datatest;
-typedef struct MinMax MinMax;
-
-struct MinMax {
-  int nMin;
-  int nMax;
-};
+typedef struct Datatest1 Datatest1;
+typedef struct Datatest2 Datatest2;
 
 /*
 ** An instance of the following structure contains parameters used to
 ** customize the test function in this file. Test procedure:
 **
@@ -21,11 +16,11 @@
 **   2. Insert nRow key value pairs into the database.
 **
 **   3. Delete all keys from the database. Deletes are done in the same 
 **      order as the inserts.
 **
-** During steps 2 and 3 above, after each Datatest.nVerify inserts or
+** During steps 2 and 3 above, after each Datatest1.nVerify inserts or
 ** deletes, the following:
 **
 **   a. Run Datasource.nTest key lookups and check the results are as expected.
 **
 **   b. If Datasource.bTestScan is true, run a handful (8) of range
@@ -32,11 +27,11 @@
 **      queries (scanning forwards and backwards). Check that the results
 **      are as expected.
 **
 **   c. Close and reopen the database. Then run (a) and (b) again.
 */
-struct Datatest {
+struct Datatest1 {
   /* Datasource definition */
   DatasourceDefn defn;
 
   /* Test procedure parameters */
   int nRow;                       /* Number of rows to insert then delete */
@@ -43,11 +38,52 @@
   int nVerify;                    /* How often to verify the db contents */
   int nTest;                      /* Number of keys to test (0==all) */
   int bTestScan;                  /* True to do scan tests */
 };
 
-static char *getName(const char *zSystem, Datatest *pTest){
+/*
+** An instance of the following data structure is used to describe the
+** second type of test case in this file. The chief difference between 
+** these tests and those described by Datatest1 is that these tests also
+** experiment with range-delete operations. Tests proceed as follows:
+**
+**     1. Open the datasource described by Datatest2.defn. 
+**
+**     2. Open a connection on an empty database.
+**
+**     3. Do this Datatest2.nIter times:
+**
+**        a) Insert Datatest2.nWrite key-value pairs from the datasource.
+**
+**        b) Select two pseudo-random keys and use them as the start
+**           and end points of a range-delete operation.
+**
+**        c) Verify that the contents of the database are as expected (see
+**           below for details).
+**
+**        d) Close and then reopen the database handle.
+**
+**        e) Verify that the contents of the database are still as expected.
+**
+** The inserts and range deletes are run twice - once on the database being
+** tested and once using a control system (sqlite3, kc etc. - something that 
+** works). In order to verify that the contents of the db being tested are
+** correct, the test runs a bunch of scans and lookups on both the test and
+** control databases. If the results are the same, the test passes.
+*/
+struct Datatest2 {
+  DatasourceDefn defn;
+  int nRange;
+  int nWrite;                     /* Number of writes per iteration */
+  int nIter;                      /* Total number of iterations to run */
+};
+
+/*
+** Generate a unique name for the test case pTest with database system
+** zSystem.
+*/
+static char *getName(const char *zSystem, Datatest1 *pTest){
   char *zRet;
   char *zData;
   zData = testDatasourceName(&pTest->defn);
   zRet = testMallocPrintf("data.%s.%s.%d.%d", 
       zSystem, zData, pTest->nRow, pTest->nVerify
@@ -213,13 +249,13 @@
   printf("%s\n", (char *)pKey);
   fflush(stdout);
 }
 #endif
 
-static void doDataTest(
+static void doDataTest1(
   const char *zSystem,            /* Database system to test */
-  Datatest *p,                    /* Structure containing test parameters */
+  Datatest1 *p,                   /* Structure containing test parameters */
   int *pRc                        /* OUT: Error code */
 ){
   int i;
   int iDot;
   int rc = LSM_OK;
@@ -278,16 +314,16 @@
   testCaseFinish(rc);
   *pRc = rc;
 }
 
 
-void test_data_3(
+void test_data_1(
   const char *zSystem,            /* Database system name */
   const char *zPattern,           /* Run test cases that match this pattern */
   int *pRc                        /* IN/OUT: Error code */
 ){
-  Datatest aTest[] = {
+  Datatest1 aTest[] = {
     { {DATA_RANDOM,     20,25,     100,200},       1000,  250, 1000, 1},
     { {DATA_RANDOM,     8,10,      100,200},       1000,  250, 1000, 1},
     { {DATA_RANDOM,     8,10,      10,20},         1000,  250, 1000, 1},
     { {DATA_RANDOM,     8,10,      1000,2000},     1000,  250, 1000, 1},
     { {DATA_RANDOM,     8,100,     10000,20000},    100,   25,  100, 1},
@@ -304,10 +340,149 @@
   int i;
 
   for(i=0; *pRc==LSM_OK && i<ArraySize(aTest); i++){
     char *zName = getName(zSystem, &aTest[i]);
     if( testCaseBegin(pRc, zPattern, "%s", zName) ){
-      doDataTest(zSystem, &aTest[i], pRc);
+      doDataTest1(zSystem, &aTest[i], pRc);
+    }
+    testFree(zName);
+  }
+}
+
+static void testCompareDb(
+  Datasource *pData,
+  int nData,
+  int iSeed,
+  TestDb *pControl,
+  TestDb *pDb,
+  int *pRc
+){
+  int i;
+
+  testScanCompare(pControl, pDb, 0, 0, 0,         0, 0,         pRc);
+  testScanCompare(pControl, pDb, 1, 0, 0,         0, 0,         pRc);
+
+  if( *pRc==0 ){
+    int iKey1;
+    int iKey2;
+    void *pKey1; int nKey1;       /* Start key */
+    void *pKey2; int nKey2;       /* Final key */
+
+    iKey1 = testPrngValue(iSeed) % nData;
+    iKey2 = testPrngValue(iSeed+1) % nData;
+    testDatasourceEntry(pData, iKey1, &pKey2, &nKey1, 0, 0);
+    pKey1 = testMalloc(nKey1+1);
+    memcpy(pKey1, pKey2, nKey1+1);
+    testDatasourceEntry(pData, iKey2, &pKey2, &nKey2, 0, 0);
+
+    testScanCompare(pControl, pDb, 0, 0, 0,         pKey2, nKey2, pRc);
+    testScanCompare(pControl, pDb, 0, pKey1, nKey1, 0, 0,         pRc);
+    testScanCompare(pControl, pDb, 0, pKey1, nKey1, pKey2, nKey2, pRc);
+    testScanCompare(pControl, pDb, 1, 0, 0,         pKey2, nKey2, pRc);
+    testScanCompare(pControl, pDb, 1, pKey1, nKey1, 0, 0,         pRc);
+    testScanCompare(pControl, pDb, 1, pKey1, nKey1, pKey2, nKey2, pRc);
+    testFree(pKey1);
+  }
+
+  for(i=0; i<nData && *pRc==0; i++){
+    void *pKey; int nKey;
+    testDatasourceEntry(pData, i, &pKey, &nKey, 0, 0);
+    testFetchCompare(pControl, pDb, pKey, nKey, pRc);
+  }
+}
+
+static void doDataTest2(
+  const char *zSystem,            /* Database system to test */
+  Datatest2 *p,                   /* Structure containing test parameters */
+  int *pRc                        /* OUT: Error code */
+){
+  TestDb *pDb;
+  TestDb *pControl;
+  Datasource *pData;
+  int i;
+  int rc = LSM_OK;
+  int iDot = 0;
+
+  /* Start the test case, open a database and allocate the datasource. */
+  pDb = testOpen(zSystem, 1, &rc);
+  pData = testDatasourceNew(&p->defn);
+  rc = testControlDb(&pControl);
+
+  if( tdb_lsm(pDb) ){
+    int nBuf = 32 * 1024 * 1024;
+    lsm_config(tdb_lsm(pDb), LSM_CONFIG_WRITE_BUFFER, &nBuf);
+  }
+
+  for(i=0; rc==0 && i<p->nIter; i++){
+    void *pKey1; int nKey1;
+    void *pKey2; int nKey2;
+    int ii;
+    int nRange = MIN(p->nIter*p->nWrite, p->nRange);
+
+    for(ii=0; rc==0 && ii<p->nWrite; ii++){
+      int iKey = (i*p->nWrite + ii) % p->nRange;
+      testWriteDatasource(pControl, pData, iKey, &rc);
+      testWriteDatasource(pDb, pData, iKey, &rc);
+    }
+
+    testDatasourceEntry(pData, i+1000000, &pKey1, &nKey1, 0, 0);
+    pKey1 = testMallocCopy(pKey1, nKey1);
+    testDatasourceEntry(pData, i+2000000, &pKey2, &nKey2, 0, 0);
+
+    testDeleteRange(pDb, pKey1, nKey1, pKey2, nKey2, &rc);
+    testDeleteRange(pControl, pKey1, nKey1, pKey2, nKey2, &rc);
+    testFree(pKey1);
+
+    testCompareDb(pData, nRange, i, pControl, pDb, &rc);
+    testReopen(&pDb, &rc);
+    testCompareDb(pData, nRange, i, pControl, pDb, &rc);
+
+    /* Update the progress dots... */
+    testCaseProgress(i, p->nIter, testCaseNDot(), &iDot);
+  }
+
+  testClose(&pDb);
+  testClose(&pControl);
+  testDatasourceFree(pData);
+  testCaseFinish(rc);
+  *pRc = rc;
+}
+
+static char *getName2(const char *zSystem, Datatest2 *pTest){
+  char *zRet;
+  char *zData;
+  zData = testDatasourceName(&pTest->defn);
+  zRet = testMallocPrintf("data2.%s.%s.%d.%d.%d", 
+      zSystem, zData, pTest->nRange, pTest->nWrite, pTest->nIter
+  );
+  testFree(zData);
+  return zRet;
+}
+
+void test_data_2(
+  const char *zSystem,            /* Database system name */
+  const char *zPattern,           /* Run test cases that match this pattern */
+  int *pRc                        /* IN/OUT: Error code */
+){
+  Datatest2 aTest[] = {
+      /* defn,                                 nRange, nWrite, nIter */
+    { {DATA_RANDOM,     20,25,     100,200},   10000,  10,     50   },
+    { {DATA_RANDOM,     20,25,     100,200},   10000,  200,    50   },
+    { {DATA_RANDOM,     20,25,     100,200},   100,    10,     1000 },
+    { {DATA_RANDOM,     20,25,     100,200},   100,    200,    50   },
+
+#if 0
+    { {DATA_RANDOM,     20,25,     100,200},       200, 50 }
+#endif
+  };
+
+  int i;
+
+  for(i=0; *pRc==LSM_OK && i<ArraySize(aTest); i++){
+    char *zName = getName2(zSystem, &aTest[i]);
+    if( testCaseBegin(pRc, zPattern, "%s", zName) ){
+      doDataTest2(zSystem, &aTest[i], pRc);
     }
     testFree(zName);
   }
 }
+

Index: lsm-test/lsmtest8.c
==================================================================
--- lsm-test/lsmtest8.c
+++ lsm-test/lsmtest8.c
@@ -303,12 +303,12 @@
 void do_writer_crash_test(const char *zPattern, int *pRc){
   struct Test {
     const char *zName;
     void (*xFunc)(int *);
   } aTest[] = {
-    { "writercrash2.lsm", doWriterCrash2 },
     { "writercrash1.lsm", doWriterCrash1 },
+    { "writercrash2.lsm", doWriterCrash2 },
   };
   int i;
   for(i=0; i<ArraySize(aTest); i++){
     struct Test *p = &aTest[i];
     if( testCaseBegin(pRc, zPattern, p->zName) ){

Index: lsm-test/lsmtest_main.c
==================================================================
--- lsm-test/lsmtest_main.c
+++ lsm-test/lsmtest_main.c
@@ -71,11 +71,23 @@
   void *pKey, int nKey,           /* Key to query database for */
   int *pRc                        /* IN/OUT: Error code */
 ){
   if( *pRc==0 ){
     int rc;
-    rc = tdb_delete(pDb, pKey, nKey);
+    *pRc = rc = tdb_delete(pDb, pKey, nKey);
+    testSetError(rc);
+  }
+}
+void testDeleteRange(
+  TestDb *pDb,                    /* Database handle */
+  void *pKey1, int nKey1,
+  void *pKey2, int nKey2,
+  int *pRc                        /* IN/OUT: Error code */
+){
+  if( *pRc==0 ){
+    int rc;
+    *pRc = rc = tdb_delete_range(pDb, pKey1, nKey1, pKey2, nKey2);
     testSetError(rc);
   }
 }
 
 void testBegin(TestDb *pDb, int iTrans, int *pRc){
@@ -122,11 +134,11 @@
 ){
   int nVal = (zVal ? strlen(zVal) : 0);
   testFetch(pDb, (void *)zKey, strlen(zKey), (void *)zVal, nVal, pRc);
 }
 
-static void testFetchCompare(
+void testFetchCompare(
   TestDb *pDb1, 
   TestDb *pDb2, 
   void *pKey, int nKey, 
   int *pRc
 ){
@@ -133,10 +145,13 @@
   int rc;
   void *pDbVal1;
   void *pDbVal2;
   int nDbVal1;
   int nDbVal2;
+
+  static int nCall = 0;
+  nCall++;
 
   rc = tdb_fetch(pDb1, pKey, nKey, &pDbVal1, &nDbVal1);
   testSetError(rc);
 
   rc = tdb_fetch(pDb2, pKey, nKey, &pDbVal2, &nDbVal2);
@@ -183,11 +198,14 @@
   ScanResult *p = (ScanResult *)pCtx;
   u8 *aKey = (u8 *)pKey;
   u8 *aVal = (u8 *)pVal;
   int i;
 
-  if( test_scan_debug ) printf("%.*s\n", nKey, (char *)pKey);
+  if( test_scan_debug ){
+    printf("%d: %.*s\n", p->nRow, nKey, (char *)pKey);
+    fflush(stdout);
+  }
 #if 0
   if( test_scan_debug ) printf("%.20s\n", (char *)pVal);
 #endif
 
 #if 0
@@ -371,10 +389,16 @@
 void *testMalloc(int n){
   void *pRet = malloc(n);
   memset(pRet, 0, n);
   return pRet;
 }
+
+void *testMallocCopy(void *pCopy, int nByte){
+  void *pRet = testMalloc(nByte);
+  memcpy(pRet, pCopy, nByte);
+  return pRet;
+}
 
 void *testRealloc(void *p, int n){
   return realloc(p, n);
 }
 
@@ -434,11 +458,12 @@
   }
 
   for(j=0; tdb_system_name(j); j++){
     rc = 0;
 
-    test_data_3(tdb_system_name(j), zPattern, &rc);
+    test_data_1(tdb_system_name(j), zPattern, &rc);
+    test_data_2(tdb_system_name(j), zPattern, &rc);
     test_rollback(tdb_system_name(j), zPattern, &rc);
     test_mc(tdb_system_name(j), zPattern, &rc);
     test_mt(tdb_system_name(j), zPattern, &rc);
 
     if( rc ) nFail++;

Index: lsm-test/lsmtest_tdb.c
==================================================================
--- lsm-test/lsmtest_tdb.c
+++ lsm-test/lsmtest_tdb.c
@@ -179,10 +179,11 @@
 static int test_leveldb_open(const char *zFilename, int bClear, TestDb **ppDb){
   static const DatabaseMethods LeveldbMethods = {
     test_leveldb_close,
     test_leveldb_write,
     test_leveldb_delete,
+    0,
     test_leveldb_fetch,
     test_leveldb_scan,
     error_transaction_function,
     error_transaction_function,
     error_transaction_function
@@ -309,10 +310,11 @@
 struct SqlDb {
   TestDb base;
   sqlite3 *db;
   sqlite3_stmt *pInsert;
   sqlite3_stmt *pDelete;
+  sqlite3_stmt *pDeleteRange;
   sqlite3_stmt *pFetch;
   sqlite3_stmt *apScan[8];
 
   int nOpenTrans;
 
@@ -323,10 +325,11 @@
 
 static int sql_close(TestDb *pTestDb){
   SqlDb *pDb = (SqlDb *)pTestDb;
   sqlite3_finalize(pDb->pInsert);
   sqlite3_finalize(pDb->pDelete);
+  sqlite3_finalize(pDb->pDeleteRange);
   sqlite3_finalize(pDb->pFetch);
   sqlite3_finalize(pDb->apScan[0]);
   sqlite3_finalize(pDb->apScan[1]);
   sqlite3_finalize(pDb->apScan[2]);
   sqlite3_finalize(pDb->apScan[3]);
@@ -358,10 +361,22 @@
   SqlDb *pDb = (SqlDb *)pTestDb;
   sqlite3_bind_blob(pDb->pDelete, 1, pKey, nKey, SQLITE_STATIC);
   sqlite3_step(pDb->pDelete);
   return sqlite3_reset(pDb->pDelete);
 }
+
+static int sql_delete_range(
+  TestDb *pTestDb, 
+  void *pKey1, int nKey1,
+  void *pKey2, int nKey2
+){
+  SqlDb *pDb = (SqlDb *)pTestDb;
+  sqlite3_bind_blob(pDb->pDeleteRange, 1, pKey1, nKey1, SQLITE_STATIC);
+  sqlite3_bind_blob(pDb->pDeleteRange, 2, pKey2, nKey2, SQLITE_STATIC);
+  sqlite3_step(pDb->pDeleteRange);
+  return sqlite3_reset(pDb->pDeleteRange);
+}
 
 static int sql_fetch(
   TestDb *pTestDb, 
   void *pKey, 
   int nKey, 
@@ -510,19 +525,21 @@
 static int sql_open(const char *zFilename, int bClear, TestDb **ppDb){
   static const DatabaseMethods SqlMethods = {
     sql_close,
     sql_write,
     sql_delete,
+    sql_delete_range,
     sql_fetch,
     sql_scan,
     sql_begin,
     sql_commit,
     sql_rollback
   };
   const char *zCreate = "CREATE TABLE IF NOT EXISTS t1(k PRIMARY KEY, v)";
   const char *zInsert = "REPLACE INTO t1 VALUES(?, ?)";
   const char *zDelete = "DELETE FROM t1 WHERE k = ?";
+  const char *zRange = "DELETE FROM t1 WHERE k>? AND k<?";
   const char *zFetch  = "SELECT v FROM t1 WHERE k = ?";
 
   const char *zScan0  = "SELECT * FROM t1 WHERE k BETWEEN ?1 AND ?2 ORDER BY k";
   const char *zScan1  = "SELECT * FROM t1 WHERE k <= ?2 ORDER BY k";
   const char *zScan2  = "SELECT * FROM t1 WHERE k >= ?1 ORDER BY k";
@@ -548,10 +565,11 @@
 
   if( 0!=(rc = sqlite3_open(zFilename, &pDb->db))
    || 0!=(rc = sqlite3_exec(pDb->db, zCreate, 0, 0, 0))
    || 0!=(rc = sqlite3_prepare_v2(pDb->db, zInsert, -1, &pDb->pInsert, 0))
    || 0!=(rc = sqlite3_prepare_v2(pDb->db, zDelete, -1, &pDb->pDelete, 0))
+   || 0!=(rc = sqlite3_prepare_v2(pDb->db, zRange, -1, &pDb->pDeleteRange, 0))
    || 0!=(rc = sqlite3_prepare_v2(pDb->db, zFetch, -1, &pDb->pFetch, 0))
    || 0!=(rc = sqlite3_prepare_v2(pDb->db, zScan0, -1, &pDb->apScan[0], 0))
    || 0!=(rc = sqlite3_prepare_v2(pDb->db, zScan1, -1, &pDb->apScan[1], 0))
    || 0!=(rc = sqlite3_prepare_v2(pDb->db, zScan2, -1, &pDb->apScan[2], 0))
    || 0!=(rc = sqlite3_prepare_v2(pDb->db, zScan3, -1, &pDb->apScan[3], 0))
@@ -646,10 +664,16 @@
 }
 
 int tdb_delete(TestDb *pDb, void *pKey, int nKey){
   return pDb->pMethods->xDelete(pDb, pKey, nKey);
 }
+
+int tdb_delete_range(
+    TestDb *pDb, void *pKey1, int nKey1, void *pKey2, int nKey2
+){
+  return pDb->pMethods->xDeleteRange(pDb, pKey1, nKey1, pKey2, nKey2);
+}
 
 int tdb_fetch(TestDb *pDb, void *pKey, int nKey, void **ppVal, int *pnVal){
   return pDb->pMethods->xFetch(pDb, pKey, nKey, ppVal, pnVal);
 }
 

Index: lsm-test/lsmtest_tdb.h
==================================================================
--- lsm-test/lsmtest_tdb.h
+++ lsm-test/lsmtest_tdb.h
@@ -48,10 +48,15 @@
 /*
 ** Delete a key from the database.
 */
 int tdb_delete(TestDb *pDb, void *pKey, int nKey);
 
+/*
+** Delete a range of keys from the database.
+*/
+int tdb_delete_range(TestDb *, void *pKey1, int nKey1, void *pKey2, int nKey2);
+
 /*
 ** Query the database for key (pKey/nKey). If no entry is found, set *ppVal
 ** to 0 and *pnVal to -1 before returning. Otherwise, set *ppVal and *pnVal
 ** to a pointer to and size of the value associated with (pKey/nKey).
 */

Index: lsm-test/lsmtest_tdb3.c
==================================================================
--- lsm-test/lsmtest_tdb3.c
+++ lsm-test/lsmtest_tdb3.c
@@ -452,10 +452,19 @@
 
 static int test_lsm_delete(TestDb *pTestDb, void *pKey, int nKey){
   LsmDb *pDb = (LsmDb *)pTestDb;
   return lsm_delete(pDb->db, pKey, nKey);
 }
+
+static int test_lsm_delete_range(
+  TestDb *pTestDb, 
+  void *pKey1, int nKey1,
+  void *pKey2, int nKey2
+){
+  LsmDb *pDb = (LsmDb *)pTestDb;
+  return lsm_delete_range(pDb->db, pKey1, nKey1, pKey2, nKey2);
+}
 
 static int test_lsm_fetch(
   TestDb *pTestDb, 
   void *pKey, 
   int nKey, 
@@ -728,10 +737,11 @@
 ){
   static const DatabaseMethods LsmMethods = {
     test_lsm_close,
     test_lsm_write,
     test_lsm_delete,
+    test_lsm_delete_range,
     test_lsm_fetch,
     test_lsm_scan,
     test_lsm_begin,
     test_lsm_commit,
     test_lsm_rollback
@@ -1113,56 +1123,19 @@
 
   return rc;
 }
 
 
-static int test_lsm_mt(
-  const char *zFilename,          /* File to open */
-  int nWorker,                    /* Either 1 or 2, for worker threads */
-  int bClear,                     /* True to delete any existing db */
-  TestDb **ppDb                   /* OUT: TestDb database handle */
-){
-  LsmDb *pDb;
-  int rc;
-
-  rc = test_lsm_open(zFilename, bClear, ppDb);
-  pDb = (LsmDb *)*ppDb;
-
-  assert( nWorker==1 || nWorker==2 );
-
-  /* Turn off auto-work and configure a work-hook on the client connection. */
-  if( rc==0 ){
-    int bAutowork = 0;
-    lsm_config(pDb->db, LSM_CONFIG_AUTOWORK, &bAutowork);
-    lsm_config_work_hook(pDb->db, mt_client_work_hook, (void *)pDb);
-  }
-
-  if( rc==0 ){
-    pDb->aWorker = (LsmWorker *)testMalloc(sizeof(LsmWorker) * nWorker);
-    memset(pDb->aWorker, 0, sizeof(LsmWorker) * nWorker);
-    pDb->nWorker = nWorker;
-
-    rc = mt_start_worker(pDb, 0, zFilename, 0, LSM_WORK_FLUSH, 
-        nWorker==1 ? 512 : 0, 1
-    );
-  }
-
-  if( rc==0 && nWorker==2 ){
-    rc = mt_start_worker(pDb, 1, zFilename, 0, 0, 512, 0);
-  }
-
-  return rc;
-}
-
 int test_lsm_mt2(const char *zFilename, int bClear, TestDb **ppDb){
-  return test_lsm_mt(zFilename, 1, bClear, ppDb);
+  const char *zCfg = "threads=2";
+  return testLsmOpen(zCfg, zFilename, bClear, ppDb);
 }
 
 int test_lsm_mt3(const char *zFilename, int bClear, TestDb **ppDb){
-  return test_lsm_mt(zFilename, 2, bClear, ppDb);
+  const char *zCfg = "threads=3";
+  return testLsmOpen(zCfg, zFilename, bClear, ppDb);
 }
-
 
 #else
 static void mt_shutdown(LsmDb *pDb) { 
   unused_parameter(pDb); 
 }

Index: src/lsm.h
==================================================================
--- src/lsm.h
+++ src/lsm.h
@@ -378,12 +378,15 @@
 ** key value does not exist in the database.
 */
 int lsm_delete(lsm_db *, const void *pKey, int nKey);
 
 /*
-** Delete all database entries with keys that are greater than or equal to
-** (pKey1/nKey1) and smaller than or equal to (pKey2/nKey2).
+** Delete all database entries with keys that are greater than (pKey1/nKey1) 
+** and smaller than (pKey2/nKey2). Note that keys (pKey1/nKey1) and
+** (pKey2/nKey2) themselves, if they exist in the database, are not deleted.
+**
+** Return LSM_OK if successful, or an LSM error code otherwise.
 */
 int lsm_delete_range(lsm_db *, 
     const void *pKey1, int nKey1, const void *pKey2, int nKey2
 );
 

Index: src/lsmInt.h
==================================================================
--- src/lsmInt.h
+++ src/lsmInt.h
@@ -145,10 +145,22 @@
 */
 #define LSM_MAX_FREELIST_ENTRIES 100
 
 #define LSM_ATTEMPTS_BEFORE_PROTOCOL 10000
 
+
+/*
+** Each entry stored in the LSM (or in-memory tree structure) has an
+** associated mask of the following flags.
+*/
+#define LSM_START_DELETE 0x01     /* Start of open-ended delete range */
+#define LSM_END_DELETE   0x02     /* End of open-ended delete range */
+#define LSM_POINT_DELETE 0x04     /* Delete this key */
+#define LSM_INSERT       0x08     /* Insert this key and value */
+#define LSM_SEPARATOR    0x10     /* True if entry is separator key only */
+#define LSM_SYSTEMKEY    0x20     /* True if entry is a system key (FREELIST) */
+
 /*
 ** A string that can grow by appending.
 */
 struct LsmString {
   lsm_env *pEnv;              /* Run-time environment */
@@ -376,10 +388,11 @@
   int nInput;                     /* Number of input runs being merged */
   MergeInput *aInput;             /* Array nInput entries in size */
   MergeInput splitkey;            /* Location in file of current splitkey */
   int nSkip;                      /* Number of separators entries to skip */
   int iOutputOff;                 /* Write offset on output page */
+  Pgno iCurrentPtr;               /* Current pointer value */
   int bHierReadonly;              /* True if b-tree heirarchies are read-only */
 };
 
 /* 
 ** The first argument to this macro is a pointer to a Segment structure.
@@ -541,15 +554,17 @@
 int lsmTreeCursorSeek(TreeCursor *pCsr, void *pKey, int nKey, int *pRes);
 int lsmTreeCursorNext(TreeCursor *pCsr);
 int lsmTreeCursorPrev(TreeCursor *pCsr);
 int lsmTreeCursorEnd(TreeCursor *pCsr, int bLast);
 void lsmTreeCursorReset(TreeCursor *pCsr);
-int lsmTreeCursorKey(TreeCursor *pCsr, void **ppKey, int *pnKey);
+int lsmTreeCursorKey(TreeCursor *pCsr, int *pFlags, void **ppKey, int *pnKey);
+int lsmTreeCursorFlags(TreeCursor *pCsr);
 int lsmTreeCursorValue(TreeCursor *pCsr, void **ppVal, int *pnVal);
 int lsmTreeCursorValid(TreeCursor *pCsr);
 int lsmTreeCursorSave(TreeCursor *pCsr);
 
+void lsmFlagsToString(int flags, char *zFlags);
 
 /* 
 ** Functions from file "mem.c".
 */
 int lsmPoolNew(lsm_env *pEnv, Mempool **ppPool);

Index: src/lsm_ckpt.c
==================================================================
--- src/lsm_ckpt.c
+++ src/lsm_ckpt.c
@@ -62,10 +62,11 @@
 **     6. For each segment in the merge:
 **        5a. Page number of next cell to read during merge
 **        5b. Cell number of next cell to read during merge
 **     7. Page containing current split-key.
 **     8. Cell within page containing current split-key.
+**     9. Current pointer value.
 **
 **   The freelist. 
 **
 **     1. Number of free-list entries stored in checkpoint header.
 **     2. For each entry:
@@ -310,10 +311,11 @@
       ckptSetValue(p, iOut++, pMerge->aInput[i].iPg, pRc);
       ckptSetValue(p, iOut++, pMerge->aInput[i].iCell, pRc);
     }
     ckptSetValue(p, iOut++, pMerge->splitkey.iPg, pRc);
     ckptSetValue(p, iOut++, pMerge->splitkey.iCell, pRc);
+    ckptSetValue(p, iOut++, pMerge->iCurrentPtr, pRc);
   }
 
   *piOut = iOut;
 }
 
@@ -499,10 +501,11 @@
     pMerge->aInput[i].iPg = (Pgno)aInt[iIn++];
     pMerge->aInput[i].iCell = (int)aInt[iIn++];
   }
   pMerge->splitkey.iPg = (Pgno)aInt[iIn++];
   pMerge->splitkey.iCell = (int)aInt[iIn++];
+  pMerge->iCurrentPtr = (int)aInt[iIn++];
 
   /* Set *piIn and return LSM_OK. */
   *piIn = iIn;
   return LSM_OK;
 }

Index: src/lsm_file.c
==================================================================
--- src/lsm_file.c
+++ src/lsm_file.c
@@ -727,10 +727,11 @@
   Page *p;
   int iHash;
   int rc = LSM_OK;
 
   assert( iPg>=fsFirstPageOnBlock(pFS, 1) );
+  *ppPg = 0;
 
   if( pFS->bUseMmap ){
     i64 iEnd = (i64)iPg * pFS->nPagesize;
     fsGrowMapping(pFS, iEnd, &rc);
     if( rc!=LSM_OK ) return rc;

Index: src/lsm_main.c
==================================================================
--- src/lsm_main.c
+++ src/lsm_main.c
@@ -477,15 +477,13 @@
 
   va_end(ap);
   return rc;
 }
 
-/* 
-** Write a new value into the database.
-*/
-int lsm_write(
-  lsm_db *pDb,                    /* Database connection */
+static int doWriteOp(
+  lsm_db *pDb,
+  int bDeleteRange,
   const void *pKey, int nKey,     /* Key to write or delete */
   const void *pVal, int nVal      /* Value to write. Or nVal==-1 for a delete */
 ){
   int rc = LSM_OK;                /* Return code */
   int bCommit = 0;                /* True to commit before returning */
@@ -494,11 +492,15 @@
     bCommit = 1;
     rc = lsm_begin(pDb, 1);
   }
 
   if( rc==LSM_OK ){
-    rc = lsmLogWrite(pDb, (void *)pKey, nKey, (void *)pVal, nVal);
+    if( bDeleteRange==0 ){
+      rc = lsmLogWrite(pDb, (void *)pKey, nKey, (void *)pVal, nVal);
+    }else{
+      /* TODO */
+    }
   }
 
   lsmSortedSaveTreeCursors(pDb);
 
   if( rc==LSM_OK ){
@@ -511,11 +513,16 @@
     if( nQuant>pDb->nTreeLimit ){
       nQuant = pDb->nTreeLimit;
     }
 
     nBefore = lsmTreeSize(pDb);
-    rc = lsmTreeInsert(pDb, (void *)pKey, nKey, (void *)pVal, nVal);
+    if( bDeleteRange ){
+      rc = lsmTreeDelete(pDb, (void *)pKey, nKey, (void *)pVal, nVal);
+    }else{
+      rc = lsmTreeInsert(pDb, (void *)pKey, nKey, (void *)pVal, nVal);
+    }
+
     nAfter = lsmTreeSize(pDb);
     nDiff = (nAfter/nQuant) - (nBefore/nQuant);
     if( rc==LSM_OK && pDb->bAutowork && nDiff!=0 ){
       rc = lsmSortedAutoWork(pDb, nDiff * LSM_AUTOWORK_QUANT);
     }
@@ -531,16 +538,42 @@
     }
   }
 
   return rc;
 }
+
+/* 
+** Write a new value into the database.
+*/
+int lsm_write(
+  lsm_db *db,                     /* Database connection */
+  const void *pKey, int nKey,     /* Key to write or delete */
+  const void *pVal, int nVal      /* Value to write. Or nVal==-1 for a delete */
+){
+  return doWriteOp(db, 0, pKey, nKey, pVal, nVal);
+}
 
 /*
 ** Delete a value from the database. 
 */
-int lsm_delete(lsm_db *pDb, const void *pKey, int nKey){
-  return lsm_write(pDb, pKey, nKey, 0, -1);
+int lsm_delete(lsm_db *db, const void *pKey, int nKey){
+  return doWriteOp(db, 0, pKey, nKey, 0, -1);
+}
+
+/*
+** Delete a range of database keys.
+*/
+int lsm_delete_range(
+  lsm_db *db,                     /* Database handle */
+  const void *pKey1, int nKey1,   /* Lower bound of range to delete */
+  const void *pKey2, int nKey2    /* Upper bound of range to delete */
+){
+  int rc = LSM_OK;
+  if( db->xCmp((void *)pKey1, nKey1, (void *)pKey2, nKey2)<0 ){
+    rc = doWriteOp(db, 1, pKey1, nKey1, pKey2, nKey2);
+  }
+  return rc;
 }
 
 /*
 ** Open a new cursor handle. 
 **

Index: src/lsm_shared.c
==================================================================
--- src/lsm_shared.c
+++ src/lsm_shared.c
@@ -633,20 +633,18 @@
 ** been flushed to disk. The significance of this is that once the snapshot
 ** created to hold the updated state of the database is synced to disk, log
 ** file space can be recycled.
 */
 void lsmFinishWork(lsm_db *pDb, int bFlush, int nOvfl, int *pRc){
-  /* If no error has occurred, serialize the worker snapshot and write
-  ** it to shared memory.  */
-
-  assert( pDb->pWorker );
-  assert( pDb->pWorker->nFreelistOvfl==0 || nOvfl==0 );
-  if( *pRc==LSM_OK ){
-    *pRc = lsmCheckpointSaveWorker(pDb, bFlush, nOvfl);
-  }
-
+  assert( *pRc!=0 || pDb->pWorker );
   if( pDb->pWorker ){
+    /* If no error has occurred, serialize the worker snapshot and write
+    ** it to shared memory.  */
+    assert( pDb->pWorker->nFreelistOvfl==0 || nOvfl==0 );
+    if( *pRc==LSM_OK ){
+      *pRc = lsmCheckpointSaveWorker(pDb, bFlush, nOvfl);
+    }
     lsmFreeSnapshot(pDb->pEnv, pDb->pWorker);
     pDb->pWorker = 0;
   }
 
   lsmShmLock(pDb, LSM_LOCK_WORKER, LSM_LOCK_UNLOCK, 0);

Index: src/lsm_sorted.c
==================================================================
--- src/lsm_sorted.c
+++ src/lsm_sorted.c
@@ -40,76 +40,49 @@
 **
 **      aaaaa bbbbb ccc <footer>    cc eeeee fffff g <footer>    gggg....
 **
 ** RECORD FORMAT:
 ** 
-**   Each record in a sorted file is either a WRITE, a DELETE, or a 
-**   SEPARATOR. 
-**
-**   The first byte of the record indicates the type, as follows:
-**
-**     SORTED_SEPARATOR:  0x01
-**     SORTED_WRITE:      0x02
-**     SORTED_DELETE:     0x03
-**
-**   If the sorted file contains pointers, then immediately following the
-**   type byte is a pointer to the smallest key in the next file that is larger
-**   than the key in the current record. The pointer is encoded as a varint.
-**   When added to the 32-bit page number stored in the footer, it is the 
-**   page number of the page that contains the smallest key in the next sorted 
-**   file that is larger than this key. 
+**   The first byte of the record is a flags byte. It is a combination
+**   of the following flags (defined in lsmInt.h):
+**
+**       LSM_START_DELETE
+**       LSM_END_DELETE 
+**       LSM_POINT_DELETE
+**       LSM_INSERT    
+**       LSM_SEPARATOR
+**       LSM_SYSTEMKEY
+**
+**   Immediately following the type byte is a pointer to the smallest key 
+**   in the next file that is larger than the key in the current record. The 
+**   pointer is encoded as a varint. When added to the 32-bit page number 
+**   stored in the footer, it is the page number of the page that contains the
+**   smallest key in the next sorted file that is larger than this key. 
 **
 **   Next is the number of bytes in the key, encoded as a varint.
 **
-**   If the record is a SORTED_WRITE, the number of bytes in the value, as
+**   If the LSM_INSERT flag is set, the number of bytes in the value, as
 **   a varint, is next.
 **
-**   Finally, the blob of data containing the key, and for SORTED_WRITE
+**   Finally, the blob of data containing the key, and for LSM_INSERT
 **   records, the value as well.
-**
-** SEPARATOR ARRAYS:
-**
-**   Each time a sorted run that spans more than one page is constructed, a
-**   separators array is also constructed. A separators array contains normal
-**   pages and b-tree pages. Both types of pages use the same format (as 
-**   above).
-**
-**   The normal pages in the separators array contain a SORTED_SEPARATOR 
-**   record with a copy of the first key on each page of the main array
-**   except the leftmost. If a main array page contains no keys, then there
-**   is no corresponding entry in the separators array.
 */
 
 #ifndef _LSM_INT_H
 # include "lsmInt.h"
 #endif
 #include "sqlite4.h"            /* only for sqlite4_snprintf() */
-/* 
-** Record types for user data.
-*/
-#define SORTED_SEPARATOR 0x01
-#define SORTED_WRITE     0x02
-#define SORTED_DELETE    0x03
-
-#define SORTED_SYSTEM_DATA 0x10
-
-/* 
-** Record types for system data (e.g. free-block list, secondary storage
-** management entries). These are the same as the user types with the
-** most-significant bit set.
-*/
-#define SORTED_SYSTEM_SEPARATOR (SORTED_SYSTEM_DATA | SORTED_SEPARATOR)
-#define SORTED_SYSTEM_WRITE     (SORTED_SYSTEM_DATA | SORTED_WRITE)
-#define SORTED_SYSTEM_DELETE    (SORTED_SYSTEM_DATA | SORTED_DELETE)
 
 /*
 ** Macros to help decode record types.
 */
-#define rtTopic(eType)       ((eType) & 0xF0)
-#define rtIsDelete(eType)    (((eType) & 0x0F)==SORTED_DELETE)
-#define rtIsSeparator(eType) (((eType) & 0x0F)==SORTED_SEPARATOR)
-#define rtIsWrite(eType)     (((eType) & 0x0F)==SORTED_WRITE)
+#define rtTopic(eType)       ((eType) & LSM_SYSTEMKEY)
+#define rtIsDelete(eType)    (((eType) & 0x0F)==LSM_POINT_DELETE)
+
+#define rtIsSeparator(eType) (((eType) & LSM_SEPARATOR)!=0)
+#define rtIsWrite(eType)     (((eType) & LSM_INSERT)!=0)
+#define rtIsSystem(eType)    (((eType) & LSM_SYSTEMKEY)!=0)
 
 /*
 ** The following macros are used to access a page footer.
 */
 #define SEGMENT_NRECORD_OFFSET(pgsz)        ((pgsz) - 2)
@@ -232,10 +205,13 @@
   int *aTree;                     /* Array of comparison results */
 
   /* Used by cursors flushing the in-memory tree only */
   int *pnOvfl;                    /* Number of free-list entries to store */
   void *pSystemVal;               /* Pointer to buffer to free */
+
+  /* Used by worker cursors only */
+  Pgno *pPrevMergePtr;
 };
 
 #define CURSOR_DATA_TREE0     0   /* Current tree cursor */
 #define CURSOR_DATA_TREE1     1   /* The "old" tree, if any */
 #define CURSOR_DATA_SYSTEM    2
@@ -266,18 +242,24 @@
 **   Set if it is Ok to call lsm_csr_prev().
 **
 ** CURSOR_READ_SEPARATORS
 **   Set if this cursor should visit the separator keys in segment 
 **   aPtr[nPtr-1].
+**
+** CURSOR_SEEK_EQ
+**   Cursor has undergone a successful lsm_csr_seek(LSM_SEEK_EQ) operation.
+**   The key and value are stored in MultiCursor.key and MultiCursor.val
+**   respectively.
 */
 #define CURSOR_IGNORE_DELETE    0x00000001
 #define CURSOR_NEW_SYSTEM       0x00000002
 #define CURSOR_AT_FREELIST      0x00000004
 #define CURSOR_IGNORE_SYSTEM    0x00000010
 #define CURSOR_NEXT_OK          0x00000020
 #define CURSOR_PREV_OK          0x00000040
 #define CURSOR_READ_SEPARATORS  0x00000080
+#define CURSOR_SEEK_EQ          0x00000100
 
 typedef struct MergeWorker MergeWorker;
 typedef struct Hierarchy Hierarchy;
 
 struct Hierarchy {
@@ -612,11 +594,11 @@
 
     rc = pageGetBtreeKey(
         pCsr->aPg[iPg].pPage, iCell,
         &dummy, &pCsr->eType, &pCsr->pKey, &pCsr->nKey, &pCsr->blob
     );
-    pCsr->eType |= SORTED_SEPARATOR;
+    pCsr->eType |= LSM_SEPARATOR;
   }
 
   return rc;
 }
 
@@ -920,11 +902,11 @@
         assert( i>=0 );
         rc = pageGetBtreeKey(
             pCsr->aPg[i].pPage, pCsr->aPg[i].iCell-1,
             &dummy, &pCsr->eType, &pCsr->pKey, &pCsr->nKey, &pCsr->blob
         );
-        pCsr->eType |= SORTED_SEPARATOR;
+        pCsr->eType |= LSM_SEPARATOR;
 
       }else{
         rc = btreeCursorLoadKey(pCsr);
       }
     }
@@ -1110,17 +1092,24 @@
   MultiCursor *pCsr, 
   SegmentPtr *pPtr,
   int bReverse
 ){
   int eDir = (bReverse ? -1 : 1);
+  Level *pLvl = pPtr->pLevel;
   do {
     int rc;
     int iCell;                    /* Number of new cell in page */
+    int svFlags = 0;              /* SegmentPtr.eType before advance */
 
     iCell = pPtr->iCell + eDir;
     assert( pPtr->pPg );
     assert( iCell<=pPtr->nCell && iCell>=-1 );
+
+    if( bReverse && pPtr->pSeg!=&pPtr->pLevel->lhs ){
+      svFlags = pPtr->eType;
+      assert( svFlags );
+    }
 
     if( iCell>=pPtr->nCell || iCell<0 ){
       do {
         rc = segmentPtrNextPage(pPtr, eDir); 
       }while( rc==LSM_OK 
@@ -1130,10 +1119,26 @@
       if( rc!=LSM_OK ) return rc;
       iCell = bReverse ? (pPtr->nCell-1) : 0;
     }
     rc = segmentPtrLoadCell(pPtr, iCell);
     if( rc!=LSM_OK ) return rc;
+
+    if( svFlags && pPtr->pPg ){
+      int res = sortedKeyCompare(pCsr->pDb->xCmp,
+          rtTopic(pPtr->eType), pPtr->pKey, pPtr->nKey,
+          pLvl->iSplitTopic, pLvl->pSplitKey, pLvl->nSplitKey
+      );
+      if( res<0 ) segmentPtrReset(pPtr);
+    }
+    if( pPtr->pPg==0 && (svFlags & LSM_END_DELETE) ){
+      rc = lsmFsDbPageGet(pCsr->pDb->pFS, pPtr->pSeg->iFirst, &pPtr->pPg);
+      if( rc!=LSM_OK ) return rc;
+      pPtr->eType = LSM_START_DELETE | (pLvl->iSplitTopic ? LSM_SYSTEMKEY : 0);
+      pPtr->pKey = pLvl->pSplitKey;
+      pPtr->nKey = pLvl->nSplitKey;
+    }
+
   }while( pCsr 
        && pPtr->pPg 
        && segmentPtrIgnoreSeparators(pCsr, pPtr)
        && rtIsSeparator(pPtr->eType)
   );
@@ -1163,10 +1168,11 @@
 **
 ** Return LSM_OK if successful or an lsm error code if something goes
 ** wrong (IO error, OOM etc.).
 */
 static int segmentPtrEnd(MultiCursor *pCsr, SegmentPtr *pPtr, int bLast){
+  Level *pLvl = pPtr->pLevel;
   int rc = LSM_OK;
   FileSystem *pFS = pCsr->pDb->pFS;
   int bIgnore;
 
   segmentPtrEndPage(pFS, pPtr, bLast, &rc);
@@ -1173,20 +1179,33 @@
   while( rc==LSM_OK && pPtr->pPg 
       && (pPtr->nCell==0 || (pPtr->flags & SEGMENT_BTREE_FLAG))
   ){
     rc = segmentPtrNextPage(pPtr, (bLast ? -1 : 1));
   }
-  
+
   if( rc==LSM_OK && pPtr->pPg ){
     rc = segmentPtrLoadCell(pPtr, bLast ? (pPtr->nCell-1) : 0);
   }
-
+  
   bIgnore = segmentPtrIgnoreSeparators(pCsr, pPtr);
   if( rc==LSM_OK && pPtr->pPg && bIgnore && rtIsSeparator(pPtr->eType) ){
     rc = segmentPtrAdvance(pCsr, pPtr, bLast);
   }
 
+
+  if( bLast && rc==LSM_OK && pPtr->pPg
+   && pPtr->pSeg==&pLvl->lhs 
+   && pLvl->nRight && (pPtr->eType & LSM_START_DELETE)
+  ){
+    pPtr->iCell++;
+    pPtr->eType = LSM_END_DELETE | (pLvl->iSplitTopic);
+    pPtr->pKey = pLvl->pSplitKey;
+    pPtr->nKey = pLvl->nSplitKey;
+    pPtr->pVal = 0;
+    pPtr->nVal = 0;
+  }
+
   return rc;
 }
 
 static void segmentPtrKey(SegmentPtr *pPtr, void **ppKey, int *pnKey){
   assert( pPtr->pPg );
@@ -1293,25 +1312,17 @@
 
   return 1;
 }
 #endif
 
-int segmentPtrSeek(
+static int segmentPtrSearchOversized(
   MultiCursor *pCsr,              /* Cursor context */
   SegmentPtr *pPtr,               /* Pointer to seek */
-  void *pKey, int nKey,           /* Key to seek to */
-  int eSeek,                      /* Search bias - see above */
-  int *piPtr                      /* OUT: FC pointer */
+  void *pKey, int nKey            /* Key to seek to */
 ){
   int (*xCmp)(void *, int, void *, int) = pCsr->pDb->xCmp;
-  int res;                        /* Result of comparison operation */
   int rc = LSM_OK;
-  int iMin;
-  int iMax;
-  int iPtrOut = 0;
-
-  const int iTopic = 0;
 
   /* If the OVERSIZED flag is set, then there is no pointer in the
   ** upper level to the next page in the segment that contains at least
   ** one key. So compare the largest key on the current page with the
   ** key being sought (pKey/nKey). If (pKey/nKey) is larger, advance
@@ -1331,11 +1342,11 @@
 
     /* If the loaded key is >= than (pKey/nKey), break out of the loop.
     ** If (pKey/nKey) is present in this array, it must be on the current 
     ** page.  */
     res = sortedKeyCompare(
-        xCmp, iLastTopic, pLastKey, nLastKey, iTopic, pKey, nKey
+        xCmp, iLastTopic, pLastKey, nLastKey, 0, pKey, nKey
     );
     if( res>=0 ) break;
 
     /* Advance to the next page that contains at least one key. */
     pNext = pPtr->pPg;
@@ -1362,17 +1373,187 @@
 
     /* This should probably be an LSM_CORRUPT error. */
     assert( rc!=LSM_OK || (pPtr->flags & PGFTR_SKIP_THIS_FLAG) );
   }
 
+  return rc;
+}
+
+static int ptrFwdPointer(
+  Page *pPage,
+  int iCell,
+  Segment *pSeg,
+  Pgno *piPtr,
+  int *pbFound
+){
+  Page *pPg = pPage;
+  int iFirst = iCell;
+  int rc = LSM_OK;
+
+  do {
+    Page *pNext = 0;
+    u8 *aData;
+    int nData;
+
+    aData = lsmFsPageData(pPg, &nData);
+    if( (pageGetFlags(aData, nData) & SEGMENT_BTREE_FLAG)==0 ){
+      int i;
+      int nCell = pageGetNRec(aData, nData);
+      for(i=iFirst; i<nCell; i++){
+        u8 eType = *pageGetCell(aData, nData, i);
+        if( (eType & LSM_START_DELETE)==0 ){
+          *pbFound = 1;
+          *piPtr = pageGetRecordPtr(aData, nData, i) + pageGetPtr(aData, nData);
+          lsmFsPageRelease(pPg);
+          return LSM_OK;
+        }
+      }
+    }
+
+    rc = lsmFsDbPageNext(pSeg, pPg, 1, &pNext);
+    lsmFsPageRelease(pPg);
+    pPg = pNext;
+    iFirst = 0;
+  }while( pPg && rc==LSM_OK );
+  lsmFsPageRelease(pPg);
+
+  *pbFound = 0;
+  return rc;
+}
+
+static int sortedRhsFirst(MultiCursor *pCsr, Level *pLvl, SegmentPtr *pPtr){
+  int rc;
+  rc = segmentPtrEnd(pCsr, pPtr, 0);
+  while( pPtr->pPg && rc==LSM_OK ){
+    int res = sortedKeyCompare(pCsr->pDb->xCmp,
+        pLvl->iSplitTopic, pLvl->pSplitKey, pLvl->nSplitKey,
+        rtTopic(pPtr->eType), pPtr->pKey, pPtr->nKey
+    );
+    if( res<=0 ) break;
+    rc = segmentPtrAdvance(pCsr, pPtr, 0);
+  }
+  return rc;
+}
+
+
+/*
+** This function is called as part of a SEEK_GE op on a multi-cursor if the 
+** FC pointer read from segment *pPtr comes from an entry with the 
+** LSM_START_DELETE flag set. In this case the pointer value cannot be 
+** trusted. Instead, the pointer that should be followed is that associated
+** with the next entry in *pPtr that does not have LSM_START_DELETE set.
+**
+** Why the pointers can't be trusted:
+**
+**
+**
+** TODO: This is a stop-gap solution:
+** 
+**   At the moment, this function is called from within segmentPtrSeek(), 
+**   as part of the initial lsmMCursorSeek() call. However, consider a 
+**   database where the following has occurred:
+**
+**      1. A range delete removes keys 1..9999 using a range delete.
+**      2. Keys 1 through 9999 are reinserted.
+**      3. The levels containing the ops in 1. and 2. above are merged. Call
+**         this level N. Level N contains FC pointers to level N+1.
+**
+**   Then, if the user attempts to query for (key>=2 LIMIT 10), the 
+**   lsmMCursorSeek() call will iterate through 9998 entries searching for a 
+**   pointer down to the level N+1 that is never actually used. It would be
+**   much better if the multi-cursor could do this lazily - only seek to the
+**   level (N+1) page after the user has moved the cursor on level N passed
+**   the big range-delete.
+*/
+static int segmentPtrFwdPointer(
+  MultiCursor *pCsr,              /* Multi-cursor pPtr belongs to */
+  SegmentPtr *pPtr,               /* Segment-pointer to extract FC ptr from */
+  Pgno *piPtr                     /* OUT: FC pointer value */
+){
+  Level *pLvl = pPtr->pLevel;
+  Level *pNext = pLvl->pNext;
+  Page *pPg = pPtr->pPg;
+  int rc;
+  int bFound;
+  Pgno iOut = 0;
+
+  if( pPtr->pSeg==&pLvl->lhs || pPtr->pSeg==&pLvl->aRhs[pLvl->nRight-1] ){
+    if( pNext==0 
+        || (pNext->nRight==0 && pNext->lhs.iRoot)
+        || (pNext->nRight!=0 && pNext->aRhs[0].iRoot)
+      ){
+      /* Do nothing. The pointer will not be used anyway. */
+      return LSM_OK;
+    }
+  }else{
+    if( pPtr[1].pSeg->iRoot ){
+      return LSM_OK;
+    }
+  }
+
+  /* Search for a pointer within the current segment. */
+  lsmFsPageRef(pPg);
+  rc = ptrFwdPointer(pPg, pPtr->iCell, pPtr->pSeg, &iOut, &bFound);
+
+  if( rc==LSM_OK && bFound==0 ){
+    /* This case happens when pPtr points to the left-hand-side of a segment
+    ** currently undergoing an incremental merge. In this case, jump to the
+    ** oldest segment in the right-hand-side of the same level and continue
+    ** searching. But - do not consider any keys smaller than the levels
+    ** split-key. */
+    SegmentPtr ptr;
+
+    if( pPtr->pLevel->nRight==0 || pPtr->pSeg!=&pPtr->pLevel->lhs ){
+      return LSM_CORRUPT_BKPT;
+    }
+
+    memset(&ptr, 0, sizeof(SegmentPtr));
+    ptr.pLevel = pPtr->pLevel;
+    ptr.pSeg = &ptr.pLevel->aRhs[ptr.pLevel->nRight-1];
+    rc = sortedRhsFirst(pCsr, ptr.pLevel, &ptr);
+    if( rc==LSM_OK ){
+      rc = ptrFwdPointer(ptr.pPg, ptr.iCell, ptr.pSeg, &iOut, &bFound);
+      ptr.pPg = 0;
+    }
+    segmentPtrReset(&ptr);
+  }
+
+  *piPtr = iOut;
+  return rc;
+}
+
+static int segmentPtrSeek(
+  MultiCursor *pCsr,              /* Cursor context */
+  SegmentPtr *pPtr,               /* Pointer to seek */
+  void *pKey, int nKey,           /* Key to seek to */
+  int eSeek,                      /* Search bias - see above */
+  int *piPtr,                     /* OUT: FC pointer */
+  int *pbStop
+){
+  int (*xCmp)(void *, int, void *, int) = pCsr->pDb->xCmp;
+  int res;                        /* Result of comparison operation */
+  int rc = LSM_OK;
+  int iMin;
+  int iMax;
+  int iPtrOut = 0;
+  const int iTopic = 0;
+
+  /* If the current page contains an oversized entry, then there are no
+  ** pointers to one or more of the subsequent pages in the sorted run.
+  ** The following call ensures that the segment-ptr points to the correct 
+  ** page in this case.  */
+  rc = segmentPtrSearchOversized(pCsr, pPtr, pKey, nKey);
   iPtrOut = pPtr->iPtr;
 
   /* Assert that this page is the right page of this segment for the key
   ** that we are searching for. Do this by loading page (iPg-1) and testing
   ** that pKey/nKey is greater than all keys on that page, and then by 
   ** loading (iPg+1) and testing that pKey/nKey is smaller than all
-  ** the keys it houses.  */
+  ** the keys it houses.  
+  **
+  ** TODO: With range-deletes in the tree, the test described above may fail.
+  */
 #if 0
   assert( assertKeyLocation(pCsr, pPtr, pKey, nKey) );
 #endif
 
   assert( pPtr->nCell>0 
@@ -1415,32 +1596,60 @@
     if( rc==LSM_OK ){
       assert( res==0 || (iMin==iMax && iMin>=0 && iMin<pPtr->nCell) );
       if( res ){
         rc = segmentPtrLoadCell(pPtr, iMin);
       }
+      assert( rc!=LSM_OK || res>0 || iPtrOut==(pPtr->iPtr + pPtr->iPgPtr) );
 
       if( rc==LSM_OK ){
         switch( eSeek ){
-          case LSM_SEEK_EQ:
-            if( res!=0 || rtIsSeparator(pPtr->eType) ) segmentPtrReset(pPtr);
+          case LSM_SEEK_EQ: {
+            int eType = pPtr->eType;
+            if( (res<0 && (eType & LSM_START_DELETE))
+             || (res>0 && (eType & LSM_END_DELETE))
+             || (res==0 && (eType & LSM_POINT_DELETE))
+            ){
+              *pbStop = 1;
+            }else if( res==0 && (eType & LSM_INSERT) ){
+              lsm_env *pEnv = pCsr->pDb->pEnv;
+              *pbStop = 1;
+              pCsr->eType = pPtr->eType;
+              rc = sortedBlobSet(pEnv, &pCsr->key, pPtr->pKey, pPtr->nKey);
+              if( rc==LSM_OK ){
+                rc = sortedBlobSet(pEnv, &pCsr->val, pPtr->pVal, pPtr->nVal);
+              }
+              pCsr->flags |= CURSOR_SEEK_EQ;
+            }
+            segmentPtrReset(pPtr);
             break;
+          }
           case LSM_SEEK_LE:
             if( res>0 ) rc = segmentPtrAdvance(pCsr, pPtr, 1);
             break;
-          case LSM_SEEK_GE:
-            if( res<0 ) rc = segmentPtrAdvance(pCsr, pPtr, 0);
+          case LSM_SEEK_GE: {
+            /* Figure out if we need to 'skip' the pointer forward or not */
+            if( (res<=0 && (pPtr->eType & LSM_START_DELETE)) 
+             || (res>0  && (pPtr->eType & LSM_END_DELETE)) 
+            ){
+              rc = segmentPtrFwdPointer(pCsr, pPtr, &iPtrOut);
+            }
+            if( res<0 && rc==LSM_OK ){
+              rc = segmentPtrAdvance(pCsr, pPtr, 0);
+            }
             break;
+          }
         }
       }
     }
 
     /* If the cursor seek has found a separator key, and this cursor is
     ** supposed to ignore separators keys, advance to the next entry.  */
-    if( rc==LSM_OK && pPtr->pPg 
+    if( rc==LSM_OK && pPtr->pPg
      && segmentPtrIgnoreSeparators(pCsr, pPtr) 
      && rtIsSeparator(pPtr->eType)
     ){
+      assert( eSeek!=LSM_SEEK_EQ );
       rc = segmentPtrAdvance(pCsr, pPtr, eSeek==LSM_SEEK_LE);
     }
   }
 
   assert( rc!=LSM_OK || assertSeekResult(pCsr,pPtr,iTopic,pKey,nKey,eSeek) );
@@ -1533,11 +1742,12 @@
   MultiCursor *pCsr, 
   SegmentPtr *pPtr,
   void *pKey, int nKey,
   int iPg,                        /* Page to search */
   int eSeek,                      /* Search bias - see above */
-  int *piPtr                      /* OUT: FC pointer */
+  int *piPtr,                     /* OUT: FC pointer */
+  int *pbStop                     /* OUT: Stop search flag */
 ){
   int iPtr = iPg;
   int rc = LSM_OK;
 
   if( pPtr->pSeg->iRoot ){
@@ -1553,30 +1763,43 @@
       rc = segmentPtrLoadPage(pCsr->pDb->pFS, pPtr, iPtr);
     }
   }
 
   if( rc==LSM_OK ){
-    rc = segmentPtrSeek(pCsr, pPtr, pKey, nKey, eSeek, piPtr);
+    rc = segmentPtrSeek(pCsr, pPtr, pKey, nKey, eSeek, piPtr, pbStop);
   }
   return rc;
 }
 
 /*
 ** Seek each segment pointer in the array of (pLvl->nRight+1) at aPtr[].
+**
+** pbStop:
+**   This parameter is only significant if parameter eSeek is set to
+**   LSM_SEEK_EQ. In this case, it is set to true before returning if
+**   the seek operation is finished. This can happen in two ways:
+**   
+**     a) A key matching (pKey/nKey) is found, or
+**     b) A point-delete or range-delete deleting the key is found.
+**
+**   In case (a), the multi-cursor CURSOR_SEEK_EQ flag is set and the pCsr->key
+**   and pCsr->val blobs populated before returning.
 */
 static int seekInLevel(
   MultiCursor *pCsr,              /* Sorted cursor object to seek */
-  Level *pLvl,                    /* Level to seek within */
-  SegmentPtr *aPtr,               /* Pointer to array of (nRight+1) SPs */
+  SegmentPtr *aPtr,               /* Pointer to array of (nRhs+1) SPs */
   int eSeek,                      /* Search bias - see above */
   void *pKey, int nKey,           /* Key to search for */
-  Pgno *piPgno                    /* IN/OUT: fraction cascade pointer (or 0) */
+  Pgno *piPgno,                   /* IN/OUT: fraction cascade pointer (or 0) */
+  int *pbStop                     /* OUT: See above */
 ){
+  Level *pLvl = aPtr[0].pLevel;   /* Level to seek within */
   int rc = LSM_OK;                /* Return code */
   int iOut = 0;                   /* Pointer to return to caller */
   int res = -1;                   /* Result of xCmp(pKey, split) */
   int nRhs = pLvl->nRight;        /* Number of right-hand-side segments */
+  int bStop = 0;
 
   /* If this is a composite level (one currently undergoing an incremental
   ** merge), figure out if the search key is larger or smaller than the
   ** levels split-key.  */
   if( nRhs ){
@@ -1590,31 +1813,33 @@
   ** left-hand-side of the level in this case.  */
   if( res<0 ){
     int iPtr = 0;
     if( nRhs==0 ) iPtr = *piPgno;
 
-    rc = seekInSegment(pCsr, &aPtr[0], pKey, nKey, iPtr, eSeek, &iOut);
+    rc = seekInSegment(pCsr, &aPtr[0], pKey, nKey, iPtr, eSeek, &iOut, &bStop);
     if( rc==LSM_OK && nRhs>0 && eSeek==LSM_SEEK_GE && aPtr[0].pPg==0 ){
       res = 0;
     }
   }
   
   if( res>=0 ){
     int iPtr = *piPgno;
     int i;
-    for(i=1; rc==LSM_OK && i<=nRhs; i++){
+    for(i=1; rc==LSM_OK && i<=nRhs && bStop==0; i++){
       iOut = 0;
-      rc = seekInSegment(pCsr, &aPtr[i], pKey, nKey, iPtr, eSeek, &iOut);
+      rc = seekInSegment(pCsr, &aPtr[i], pKey, nKey, iPtr, eSeek, &iOut,&bStop);
       iPtr = iOut;
     }
 
     if( rc==LSM_OK && eSeek==LSM_SEEK_LE ){
       rc = segmentPtrEnd(pCsr, &aPtr[0], 1);
     }
   }
 
+  assert( eSeek==LSM_SEEK_EQ || bStop==0 );
   *piPgno = iOut;
+  *pbStop = bStop;
   return rc;
 }
 
 static void multiCursorGetKey(
   MultiCursor *pCsr, 
@@ -1633,22 +1858,21 @@
       TreeCursor *pTreeCsr = pCsr->apTreeCsr[iKey-CURSOR_DATA_TREE0];
       if( lsmTreeCursorValid(pTreeCsr) ){
         int nVal;
         void *pVal;
 
-        lsmTreeCursorKey(pTreeCsr, &pKey, &nKey);
+        lsmTreeCursorKey(pTreeCsr, &eType, &pKey, &nKey);
         lsmTreeCursorValue(pTreeCsr, &pVal, &nVal);
-        eType = (nVal<0) ? SORTED_DELETE : SORTED_WRITE;
       }
       break;
     }
 
     case CURSOR_DATA_SYSTEM:
       if( pCsr->flags & CURSOR_AT_FREELIST ){
         pKey = (void *)"FREELIST";
         nKey = 8;
-        eType = SORTED_SYSTEM_WRITE;
+        eType = LSM_SYSTEMKEY | LSM_INSERT;
       }
       break;
 
     default: {
       int iPtr = iKey - CURSOR_DATA_SEGMENT;
@@ -1674,19 +1898,48 @@
   if( peType ) *peType = eType;
   if( pnKey ) *pnKey = nKey;
   if( ppKey ) *ppKey = pKey;
 }
 
+static int sortedDbKeyCompare(
+  int (*xCmp)(void *, int, void *, int),
+  int iLhsFlags, void *pLhsKey, int nLhsKey,
+  int iRhsFlags, void *pRhsKey, int nRhsKey
+){
+  int res;
+
+  /* Compare the keys, including the system flag. */
+  res = sortedKeyCompare(xCmp, 
+    rtTopic(iLhsFlags), pLhsKey, nLhsKey,
+    rtTopic(iRhsFlags), pRhsKey, nRhsKey
+  );
+
+  /* If a key has the LSM_START_DELETE flag set, but not the LSM_INSERT or
+  ** LSM_POINT_DELETE flags, it is considered a delta larger. This prevents
+  ** the beginning of an open-ended set from masking a database entry or
+  ** delete at a lower level.  */
+  if( res==0 ){
+    const int insdel = LSM_POINT_DELETE|LSM_INSERT;
+    int iDel1 = 0;
+    int iDel2 = 0;
+    if( LSM_START_DELETE==(iLhsFlags & (LSM_START_DELETE|insdel)) ) iDel1 = +1;
+    if( LSM_END_DELETE  ==(iLhsFlags & (LSM_END_DELETE  |insdel)) ) iDel1 = -1;
+    if( LSM_START_DELETE==(iRhsFlags & (LSM_START_DELETE|insdel)) ) iDel2 = +1;
+    if( LSM_END_DELETE  ==(iRhsFlags & (LSM_END_DELETE  |insdel)) ) iDel2 = -1;
+    res = (iDel1 - iDel2);
+  }
+
+  return res;
+}
 
 static void multiCursorDoCompare(MultiCursor *pCsr, int iOut, int bReverse){
   int i1;
   int i2;
   int iRes;
   void *pKey1; int nKey1; int eType1;
   void *pKey2; int nKey2; int eType2;
-
-  int mul = (bReverse ? -1 : 1);
+  const int mul = (bReverse ? -1 : 1);
 
   assert( pCsr->aTree && iOut<pCsr->nTree );
   if( iOut>=(pCsr->nTree/2) ){
     i1 = (iOut - pCsr->nTree/2) * 2;
     i2 = i1 + 1;
@@ -1703,16 +1956,16 @@
   }else if( pKey2==0 ){
     iRes = i1;
   }else{
     int res;
 
-    res = (rtTopic(eType1) - rtTopic(eType2));
-    if( res==0 ){
-      res = pCsr->pDb->xCmp(pKey1, nKey1, pKey2, nKey2);
-    }
+    /* Compare the keys */
+    res = sortedDbKeyCompare(pCsr->pDb->xCmp, 
+        eType1, pKey1, nKey1, eType2, pKey2, nKey2
+    );
+
     res = res * mul;
-
     if( res==0 ){
       iRes = (rtIsSeparator(eType1) ? i2 : i1);
     }else if( res<0 ){
       iRes = i1;
     }else{
@@ -1721,39 +1974,21 @@
   }
 
   pCsr->aTree[iOut] = iRes;
 }
 
-static int sortedRhsFirst(MultiCursor *pCsr, Level *pLvl, SegmentPtr *pPtr){
-  int rc;
-  rc = segmentPtrEnd(pCsr, pPtr, 0);
-  while( pPtr->pPg && rc==LSM_OK ){
-    int res = sortedKeyCompare(pCsr->pDb->xCmp,
-        pLvl->iSplitTopic, pLvl->pSplitKey, pLvl->nSplitKey,
-        rtTopic(pPtr->eType), pPtr->pKey, pPtr->nKey
-    );
-    if( res<=0 ) break;
-    rc = segmentPtrAdvance(pCsr, pPtr, 0);
-  }
-  return rc;
-}
-
 /*
 ** This function advances segment pointer iPtr belonging to multi-cursor
 ** pCsr forward (bReverse==0) or backward (bReverse!=0).
 **
 ** If the segment pointer points to a segment that is part of a composite
-** level, then the following special cases are handled.
+** level, then the following special case is handled.
 **
 **   * If iPtr is the lhs of a composite level, and the cursor is being
 **     advanced forwards, and segment iPtr is at EOF, move all pointers
 **     that correspond to rhs segments of the same level to the first
 **     key in their respective data.
-**
-**   * If iPtr is on the rhs of a composite level, and the cursor is being
-**     reversed, and the new key is smaller than the split-key, set the
-**     segment pointer to point to EOF.
 */
 static int segmentCursorAdvance(
   MultiCursor *pCsr, 
   int iPtr,
   int bReverse
@@ -1770,30 +2005,18 @@
   if( bComposite && pPtr->pSeg==&pLvl->lhs       /* lhs of composite level */
    && bReverse==0                                /* csr advanced forwards */
    && pPtr->pPg==0                               /* segment at EOF */
   ){
     int i;
-
     for(i=0; rc==LSM_OK && i<pLvl->nRight; i++){
       rc = sortedRhsFirst(pCsr, pLvl, &pCsr->aPtr[iPtr+1+i]);
     }
-
     for(i=pCsr->nTree-1; i>0; i--){
       multiCursorDoCompare(pCsr, i, 0);
     }
   }
 
-  else if( pPtr->pPg && bComposite && bReverse && pPtr->pSeg!=&pLvl->lhs ){
-    int res = sortedKeyCompare(pCsr->pDb->xCmp,
-        rtTopic(pPtr->eType), pPtr->pKey, pPtr->nKey,
-        pLvl->iSplitTopic, pLvl->pSplitKey, pLvl->nSplitKey
-    );
-    if( res<0 ){
-      segmentPtrReset(pPtr);
-    }
-  }
-
   return rc;
 }
 
 static void mcursorFreeComponents(MultiCursor *pCsr){
   int i;
@@ -2079,11 +2302,11 @@
   }
   
   if( rc==LSM_OK ){
     rc = lsmMCursorLast(pCsr);
     if( rc==LSM_OK 
-     && pCsr->eType==SORTED_SYSTEM_WRITE 
+     && rtIsWrite(pCsr->eType) && rtIsSystem(pCsr->eType)
      && pCsr->key.nData==8 
      && 0==memcmp(pCsr->key.pData, "FREELIST", 8)
     ){
       void *pVal; int nVal;         /* Value read from database */
       rc = lsmMCursorValue(pCsr, &pVal, &nVal);
@@ -2126,16 +2349,55 @@
     int nKey;
     multiCursorGetKey(pCsr, pCsr->aTree[1], &pCsr->eType, &pKey, &nKey);
     *pRc = sortedBlobSet(pCsr->pDb->pEnv, &pCsr->key, pKey, nKey);
   }
 }
+
+static int mcursorLocationOk(MultiCursor *pCsr, int bDeleteOk){
+  int eType = pCsr->eType;
+  int iKey;
+  int i;
+  int rdmask = 0;
+  
+  assert( pCsr->flags & (CURSOR_NEXT_OK|CURSOR_PREV_OK) );
+  if( pCsr->flags & CURSOR_NEXT_OK ){
+    rdmask = LSM_END_DELETE;
+  }else{
+    rdmask = LSM_START_DELETE;
+  }
+
+  if( (pCsr->flags & CURSOR_IGNORE_DELETE) && bDeleteOk==0 ){
+    if( (eType & LSM_INSERT)==0 ) return 0;
+  }
+  if( (pCsr->flags & CURSOR_IGNORE_SYSTEM) && rtTopic(eType)!=0 ){
+    return 0;
+  }
+
+  /* Check if this key has already been deleted by a range-delete */
+  iKey = pCsr->aTree[1];
+  if( (iKey>0 && (rdmask & lsmTreeCursorFlags(pCsr->apTreeCsr[0]))) 
+   || (iKey>1 && (rdmask & lsmTreeCursorFlags(pCsr->apTreeCsr[1]))) 
+  ){
+    return 0;
+  }
+  for(i=CURSOR_DATA_SEGMENT; i<iKey; i++){
+    int iPtr = i-CURSOR_DATA_SEGMENT;
+    if( pCsr->aPtr[iPtr].pPg && (pCsr->aPtr[iPtr].eType & rdmask) ){
+      return 0;
+    }
+  }
+
+  return 1;
+}
 
 static int multiCursorEnd(MultiCursor *pCsr, int bLast){
   int rc = LSM_OK;
   int i;
 
   pCsr->flags &= ~(CURSOR_NEXT_OK | CURSOR_PREV_OK);
+  pCsr->flags |= (bLast ? CURSOR_PREV_OK : CURSOR_NEXT_OK);
+
   if( pCsr->apTreeCsr[0] ){
     rc = lsmTreeCursorEnd(pCsr->apTreeCsr[0], bLast);
   }
   if( rc==LSM_OK && pCsr->apTreeCsr[1] ){
     rc = lsmTreeCursorEnd(pCsr->apTreeCsr[1], bLast);
@@ -2175,18 +2437,14 @@
   }
   if( rc==LSM_OK ){
     for(i=pCsr->nTree-1; i>0; i--){
       multiCursorDoCompare(pCsr, i, bLast);
     }
-    pCsr->flags |= (bLast ? CURSOR_PREV_OK : CURSOR_NEXT_OK);
   }
 
   multiCursorCacheKey(pCsr, &rc);
-  if( rc==LSM_OK && (
-        ((pCsr->flags & CURSOR_IGNORE_DELETE) && rtIsDelete(pCsr->eType))
-     || ((pCsr->flags & CURSOR_IGNORE_SYSTEM) && rtTopic(pCsr->eType))
-  )){
+  if( rc==LSM_OK && mcursorLocationOk(pCsr, 0)==0 ){
     if( bLast ){
       rc = lsmMCursorPrev(pCsr);
     }else{
       rc = lsmMCursorNext(pCsr);
     }
@@ -2257,24 +2515,42 @@
     segmentPtrReset(&pCsr->aPtr[i]);
   }
   pCsr->key.nData = 0;
 }
 
-static void treeCursorSeek(
+static int treeCursorSeek(
+  MultiCursor *pCsr,
   TreeCursor *pTreeCsr, 
   void *pKey, int nKey, 
-  int eSeek
+  int eSeek,
+  int *pbStop
 ){
+  int rc = LSM_OK;
   if( pTreeCsr ){
     int res = 0;
     lsmTreeCursorSeek(pTreeCsr, pKey, nKey, &res);
     switch( eSeek ){
-      case LSM_SEEK_EQ:
-        if( res!=0 ){
-          lsmTreeCursorReset(pTreeCsr);
+      case LSM_SEEK_EQ: {
+        int eType = lsmTreeCursorFlags(pTreeCsr);
+        if( (res<0 && (eType & LSM_START_DELETE))
+         || (res>0 && (eType & LSM_END_DELETE))
+         || (res==0 && (eType & LSM_POINT_DELETE))
+        ){
+          *pbStop = 1;
+        }else if( res==0 && (eType & LSM_INSERT) ){
+          lsm_env *pEnv = pCsr->pDb->pEnv;
+          void *p; int n;         /* Key/value from tree-cursor */
+          *pbStop = 1;
+          pCsr->flags |= CURSOR_SEEK_EQ;
+          rc = lsmTreeCursorKey(pTreeCsr, &pCsr->eType, &p, &n);
+          if( rc==LSM_OK ) rc = sortedBlobSet(pEnv, &pCsr->key, p, n);
+          if( rc==LSM_OK ) rc = lsmTreeCursorValue(pTreeCsr, &p, &n);
+          if( rc==LSM_OK ) rc = sortedBlobSet(pEnv, &pCsr->val, p, n);
         }
+        lsmTreeCursorReset(pTreeCsr);
         break;
+      }
       case LSM_SEEK_GE:
         if( res<0 && lsmTreeCursorValid(pTreeCsr) ){
           lsmTreeCursorNext(pTreeCsr);
         }
         break;
@@ -2284,87 +2560,82 @@
           lsmTreeCursorPrev(pTreeCsr);
         }
         break;
     }
   }
+  return rc;
 }
 
 
-static int mcursorLocationOk(MultiCursor *pCsr, int bDeleteOk){
-  int eType = pCsr->eType;
-
-  if( ((pCsr->flags & CURSOR_IGNORE_DELETE) && rtIsDelete(eType) && !bDeleteOk)
-   || ((pCsr->flags & CURSOR_IGNORE_SYSTEM) && rtTopic(pCsr->eType)!=0)
-  ){
-    return 0;
-  }
-
-  return 1;
-}
-
 /*
 ** Seek the cursor.
 */
 int lsmMCursorSeek(MultiCursor *pCsr, void *pKey, int nKey, int eSeek){
   int eESeek = eSeek;             /* Effective eSeek parameter */
-  int rc = LSM_OK;
-  int iPtr = 0;
-  Pgno iPgno = 0; 
-  Level *pLvl;
+  int bStop = 0;                  /* Set to true to halt search operation */
+  int rc = LSM_OK;                /* Return code */
+  int iPtr = 0;                   /* Used to iterate through pCsr->aPtr[] */
+  Pgno iPgno = 0;                 /* FC pointer value */
 
   if( eESeek==LSM_SEEK_LEFAST ) eESeek = LSM_SEEK_LE;
+
   assert( eESeek==LSM_SEEK_EQ || eESeek==LSM_SEEK_LE || eESeek==LSM_SEEK_GE );
-
   assert( (pCsr->flags & CURSOR_NEW_SYSTEM)==0 );
   assert( (pCsr->flags & CURSOR_AT_FREELIST)==0 );
   assert( pCsr->nPtr==0 || pCsr->aPtr[0].pLevel );
 
-  pCsr->flags &= ~(CURSOR_NEXT_OK | CURSOR_PREV_OK);
-  treeCursorSeek(pCsr->apTreeCsr[0], pKey, nKey, eESeek);
-  treeCursorSeek(pCsr->apTreeCsr[1], pKey, nKey, eESeek);
+  pCsr->flags &= ~(CURSOR_NEXT_OK | CURSOR_PREV_OK | CURSOR_SEEK_EQ);
+  rc = treeCursorSeek(pCsr, pCsr->apTreeCsr[0], pKey, nKey, eESeek, &bStop);
+  if( rc==LSM_OK && bStop==0 ){
+    rc = treeCursorSeek(pCsr, pCsr->apTreeCsr[1], pKey, nKey, eESeek, &bStop);
+  }
 
   /* Seek all segment pointers. */
-  for(pLvl=pCsr->pDb->pClient->pLevel; rc==LSM_OK && pLvl; pLvl=pLvl->pNext){
+  for(iPtr=0; iPtr<pCsr->nPtr && rc==LSM_OK && bStop==0; iPtr++){
     SegmentPtr *pPtr = &pCsr->aPtr[iPtr];
-    iPtr += (1+pLvl->nRight);
-    assert( pPtr->pSeg==&pLvl->lhs );
-    rc = seekInLevel(pCsr, pLvl, pPtr, eESeek, pKey, nKey, &iPgno);
-  }
-
-  if( rc==LSM_OK ){
-    rc = multiCursorAllocTree(pCsr);
-  }
-  if( rc==LSM_OK ){
-    int i;
-    for(i=pCsr->nTree-1; i>0; i--){
-      multiCursorDoCompare(pCsr, i, eESeek==LSM_SEEK_LE);
-    }
-    if( eSeek==LSM_SEEK_GE ) pCsr->flags |= CURSOR_NEXT_OK;
-    if( eSeek==LSM_SEEK_LE ) pCsr->flags |= CURSOR_PREV_OK;
-  }
-
-  multiCursorCacheKey(pCsr, &rc);
-  if( rc==LSM_OK && 0==mcursorLocationOk(pCsr, eSeek==LSM_SEEK_LEFAST) ){
-    switch( eESeek ){
-      case LSM_SEEK_EQ:
-        lsmMCursorReset(pCsr);
-        break;
-      case LSM_SEEK_GE:
-        rc = lsmMCursorNext(pCsr);
-        break;
-      default:
-        rc = lsmMCursorPrev(pCsr);
-        break;
+    assert( pPtr->pSeg==&pPtr->pLevel->lhs );
+    rc = seekInLevel(pCsr, pPtr, eESeek, pKey, nKey, &iPgno, &bStop);
+    iPtr += pPtr->pLevel->nRight;
+  }
+
+  if( eSeek!=LSM_SEEK_EQ ){
+    if( rc==LSM_OK ){
+      rc = multiCursorAllocTree(pCsr);
+    }
+    if( rc==LSM_OK ){
+      int i;
+      for(i=pCsr->nTree-1; i>0; i--){
+        multiCursorDoCompare(pCsr, i, eESeek==LSM_SEEK_LE);
+      }
+      if( eSeek==LSM_SEEK_GE ) pCsr->flags |= CURSOR_NEXT_OK;
+      if( eSeek==LSM_SEEK_LE ) pCsr->flags |= CURSOR_PREV_OK;
+    }
+
+    multiCursorCacheKey(pCsr, &rc);
+    if( rc==LSM_OK && eSeek!=LSM_SEEK_LEFAST && 0==mcursorLocationOk(pCsr, 0) ){
+      switch( eESeek ){
+        case LSM_SEEK_EQ:
+          lsmMCursorReset(pCsr);
+          break;
+        case LSM_SEEK_GE:
+          rc = lsmMCursorNext(pCsr);
+          break;
+        default:
+          rc = lsmMCursorPrev(pCsr);
+          break;
+      }
     }
   }
 
   return rc;
 }
 
 int lsmMCursorValid(MultiCursor *pCsr){
   int res = 0;
-  if( pCsr->aTree ){
+  if( pCsr->flags & CURSOR_SEEK_EQ ){
+    res = 1;
+  }else if( pCsr->aTree ){
     int iKey = pCsr->aTree[1];
     if( iKey==CURSOR_DATA_TREE0 || iKey==CURSOR_DATA_TREE1 ){
       res = lsmTreeCursorValid(pCsr->apTreeCsr[iKey-CURSOR_DATA_TREE0]);
     }else{
       void *pKey; 
@@ -2390,38 +2661,53 @@
   ** or less than (if bReverse!=0) the key currently cached in pCsr->key, 
   ** then the cursor has not yet been successfully advanced.  
   */
   multiCursorGetKey(pCsr, pCsr->aTree[1], &eNewType, &pNew, &nNew);
   if( pNew ){
-    int res = rtTopic(eNewType) - rtTopic(pCsr->eType);
-    if( res==0 ){
-      res = pCsr->pDb->xCmp(pNew, nNew, pCsr->key.pData, pCsr->key.nData);
-    }
+    int res = sortedDbKeyCompare(pCsr->pDb->xCmp, 
+        eNewType, pNew, nNew, pCsr->eType, pCsr->key.pData, pCsr->key.nData
+    );
     if( (bReverse==0 && res<=0) || (bReverse!=0 && res>=0) ){
       return 0;
     }
-  }
-
-  multiCursorCacheKey(pCsr, pRc);
-  assert( pCsr->eType==eNewType );
-
-  /* If this cursor is configured to skip deleted keys, and the current
-  ** cursor points to a SORTED_DELETE entry, then the cursor has not been 
-  ** successfully advanced.  
-  **
-  ** Similarly, if the cursor is configured to skip system keys and the
-  ** current cursor points to a system key, it has not yet been advanced.
-  */
-  if( *pRc==LSM_OK && 0==mcursorLocationOk(pCsr, 0) ) return 0;
+
+    multiCursorCacheKey(pCsr, pRc);
+    assert( pCsr->eType==eNewType );
+
+    /* If this cursor is configured to skip deleted keys, and the current
+    ** cursor points to a SORTED_DELETE entry, then the cursor has not been 
+    ** successfully advanced.  
+    **
+    ** Similarly, if the cursor is configured to skip system keys and the
+    ** current cursor points to a system key, it has not yet been advanced.
+     */
+    if( *pRc==LSM_OK && 0==mcursorLocationOk(pCsr, 0) ) return 0;
+  }
   return 1;
 }
 
 static int multiCursorAdvance(MultiCursor *pCsr, int bReverse){
   int rc = LSM_OK;                /* Return Code */
   if( lsmMCursorValid(pCsr) ){
     do {
       int iKey = pCsr->aTree[1];
+
+      /* If this multi-cursor is advancing forwards, and the sub-cursor
+      ** being advanced is the one that separator keys may be being read
+      ** from, record the current absolute pointer value.  */
+      if( pCsr->pPrevMergePtr ){
+        if( iKey==(CURSOR_DATA_SEGMENT+pCsr->nPtr) ){
+          assert( pCsr->pBtCsr );
+          *pCsr->pPrevMergePtr = pCsr->pBtCsr->iPtr;
+        }else if( pCsr->pBtCsr==0 && pCsr->nPtr>0
+               && iKey==(CURSOR_DATA_SEGMENT+pCsr->nPtr-1) 
+        ){
+          SegmentPtr *pPtr = &pCsr->aPtr[iKey-CURSOR_DATA_SEGMENT];
+          *pCsr->pPrevMergePtr = pPtr->iPtr+pPtr->iPgPtr;
+        }
+      }
+
       if( iKey==CURSOR_DATA_TREE0 || iKey==CURSOR_DATA_TREE1 ){
         TreeCursor *pTreeCsr = pCsr->apTreeCsr[iKey-CURSOR_DATA_TREE0];
         if( bReverse ){
           rc = lsmTreeCursorPrev(pTreeCsr);
         }else{
@@ -2436,11 +2722,10 @@
         assert( bReverse==0 && pCsr->pBtCsr );
         rc = btreeCursorNext(pCsr->pBtCsr);
       }else{
         rc = segmentCursorAdvance(pCsr, iKey-CURSOR_DATA_SEGMENT, bReverse);
       }
-
       if( rc==LSM_OK ){
         int i;
         for(i=(iKey+pCsr->nTree)/2; i>0; i=i/2){
           multiCursorDoCompare(pCsr, i, bReverse);
         }
@@ -2459,55 +2744,66 @@
   if( (pCsr->flags & CURSOR_PREV_OK)==0 ) return LSM_MISUSE_BKPT;
   return multiCursorAdvance(pCsr, 1);
 }
 
 int lsmMCursorKey(MultiCursor *pCsr, void **ppKey, int *pnKey){
-  int iKey = pCsr->aTree[1];
-
-  if( iKey==CURSOR_DATA_TREE0 || iKey==CURSOR_DATA_TREE1 ){
-    TreeCursor *pTreeCsr = pCsr->apTreeCsr[iKey-CURSOR_DATA_TREE0];
-    lsmTreeCursorKey(pTreeCsr, ppKey, pnKey);
+  if( pCsr->flags & CURSOR_SEEK_EQ ){
+    *pnKey = pCsr->key.nData;
+    *ppKey = pCsr->key.pData;
   }else{
-    int nKey;
+    int iKey = pCsr->aTree[1];
+
+    if( iKey==CURSOR_DATA_TREE0 || iKey==CURSOR_DATA_TREE1 ){
+      TreeCursor *pTreeCsr = pCsr->apTreeCsr[iKey-CURSOR_DATA_TREE0];
+      lsmTreeCursorKey(pTreeCsr, 0, ppKey, pnKey);
+    }else{
+      int nKey;
 
 #ifndef NDEBUG
-    void *pKey;
-    int eType;
-    multiCursorGetKey(pCsr, iKey, &eType, &pKey, &nKey);
-    assert( eType==pCsr->eType );
-    assert( nKey==pCsr->key.nData );
-    assert( memcmp(pKey, pCsr->key.pData, nKey)==0 );
+      void *pKey;
+      int eType;
+      multiCursorGetKey(pCsr, iKey, &eType, &pKey, &nKey);
+      assert( eType==pCsr->eType );
+      assert( nKey==pCsr->key.nData );
+      assert( memcmp(pKey, pCsr->key.pData, nKey)==0 );
 #endif
 
-    nKey = pCsr->key.nData;
-    if( nKey==0 ){
-      *ppKey = 0;
-    }else{
-      *ppKey = pCsr->key.pData;
+      nKey = pCsr->key.nData;
+      if( nKey==0 ){
+        *ppKey = 0;
+      }else{
+        *ppKey = pCsr->key.pData;
+      }
+      *pnKey = nKey; 
     }
-    *pnKey = nKey; 
   }
   return LSM_OK;
 }
 
 int lsmMCursorValue(MultiCursor *pCsr, void **ppVal, int *pnVal){
   void *pVal;
   int nVal;
   int rc;
-
-  assert( pCsr->aTree );
-  assert( rtIsDelete(pCsr->eType)==0 || !(pCsr->flags & CURSOR_IGNORE_DELETE) );
-
-  rc = multiCursorGetVal(pCsr, pCsr->aTree[1], &pVal, &nVal);
-  if( pVal && rc==LSM_OK ){
-    rc = sortedBlobSet(pCsr->pDb->pEnv, &pCsr->val, pVal, nVal);
+  if( pCsr->flags & CURSOR_SEEK_EQ ){
+    rc = LSM_OK;
+    nVal = pCsr->val.nData;
     pVal = pCsr->val.pData;
-  }
+  }else{
 
-  if( rc!=LSM_OK ){
-    pVal = 0;
-    nVal = 0;
+    assert( pCsr->aTree );
+    assert( mcursorLocationOk(pCsr, (pCsr->flags & CURSOR_IGNORE_DELETE)) );
+
+    rc = multiCursorGetVal(pCsr, pCsr->aTree[1], &pVal, &nVal);
+    if( pVal && rc==LSM_OK ){
+      rc = sortedBlobSet(pCsr->pDb->pEnv, &pCsr->val, pVal, nVal);
+      pVal = pCsr->val.pData;
+    }
+
+    if( rc!=LSM_OK ){
+      pVal = 0;
+      nVal = 0;
+    }
   }
   *ppVal = pVal;
   *pnVal = nVal;
   return rc;
 }
@@ -2532,12 +2828,12 @@
 
   nRec = lsmGetU16(&aData[SEGMENT_NRECORD_OFFSET(nData)]);
   iOff = lsmGetU16(&aData[SEGMENT_CELLPTR_OFFSET(nData, nRec-1)]);
   eType = aData[iOff++];
   assert( eType==0 
-       || eType==SORTED_SEPARATOR 
-       || eType==SORTED_SYSTEM_SEPARATOR 
+       || eType==(LSM_SYSTEMKEY|LSM_SEPARATOR) 
+       || eType==(LSM_SEPARATOR)
   );
 
   iOff += lsmVarintGet32(&aData[iOff], &nKey);
   iOff += lsmVarintGet32(&aData[iOff], &nKey);
 
@@ -2858,11 +3154,11 @@
   if( bIndirect ){
     aData[iOff++] = 0x00;
     iOff += lsmVarintPut32(&aData[iOff], iPtr);
     iOff += lsmVarintPut32(&aData[iOff], iKeyPg);
   }else{
-    aData[iOff++] = (u8)(iTopic | SORTED_SEPARATOR);
+    aData[iOff++] = (u8)(iTopic | LSM_SEPARATOR);
     iOff += lsmVarintPut32(&aData[iOff], iPtr);
     iOff += lsmVarintPut32(&aData[iOff], nKey);
     memcpy(&aData[iOff], pKey, nKey);
   }
 
@@ -3004,17 +3300,10 @@
   pPg = pMW->pPage;
   aData = fsPageData(pPg, &nData);
   nRec = pageGetNRec(aData, nData);
   iFPtr = pageGetPtr(aData, nData);
 
-  /* If iPtr is 0, set it to the same value as the absolute pointer 
-  ** stored as part of the previous record.  */
-  if( iPtr==0 ){
-    iPtr = iFPtr;
-    if( nRec ) iPtr += pageGetRecordPtr(aData, nData, nRec-1);
-  }
-
   /* Calculate the relative pointer value to write to this record */
   iRPtr = iPtr - iFPtr;
   /* assert( iRPtr>=0 ); */
      
   /* Figure out how much space is required by the new record. The space
@@ -3038,12 +3327,13 @@
 
     /* If the entire header will not fit on page pPg, or if page pPg is 
      ** marked read-only, advance to the next page of the output run. */
     iOff = pMerge->iOutputOff;
     if( iOff<0 || iOff+nHdr > SEGMENT_EOF(nData, nRec+1) ){
-      iFPtr = iFPtr + (nRec ? pageGetRecordPtr(aData, nData, nRec-1) : 0);
+      iFPtr = *pCsr->pPrevMergePtr;
       iRPtr = iPtr - iFPtr;
+
       iOff = 0;
       nRec = 0;
       rc = mergeWorkerNextPage(pMW, iFPtr);
       pPg = pMW->pPage;
     }
@@ -3213,23 +3503,64 @@
     }
   }
 
   if( rc==LSM_OK ){
     rc = mergeWorkerNextPage(pMW, iFPtr);
+    if( pCsr->pPrevMergePtr ) *pCsr->pPrevMergePtr = iFPtr;
   }
 
   return rc;
 }
+
+/*
+** The cursor passed as the first argument is being used as the input for
+** a merge operation. When this function is called, *piFlags contains the
+** database entry flags for the current entry. The entry about to be written
+** to the output.
+**
+*/
+static void mergeRangeDeletes(MultiCursor *pCsr, int *piFlags){
+  int f = *piFlags;
+  int iKey = pCsr->aTree[1];
+  int i;
+
+  if( pCsr->flags & CURSOR_IGNORE_DELETE ){
+    /* The ignore-delete flag is set when the output of the merge will form
+    ** the oldest level in the database. In this case there is no point in
+    ** retaining any range-delete flags.  */
+    assert( (f & LSM_POINT_DELETE)==0 );
+    f &= ~(LSM_START_DELETE|LSM_END_DELETE);
+  }else{
+    if( iKey==0 ){
+      int btreeflags = lsmTreeCursorFlags(pCsr->apTreeCsr[1]);
+      if( btreeflags & LSM_END_DELETE ){
+        f |= (LSM_START_DELETE|LSM_END_DELETE);
+      }
+    }
+
+    for(i=LSM_MAX(0, iKey+1-CURSOR_DATA_SEGMENT); i<pCsr->nPtr; i++){
+      if( pCsr->aPtr[i].eType & LSM_END_DELETE ){
+        f |= (LSM_START_DELETE|LSM_END_DELETE);
+      }
+    }
+
+    if( (f & LSM_START_DELETE) && (f & LSM_END_DELETE) && (f & LSM_INSERT)==0 ){
+      f = 0;
+    }
+  }
+
+  *piFlags = f;
+}
 
 static int mergeWorkerStep(MergeWorker *pMW){
   lsm_db *pDb = pMW->pDb;       /* Database handle */
   MultiCursor *pCsr;            /* Cursor to read input data from */
   int rc = LSM_OK;              /* Return code */
   int eType;                    /* SORTED_SEPARATOR, WRITE or DELETE */
   void *pKey; int nKey;         /* Key */
   Segment *pSeg;                /* Output segment */
-  int iPtr = 0;
+  Pgno iPtr;
 
   pCsr = pMW->pCsr;
   pSeg = &pMW->pLevel->lhs;
 
   /* Pull the next record out of the source cursor. */
@@ -3240,17 +3571,17 @@
   ** than the previous. This is the case if the current key is identical to
   ** a key that appears in the lowest level run being merged. If so, set 
   ** iPtr to the absolute pointer value. If not, leave iPtr set to zero, 
   ** indicating that the output pointer value should be a copy of the pointer 
   ** value written with the previous key.  */
+  iPtr = (pCsr->pPrevMergePtr ? *pCsr->pPrevMergePtr : 0);
   if( pCsr->pBtCsr ){
     BtreeCursor *pBtCsr = pCsr->pBtCsr;
     if( pBtCsr->pKey ){
       int res = rtTopic(pBtCsr->eType) - rtTopic(eType);
       if( res==0 ) res = pDb->xCmp(pBtCsr->pKey, pBtCsr->nKey, pKey, nKey);
       if( 0==res ) iPtr = pBtCsr->iPtr;
-
       assert( res>=0 );
     }
   }else if( pCsr->nPtr ){
     SegmentPtr *pPtr = &pCsr->aPtr[pCsr->nPtr-1];
     if( pPtr->pPg
@@ -3258,33 +3589,37 @@
     ){
       iPtr = pPtr->iPtr+pPtr->iPgPtr;
     }
   }
 
-  if( pMW->aGobble ){
-    int iGobble = pCsr->aTree[1] - CURSOR_DATA_SEGMENT;
-    if( iGobble<pCsr->nPtr ){
-      SegmentPtr *pGobble = &pCsr->aPtr[iGobble];
-      if( (pGobble->flags & PGFTR_SKIP_THIS_FLAG)==0 ){
-        pMW->aGobble[iGobble] = lsmFsPageNumber(pGobble->pPg);
-      }
-    }
-  }
-
-  /* If this is a separator key and we know that the output pointer has not
-  ** changed, there is no point in writing an output record. Otherwise,
-  ** proceed. */
-  if( rtIsSeparator(eType)==0 || iPtr!=0 ){
-    int iSPtr = 0;                /* Separators require a pointer here */
-
-    if( pMW->pPage==0 ){
-      rc = mergeWorkerFirstPage(pMW);
-    }
-
-    /* Write the record into the main run. */
-    if( rc==LSM_OK ){
-      rc = mergeWorkerWrite(pMW, eType, pKey, nKey, pCsr, iPtr, &iSPtr);
+  mergeRangeDeletes(pCsr, &eType);
+
+  if( eType!=0 ){
+    if( pMW->aGobble ){
+      int iGobble = pCsr->aTree[1] - CURSOR_DATA_SEGMENT;
+      if( iGobble<pCsr->nPtr ){
+        SegmentPtr *pGobble = &pCsr->aPtr[iGobble];
+        if( (pGobble->flags & PGFTR_SKIP_THIS_FLAG)==0 ){
+          pMW->aGobble[iGobble] = lsmFsPageNumber(pGobble->pPg);
+        }
+      }
+    }
+
+    /* If this is a separator key and we know that the output pointer has not
+    ** changed, there is no point in writing an output record. Otherwise,
+    ** proceed. */
+    if( rtIsSeparator(eType)==0 || iPtr!=0 ){
+      int iSPtr = 0;                /* Separators require a pointer here */
+
+      if( pMW->pPage==0 ){
+        rc = mergeWorkerFirstPage(pMW);
+      }
+
+      /* Write the record into the main run. */
+      if( rc==LSM_OK ){
+        rc = mergeWorkerWrite(pMW, eType, pKey, nKey, pCsr, iPtr, &iSPtr);
+      }
     }
   }
 
   /* Advance the cursor to the next input record (assuming one exists). */
   assert( lsmMCursorValid(pMW->pCsr) );
@@ -3343,11 +3678,11 @@
   int rc = LSM_OK;                /* Return Code */
   MultiCursor *pCsr = 0;
   Level *pNext = 0;               /* The current top level */
   Level *pNew;                    /* The new level itself */
   Segment *pDel = 0;              /* Delete separators from this segment */
-  int iLeftPtr = 0;
+  Pgno iLeftPtr = 0;
   int nWrite = 0;                 /* Number of database pages written */
 
   assert( pnOvfl );
 
   /* Allocate the new level structure to write to. */
@@ -3384,10 +3719,11 @@
 
     pNew->pMerge = &merge;
     mergeworker.pDb = pDb;
     mergeworker.pLevel = pNew;
     mergeworker.pCsr = pCsr;
+    pCsr->pPrevMergePtr = &iLeftPtr;
 
     /* Mark the separators array for the new level as a "phantom". */
     mergeworker.bFlush = 1;
 
     /* Allocate the first page of the output segment. */
@@ -3415,11 +3751,11 @@
   if( rc==LSM_OK ){
     sortedInvokeWorkHook(pDb);
   }
 
 #if 0
-  lsmSortedDumpStructure(pDb, pDb->pWorker, 0, 0, "new-toplevel");
+  lsmSortedDumpStructure(pDb, pDb->pWorker, 1, 0, "new-toplevel");
 #endif
 
   if( pnWrite ) *pnWrite = nWrite;
   pDb->pWorker->nWrite += nWrite;
   return rc;
@@ -3583,10 +3919,11 @@
   /* Load the current output page into memory. */
   if( rc==LSM_OK ) rc = mergeWorkerLoadOutputPage(pMW);
 
   /* Position the cursor. */
   if( rc==LSM_OK ){
+    pCsr->pPrevMergePtr = &pMerge->iCurrentPtr;
     if( pMW->pPage==0 ){
       /* The output array is still empty. So position the cursor at the very 
       ** start of the input.  */
       rc = multiCursorEnd(pCsr, 0);
     }else{
@@ -3788,23 +4125,10 @@
               rc = sortedBtreeGobble(pDb, mergeworker.pCsr, i);
             }else if( mergeworker.aGobble[i] ){
               lsmFsGobble(pDb, pGobble->pSeg, &mergeworker.aGobble[i], 1);
             }
           }
-#if 0
-          int iGobble = mergeworker.pCsr->aTree[1] - CURSOR_DATA_SEGMENT;
-          if( iGobble<pLevel->nRight ){
-            SegmentPtr *pGobble = &mergeworker.pCsr->aSegCsr[iGobble].aPtr[0];
-            if( pGobble->pSeg->iRoot ){
-              rc = sortedBtreeGobble(pDb, mergeworker.pCsr, iGobble);
-            }else if( (pGobble->flags & PGFTR_SKIP_THIS_FLAG)==0 ){
-              Pgno iPg = lsmFsPageNumber(pGobble->pPg);
-              lsmFsGobble(pDb, pGobble->pSeg, &iPg, 1);
-            }
-          }
-#endif
-
         }else if( pLevel->lhs.iFirst==0 ){
           /* If the new level is completely empty, remove it from the 
           ** database snapshot. This can only happen if all input keys were
           ** annihilated. Since keys are only annihilated if the new level
           ** is the last in the linked list (contains the most ancient of
@@ -3850,20 +4174,19 @@
       ** has occurred, invoke the work-hook to inform the application that
       ** the database structure has changed. */
       mergeWorkerShutdown(&mergeworker, &rc);
       if( rc==LSM_OK ) sortedInvokeWorkHook(pDb);
 
+#if 0
+      lsmSortedDumpStructure(pDb, pDb->pWorker, 1, 0, "work");
+#endif
+      assertRunInOrder(pDb, &pLevel->lhs);
+
       /* If bFlush is true and the database is no longer considered "full",
       ** break out of the loop even if nRemaining is still greater than
       ** zero. The caller has an in-memory tree to flush to disk.  */
       if( bFlush && sortedDbIsFull(pDb)==0 ) break;
-
-      assertRunInOrder(pDb, &pLevel->lhs);
-
-#if 0
-      lsmSortedDumpStructure(pDb, pDb->pWorker, 0, 0, "work");
-#endif
     }
   }
 
   if( pnWrite ) *pnWrite = (nWork - nRemaining);
   pWorker->nWrite += (nWork - nRemaining);
@@ -3872,54 +4195,10 @@
   lsmLogMessage(pDb, rc, "sortedWork(): %d pages", (nWork-nRemaining));
 #endif
   return rc;
 }
 
-typedef struct Metric Metric;
-struct Metric {
-  double fAvgHeight;
-  int nTotalSz;
-  int nMinSz;
-};
-
-#if 0
-static void sortedMeasureDb(lsm_db *pDb, Metric *p){
-  Level *pLevel;                  /* Used to iterate through levels */
-  assert( pDb->pWorker );
-
-  double fHeight = 0.0;
-  int nTotalSz = 0;
-  int nMinSz = 0;
-
-  for(pLevel=lsmDbSnapshotLevel(pDb->pWorker); pLevel; pLevel=pLevel->pNext){
-    const int nLhsSz = pLevel->lhs.run.nSize;
-    int nRhsSz = 0;
-    int nSz;
-    int i;
-
-    for(i=0; i<pLevel->nRight; i++){
-      nRhsSz += pLevel->aRhs[i].run.nSize;
-    }
-
-    nSz = nRhsSz + nLhsSz;
-    fHeight += (double)nLhsSz/nSz + (double)nRhsSz/nSz * pLevel->nRight;
-    nTotalSz += nSz;
-
-    if( nMinSz==0 || nMinSz>nSz ) nMinSz = nSz;
-  }
-
-  if( nMinSz ){
-    printf("avg-height=%.2f log2(min/total)=%.2f totalsz=%d minsz=%d\n", 
-        fHeight, 
-        log((double)nTotalSz / nMinSz) / log(2),
-        nTotalSz,
-        nMinSz
-    );
-  }
-}
-#endif
-
 /*
 ** The database connection passed as the first argument must be a worker
 ** connection. This function checks if there exists an "old" in-memory tree
 ** ready to be flushed to disk. If so, *pbOut is set to true before 
 ** returning. Otherwise false.
@@ -4356,15 +4635,28 @@
     }
   }
   return LSM_OK;
 }
 
-int lsmInfoPageDump(lsm_db *pDb, Pgno iPg, int bHex, char **pzOut){
+#define INFO_PAGE_DUMP_DATA   0x01
+#define INFO_PAGE_DUMP_VALUES 0x02
+#define INFO_PAGE_DUMP_HEX    0x04
+
+static int infoPageDump(
+  lsm_db *pDb,                    /* Database handle */
+  Pgno iPg,                       /* Page number of page to dump */
+  int flags,
+  char **pzOut                    /* OUT: lsmMalloc'd string */
+){
   int rc = LSM_OK;                /* Return code */
   Page *pPg = 0;                  /* Handle for page iPg */
   int i, j;                       /* Loop counters */
   const int perLine = 16;         /* Bytes per line in the raw hex dump */
+
+  int bValues = (flags & INFO_PAGE_DUMP_VALUES);
+  int bHex = (flags & INFO_PAGE_DUMP_HEX);
+  int bData = (flags & INFO_PAGE_DUMP_DATA);
 
   *pzOut = 0;
   if( iPg==0 ) return LSM_ERROR;
 
   rc = lsmFsDbPageGet(pDb->pFS, iPg, &pPg);
@@ -4402,66 +4694,79 @@
       u8 *aVal; int nVal = 0;       /* Value */
       int iPgPtr;
       int eType;
       char cType = '?';
       Pgno iAbsPtr;
+      char zFlags[8];
 
       infoCellDump(pDb, pPg, iCell, &eType, &iPgPtr,
           &aKey, &nKey, &aVal, &nVal, &blob
       );
       iAbsPtr = iPgPtr + ((flags & SEGMENT_BTREE_FLAG) ? 0 : iPtr);
 
-      if( rtIsDelete(eType) ) cType = 'D';
-      if( rtIsWrite(eType) ) cType = 'W';
-      if( rtIsSeparator(eType) ) cType = 'S';
-      lsmStringAppendf(&str, "%c %d (%s) ", 
-          cType, iAbsPtr, (rtTopic(eType) ? "sys" : "usr")
+      lsmFlagsToString(eType, zFlags);
+      lsmStringAppendf(&str, "%s %d (%s) ", 
+          zFlags, iAbsPtr, (rtTopic(eType) ? "sys" : "usr")
       );
       infoAppendBlob(&str, bHex, aKey, nKey); 
-      if( nVal>0 ){
+      if( nVal>0 && bValues ){
         lsmStringAppendf(&str, "%*s", nKeyWidth - (nKey*(1+bHex)), "");
         lsmStringAppendf(&str, " ");
         infoAppendBlob(&str, bHex, aVal, nVal); 
       }
       lsmStringAppendf(&str, "\n");
     }
 
-    lsmStringAppendf(&str, "\n-------------------" 
-       "-------------------------------------------------------------\n");
-    lsmStringAppendf(&str, "Page %d\n",
-                     iPg, (iPg-1)*nData, iPg*nData - 1);
-    for(i=0; i<nData; i += perLine){
-      lsmStringAppendf(&str, "%04x: ", i);
-      for(j=0; j<perLine; j++){
-        if( i+j>nData ){
-          lsmStringAppendf(&str, "   ");
-        }else{
-          lsmStringAppendf(&str, "%02x ", aData[i+j]);
-        }
-      }
-      lsmStringAppendf(&str, "  ");
-      for(j=0; j<perLine; j++){
-        if( i+j>nData ){
-          lsmStringAppendf(&str, " ");
-        }else{
-          lsmStringAppendf(&str,"%c", isprint(aData[i+j]) ? aData[i+j] : '.');
-        }
-      }
-      lsmStringAppendf(&str,"\n");
+    if( bData ){
+      lsmStringAppendf(&str, "\n-------------------" 
+          "-------------------------------------------------------------\n");
+      lsmStringAppendf(&str, "Page %d\n",
+          iPg, (iPg-1)*nData, iPg*nData - 1);
+      for(i=0; i<nData; i += perLine){
+        lsmStringAppendf(&str, "%04x: ", i);
+        for(j=0; j<perLine; j++){
+          if( i+j>nData ){
+            lsmStringAppendf(&str, "   ");
+          }else{
+            lsmStringAppendf(&str, "%02x ", aData[i+j]);
+          }
+        }
+        lsmStringAppendf(&str, "  ");
+        for(j=0; j<perLine; j++){
+          if( i+j>nData ){
+            lsmStringAppendf(&str, " ");
+          }else{
+            lsmStringAppendf(&str,"%c", isprint(aData[i+j]) ? aData[i+j] : '.');
+          }
+        }
+        lsmStringAppendf(&str,"\n");
+      }
     }
 
     *pzOut = str.z;
     sortedBlobFree(&blob);
     lsmFsPageRelease(pPg);
   }
 
   return rc;
 }
+
+int lsmInfoPageDump(
+  lsm_db *pDb,                    /* Database handle */
+  Pgno iPg,                       /* Page number of page to dump */
+  int bHex,                       /* True to output key/value in hex form */
+  char **pzOut                    /* OUT: lsmMalloc'd string */
+){
+  int flags = INFO_PAGE_DUMP_DATA | INFO_PAGE_DUMP_VALUES;
+  if( bHex ) flags |= INFO_PAGE_DUMP_HEX;
+  return infoPageDump(pDb, iPg, flags, pzOut);
+}
 
 void sortedDumpSegment(lsm_db *pDb, Segment *pRun, int bVals){
   assert( pDb->xLog );
   if( pRun && pRun->iFirst ){
+    int flags = (bVals ? INFO_PAGE_DUMP_VALUES : 0);
     char *zSeg;
     Page *pPg;
 
     zSeg = segToString(pDb->pEnv, pRun, 0);
     lsmLogMessage(pDb, LSM_OK, "Segment: %s", zSeg);
@@ -4468,11 +4773,17 @@
     lsmFree(pDb->pEnv, zSeg);
 
     lsmFsDbPageGet(pDb->pFS, pRun->iFirst, &pPg);
     while( pPg ){
       Page *pNext;
+      char *z = 0;
+      infoPageDump(pDb, lsmFsPageNumber(pPg), flags, &z);
+      lsmLogMessage(pDb, LSM_OK, "%s", z);
+      lsmFree(pDb->pEnv, z);
+#if 0
       sortedDumpPage(pDb, pRun, pPg, bVals);
+#endif
       lsmFsDbPageNext(pRun, pPg, 1, &pNext);
       lsmFsPageRelease(pPg);
       pPg = pNext;
     }
   }

Index: src/lsm_tree.c
==================================================================
--- src/lsm_tree.c
+++ src/lsm_tree.c
@@ -98,10 +98,40 @@
   u32 iShmid;                     /* Last shared-memory chunk in use by old */
   u32 iRoot;                      /* Offset of root node in shm file */
   u32 nHeight;                    /* Height of tree structure */
 };
 
+#ifndef NDEBUG
+/*
+** assert() that a TreeKey.flags value is sane. Usage:
+**
+**   assert( assertFlagsOk(pTreeKey->flags) );
+*/
+static int assertFlagsOk(u8 keyflags){
+  /* At least one flag must be set. Otherwise, what is this key doing? */
+  assert( keyflags!=0 );
+
+  /* The POINT_DELETE and INSERT flags cannot both be set. */
+  assert( (keyflags & LSM_POINT_DELETE)==0 || (keyflags & LSM_INSERT)==0 );
+
+  /* If both the START_DELETE and END_DELETE flags are set, then the INSERT
+  ** flag must also be set. In other words - the three DELETE flags cannot
+  ** all be set */
+  assert( (keyflags & LSM_END_DELETE)==0 
+       || (keyflags & LSM_START_DELETE)==0 
+       || (keyflags & LSM_POINT_DELETE)==0 
+  );
+
+  return 1;
+}
+
+static int assert_delete_ranges_match(lsm_db *);
+static int treeCountEntries(lsm_db *db);
+#else
+# define assertFlagsOk(x)
+#endif
+
 /*
 ** Container for a key-value pair. Within the *-shm file, each key/value
 ** pair is stored in a single allocation (which may not actually be 
 ** contiguous in memory). Layout is the TreeKey structure, followed by
 ** the nKey bytes of key blob, followed by the nValue bytes of value blob
@@ -108,10 +138,11 @@
 ** (if nValue is non-negative).
 */
 struct TreeKey {
   int nKey;                       /* Size of pKey in bytes */
   int nValue;                     /* Size of pValue. Or negative. */
+  u8 flags;                       /* Various LSM_XXX flags */
 };
 
 #define TK_KEY(p) ((void *)&(p)[1])
 #define TK_VAL(p) ((void *)(((u8 *)&(p)[1]) + (p)->nKey))
 
@@ -283,10 +314,28 @@
 
 static ShmChunk * treeShmChunkRc(lsm_db *pDb, int iChunk, int *pRc){
   return (ShmChunk *)treeShmptr(pDb, iChunk*LSM_SHM_CHUNK_SIZE, pRc);
 }
 
+
+#ifndef NDEBUG
+static void assertIsWorkingChild(
+  lsm_db *db, 
+  TreeNode *pNode, 
+  TreeNode *pParent, 
+  int iCell
+){
+  TreeNode *p;
+  int rc = LSM_OK;
+  u32 iPtr = getChildPtr(pParent, WORKING_VERSION, iCell);
+  p = treeShmptr(db, iPtr, &rc);
+  assert( p==pNode || rc!=LSM_OK );
+}
+#else
+# define assertIsWorkingChild(w,x,y,z)
+#endif
+
 /* Values for the third argument to treeShmkey(). */
 #define TK_LOADKEY  1
 #define TK_LOADVAL  2
 
 static TreeKey *treeShmkey(
@@ -364,10 +413,29 @@
 void assert_tree_looks_ok(int rc, Tree *pTree){
 }
 #else
 # define assert_tree_looks_ok(x,y)
 #endif
+
+void lsmFlagsToString(int flags, char *zFlags){
+
+  zFlags[0] = (flags & LSM_END_DELETE)   ? ']' : '.';
+
+  /* Only one of LSM_POINT_DELETE, LSM_INSERT and LSM_SEPARATOR should ever
+  ** be set. If this is not true, write a '?' to the output.  */
+  switch( flags & (LSM_POINT_DELETE|LSM_INSERT|LSM_SEPARATOR) ){
+    case 0:                zFlags[1] = '.'; break;
+    case LSM_POINT_DELETE: zFlags[1] = '-'; break;
+    case LSM_INSERT:       zFlags[1] = '+'; break;
+    case LSM_SEPARATOR:    zFlags[1] = '^'; break;
+    default:               zFlags[1] = '?'; break;
+  }
+
+  zFlags[2] = (flags & LSM_SYSTEMKEY)    ? '*' : '.';
+  zFlags[3] = (flags & LSM_START_DELETE) ? '[' : '.';
+  zFlags[4] = '\0';
+}
 
 #ifdef LSM_DEBUG
 
 /*
 ** Pointer pBlob points to a buffer containing a blob of binary data
@@ -382,11 +450,11 @@
   if( pStr->nAlloc==0 ) return;
   for(i=0; i<nBlob; i++){
     u8 c = ((u8*)pBlob)[i];
     if( c>='a' && c<='z' ){
       pStr->z[pStr->n++] = c;
-    }else{
+    }else if( c!=0 || nBlob==1 || i!=(nBlob-1) ){
       pStr->z[pStr->n++] = "0123456789abcdef"[(c>>4)&0xf];
       pStr->z[pStr->n++] = "0123456789abcdef"[c&0xf];
     }
   }
   pStr->z[pStr->n] = 0;
@@ -398,57 +466,86 @@
 static void lsmAppendIndent(LsmString *pStr, int nIndent){
   int i;
   lsmStringExtend(pStr, nIndent);
   for(i=0; i<nIndent; i++) lsmStringAppend(pStr, " ", 1);
 }
+
+static void strAppendFlags(LsmString *pStr, u8 flags){
+  char zFlags[8];
+
+  lsmFlagsToString(flags, zFlags);
+  zFlags[4] = ':';
+
+  lsmStringAppend(pStr, zFlags, 5);
+}
 
 void dump_node_contents(
   lsm_db *pDb,
-  u32 iNode,                      /* Print out hte contents of this node */
-  int nIndent,                    /* Number of spaces indentation */
+  u32 iNode,                      /* Print out the contents of this node */
+  char *zPath,                    /* Path from root to this node */
+  int nPath,                      /* Number of bytes in zPath */
   int nHeight                     /* Height: (0==leaf) (1==parent-of-leaf) */
 ){
+  const char *zSpace = "                                           ";
   int i;
   int rc = LSM_OK;
   LsmString s;
   TreeNode *pNode;
   TreeBlob b = {0, 0};
 
-  /* Append the nIndent bytes of space to string s. */
-  lsmStringInit(&s, pDb->pEnv);
-  if( nIndent ) lsmAppendIndent(&s, nIndent);
-
   pNode = (TreeNode *)treeShmptr(pDb, iNode, &rc);
 
-  /* Append each key to string s. */
-  for(i=0; i<3; i++){
-    u32 iPtr = pNode->aiKeyPtr[i];
-    if( iPtr ){
-      TreeKey *pKey = treeShmkey(pDb, pNode->aiKeyPtr[i], TK_LOADKEY, &b, &rc);
-      lsmAppendStrBlob(&s, TK_KEY(pKey), pKey->nKey);
-      lsmStringAppend(&s, "     ", -1);
-    }
-  }
-
-  printf("%s\n", s.z);
-  lsmStringClear(&s);
-
-  for(i=0; i<4 && nHeight>0; i++){
-    u32 iPtr = getChildPtr(pNode, pDb->treehdr.root.iTransId, i);
-    if( iPtr ){
-      dump_node_contents(pDb, iPtr, nIndent + 2, nHeight-1);
+  if( nHeight==0 ){
+    /* Append the nIndent bytes of space to string s. */
+    lsmStringInit(&s, pDb->pEnv);
+
+    /* Append each key to string s. */
+    for(i=0; i<3; i++){
+      u32 iPtr = pNode->aiKeyPtr[i];
+      if( iPtr ){
+        TreeKey *pKey = treeShmkey(pDb, pNode->aiKeyPtr[i], TK_LOADKEY, &b,&rc);
+        strAppendFlags(&s, pKey->flags);
+        lsmAppendStrBlob(&s, TK_KEY(pKey), pKey->nKey);
+        lsmStringAppend(&s, "     ", -1);
+      }
+    }
+
+    printf("% 6d %.*sleaf%.*s: %s\n", 
+        iNode, nPath, zPath, 20-nPath-4, zSpace, s.z
+    );
+    lsmStringClear(&s);
+  }else{
+    for(i=0; i<4 && nHeight>0; i++){
+      u32 iPtr = getChildPtr(pNode, pDb->treehdr.root.iTransId, i);
+      zPath[nPath] = i+'0';
+      zPath[nPath+1] = '/';
+
+      if( iPtr ){
+        dump_node_contents(pDb, iPtr, zPath, nPath+2, nHeight-1);
+      }
+      if( i!=3 && pNode->aiKeyPtr[i] ){
+        TreeKey *pKey = treeShmkey(pDb, pNode->aiKeyPtr[i], TK_LOADKEY, &b,&rc);
+        lsmStringInit(&s, pDb->pEnv);
+        strAppendFlags(&s, pKey->flags);
+        lsmAppendStrBlob(&s, TK_KEY(pKey), pKey->nKey);
+        printf("% 6d %.*s%.*s: %s\n", 
+            iNode, nPath+1, zPath, 20-nPath-1, zSpace, s.z);
+        lsmStringClear(&s);
+      }
     }
   }
 
   tblobFree(pDb, &b);
 }
 
 void dump_tree_contents(lsm_db *pDb, const char *zCaption){
+  char zPath[64];
   TreeRoot *p = &pDb->treehdr.root;
   printf("\n%s\n", zCaption);
+  zPath[0] = '/';
   if( p->iRoot ){
-    dump_node_contents(pDb, p->iRoot, 0, p->nHeight-1);
+    dump_node_contents(pDb, p->iRoot, zPath, 1, p->nHeight-1);
   }
   fflush(stdout);
 }
 
 #endif
@@ -471,14 +568,16 @@
 /*
 ** Return a pointer to the mapping of the TreeKey object that the cursor
 ** is pointing to. 
 */
 static TreeKey *csrGetKey(TreeCursor *pCsr, TreeBlob *pBlob, int *pRc){
-  return (TreeKey *)treeShmkey(pCsr->pDb,
+  TreeKey *pRet = (TreeKey *)treeShmkey(pCsr->pDb,
       pCsr->apTreeNode[pCsr->iNode]->aiKeyPtr[pCsr->aiCell[pCsr->iNode]], 
       TK_LOADVAL, pBlob, pRc
   );
+  assert( pRet==0 || assertFlagsOk(pRet->flags) );
+  return pRet;
 }
 
 /*
 ** Save the current position of tree cursor pCsr.
 */
@@ -1076,16 +1175,20 @@
 
   p = treeShmChunkRc(db, db->treehdr.iFirst, &rc);
   iShmid = p->iShmid;
   while( rc==LSM_OK && p ){
     if( p->iNext ){
-      ShmChunk *pNext = treeShmChunkRc(db, p->iNext, &rc);
-      if( rc==LSM_OK ){
-        if( pNext->iShmid!=p->iShmid+1 ){
-          rc = LSM_CORRUPT_BKPT;
+      if( p->iNext>=db->treehdr.nChunk ){
+        rc = LSM_CORRUPT_BKPT;
+      }else{
+        ShmChunk *pNext = treeShmChunkRc(db, p->iNext, &rc);
+        if( rc==LSM_OK ){
+          if( pNext->iShmid!=p->iShmid+1 ){
+            rc = LSM_CORRUPT_BKPT;
+          }
+          p = pNext;
         }
-        p = pNext;
       }
     }else{
       p = 0;
     }
     nVisit++;
@@ -1165,11 +1268,11 @@
     nByte = sizeof(ShmChunkLoc) * nSort * 2;
     aSort = lsmMallocZeroRc(db->pEnv, nByte, &rc);
     iPrevShmid = pMin->iShmid;
 
     /* Fix all shm-ids, if required. */
-    if( rc==LSM_OK && iMin!=db->treehdr.iFirst ){
+    if( rc==LSM_OK ){
       iPrevShmid = pMin->iShmid-1;
       for(i=1; i<db->treehdr.nChunk; i++){
         p = treeShmChunk(db, i);
         aSort[i-1].pShm = p;
         aSort[i-1].iLoc = i;
@@ -1177,12 +1280,14 @@
           if( shm_sequence_ge(p->iShmid, db->treehdr.iNextShmid) ){
             p->iShmid = iPrevShmid--;
           }
         }
       }
-      p = treeShmChunk(db, db->treehdr.iFirst);
-      p->iShmid = iPrevShmid;
+      if( iMin!=db->treehdr.iFirst ){
+        p = treeShmChunk(db, db->treehdr.iFirst);
+        p->iShmid = iPrevShmid;
+      }
     }
 
     if( rc==LSM_OK ){
       ShmChunkLoc *aSpace = &aSort[nSort];
       for(i=0; i<nSort; i++){
@@ -1244,38 +1349,161 @@
 
   memcpy(&db->treehdr, &hdr, sizeof(TreeHeader));
   return rc;
 }
 
-/*
-** Insert a new entry into the in-memory tree.
-**
-** If the value of the 5th parameter, nVal, is negative, then a delete-marker
-** is inserted into the tree. In this case the value pointer, pVal, must be
-** NULL.
-*/
-int lsmTreeInsert(
+static void treeOverwriteKey(lsm_db *db, TreeCursor *pCsr, u32 iKey, int *pRc){
+  if( *pRc==LSM_OK ){
+    TreeRoot *p = &db->treehdr.root;
+    TreeNode *pNew;
+    u32 iNew;
+    TreeNode *pNode = pCsr->apTreeNode[pCsr->iNode];
+    int iCell = pCsr->aiCell[pCsr->iNode];
+
+    /* Create a copy of this node */
+    if( (pCsr->iNode>0 && pCsr->iNode==(p->nHeight-1)) ){
+      pNew = copyTreeLeaf(db, (TreeLeaf *)pNode, &iNew, pRc);
+    }else{
+      pNew = copyTreeNode(db, pNode, &iNew, pRc);
+    }
+
+    if( pNew ){
+      /* Modify the value in the new version */
+      pNew->aiKeyPtr[iCell] = iKey;
+
+      /* Change the pointer in the parent (if any) to point at the new 
+       ** TreeNode */
+      pCsr->iNode--;
+      treeUpdatePtr(db, pCsr, iNew);
+    }
+  }
+}
+
+static int treeNextIsEndDelete(lsm_db *db, TreeCursor *pCsr){
+  TreeNode *pNode;
+  int iNode = pCsr->iNode;
+  int iCell = pCsr->aiCell[iNode]+1;
+
+  /* Cursor currently points to a leaf node. */
+  assert( pCsr->iNode==(db->treehdr.root.nHeight-1) );
+
+  while( iNode>=0 ){
+    TreeNode *pNode = pCsr->apTreeNode[iNode];
+    if( iCell<3 && pNode->aiKeyPtr[iCell] ){
+      int rc = LSM_OK;
+      TreeKey *pKey = treeShmptr(db, pNode->aiKeyPtr[iCell], &rc);
+      assert( rc==LSM_OK );
+      return ((pKey->flags & LSM_END_DELETE) ? 1 : 0);
+    }
+    iNode--;
+    iCell = pCsr->aiCell[iNode];
+  }
+
+  return 0;
+}
+
+static int treePrevIsStartDelete(lsm_db *db, TreeCursor *pCsr){
+  TreeNode *pNode;
+  int iNode = pCsr->iNode;
+
+  /* Cursor currently points to a leaf node. */
+  assert( pCsr->iNode==(db->treehdr.root.nHeight-1) );
+
+  while( iNode>=0 ){
+    TreeNode *pNode = pCsr->apTreeNode[iNode];
+    int iCell = pCsr->aiCell[iNode]-1;
+    if( iCell>=0 && pNode->aiKeyPtr[iCell] ){
+      int rc = LSM_OK;
+      TreeKey *pKey = treeShmptr(db, pNode->aiKeyPtr[iCell], &rc);
+      assert( rc==LSM_OK );
+      return ((pKey->flags & LSM_START_DELETE) ? 1 : 0);
+    }
+    iNode--;
+  }
+
+  return 0;
+}
+
+
+static int treeInsertEntry(
   lsm_db *pDb,                    /* Database handle */
+  int flags,                      /* Flags associated with entry */
   void *pKey,                     /* Pointer to key data */
   int nKey,                       /* Size of key data in bytes */
   void *pVal,                     /* Pointer to value data (or NULL) */
   int nVal                        /* Bytes in value data (or -ve for delete) */
 ){
   int rc = LSM_OK;                /* Return Code */
   TreeKey *pTreeKey;              /* New key-value being inserted */
   u32 iTreeKey;
   TreeRoot *p = &pDb->treehdr.root;
+  TreeCursor csr;                 /* Cursor to seek to pKey/nKey */
+  int res;                        /* Result of seek operation on csr */
 
   assert( nVal>=0 || pVal==0 );
   assert_tree_looks_ok(LSM_OK, pTree);
+  assert( flags==LSM_INSERT       || flags==LSM_POINT_DELETE 
+       || flags==LSM_START_DELETE || flags==LSM_END_DELETE 
+  );
 #if 0
   dump_tree_contents(pDb, "before");
 #endif
+
+  if( p->iRoot ){
+    TreeKey *pRes;                /* Key at end of seek operation */
+    treeCursorInit(pDb, 0, &csr);
+
+    /* Seek to the leaf (or internal node) that the new key belongs on */
+    rc = lsmTreeCursorSeek(&csr, pKey, nKey, &res);
+    pRes = csrGetKey(&csr, &csr.blob, &rc);
+    if( rc!=LSM_OK ) return rc;
+
+    if( flags==LSM_START_DELETE ){
+      /* When inserting a start-delete-range entry, if the key that
+      ** occurs immediately before the new entry is already a START_DELETE,
+      ** then the new entry is not required.  */
+      if( (res<=0 && (pRes->flags & LSM_START_DELETE))
+       || (res>0  && treePrevIsStartDelete(pDb, &csr))
+      ){ 
+        goto insert_entry_out;
+      }
+    }else if( flags==LSM_END_DELETE ){
+      /* When inserting an start-delete-range entry, if the key that
+      ** occurs immediately after the new entry is already an END_DELETE,
+      ** then the new entry is not required.  */
+      if( (res<0  && treeNextIsEndDelete(pDb, &csr))
+       || (res>=0 && (pRes->flags & LSM_END_DELETE))
+      ){
+        goto insert_entry_out;
+      }
+    }
+
+    if( res==0 && (flags & (LSM_END_DELETE|LSM_START_DELETE)) ){
+      if( pRes->flags & LSM_INSERT ){
+        nVal = pRes->nValue;
+        pVal = TK_VAL(pRes);
+      }
+      flags = flags | pRes->flags;
+    }
+
+    if( flags & (LSM_INSERT|LSM_POINT_DELETE) ){
+      if( (res<0 && (pRes->flags & LSM_START_DELETE))
+       || (res>0 && (pRes->flags & LSM_END_DELETE)) 
+      ){
+        flags = flags | (LSM_END_DELETE|LSM_START_DELETE);
+      }else if( res==0 ){
+        flags = flags | (pRes->flags & (LSM_END_DELETE|LSM_START_DELETE));
+      }
+    }
+  }else{
+    memset(&csr, 0, sizeof(TreeCursor));
+  }
 
   /* Allocate and populate a new key-value pair structure */
   pTreeKey = newTreeKey(pDb, &iTreeKey, pKey, nKey, pVal, nVal, &rc);
   if( rc!=LSM_OK ) return rc;
+  pTreeKey->flags = flags;
 
   if( p->iRoot==0 ){
     /* The tree is completely empty. Add a new root node and install
     ** (pKey/nKey) as the middle entry. Even though it is a leaf at the
     ** moment, use newTreeNode() to allocate the node (i.e. allocate enough
@@ -1286,40 +1514,13 @@
       assert( p->nHeight==0 );
       pRoot->aiKeyPtr[1] = iTreeKey;
       p->nHeight = 1;
     }
   }else{
-    TreeCursor csr;
-    int res;
-
-    /* Seek to the leaf (or internal node) that the new key belongs on */
-    treeCursorInit(pDb, 0, &csr);
-    lsmTreeCursorSeek(&csr, pKey, nKey, &res);
-
     if( res==0 ){
       /* The search found a match within the tree. */
-      TreeNode *pNew;
-      u32 iNew;
-      TreeNode *pNode = csr.apTreeNode[csr.iNode];
-      int iCell = csr.aiCell[csr.iNode];
-
-      /* Create a copy of this node */
-      if( (csr.iNode>0 && csr.iNode==(p->nHeight-1)) ){
-        pNew = copyTreeLeaf(pDb, (TreeLeaf *)pNode, &iNew, &rc);
-      }else{
-        pNew = copyTreeNode(pDb, pNode, &iNew, &rc);
-      }
-
-      if( rc==LSM_OK ){
-        /* Modify the value in the new version */
-        pNew->aiKeyPtr[iCell] = iTreeKey;
-
-        /* Change the pointer in the parent (if any) to point at the new 
-        ** TreeNode */
-        csr.iNode--;
-        treeUpdatePtr(pDb, &csr, iNew);
-      }
+      treeOverwriteKey(pDb, &csr, iTreeKey, &rc);
     }else{
       /* The cursor now points to the leaf node into which the new entry should
       ** be inserted. There may or may not be a free slot within the leaf for
       ** the new key-value pair. 
       **
@@ -1333,19 +1534,363 @@
         rc = treeInsert(pDb, &csr, 0, iTreeKey, 0, iSlot);
       }else{
         rc = treeInsertLeaf(pDb, &csr, iTreeKey, iSlot);
       }
     }
-    tblobFree(pDb, &csr.blob);
   }
 
 #if 0
   dump_tree_contents(pDb, "after");
 #endif
+ insert_entry_out:
+  tblobFree(pDb, &csr.blob);
   assert_tree_looks_ok(rc, pTree);
   return rc;
 }
+
+/*
+** Insert a new entry into the in-memory tree.
+**
+** If the value of the 5th parameter, nVal, is negative, then a delete-marker
+** is inserted into the tree. In this case the value pointer, pVal, must be
+** NULL.
+*/
+int lsmTreeInsert(
+  lsm_db *pDb,                    /* Database handle */
+  void *pKey,                     /* Pointer to key data */
+  int nKey,                       /* Size of key data in bytes */
+  void *pVal,                     /* Pointer to value data (or NULL) */
+  int nVal                        /* Bytes in value data (or -ve for delete) */
+){
+  int flags;
+  if( nVal<0 ){
+    flags = LSM_POINT_DELETE;
+  }else{
+    flags = LSM_INSERT;
+  }
+
+  return treeInsertEntry(pDb, flags, pKey, nKey, pVal, nVal);
+}
+
+static int treeDeleteEntry(lsm_db *db, TreeCursor *pCsr, u32 iNewptr){
+  TreeRoot *p = &db->treehdr.root;
+  TreeNode *pNode = pCsr->apTreeNode[pCsr->iNode];
+  int iSlot = pCsr->aiCell[pCsr->iNode];
+  int bLeaf;
+  int rc = LSM_OK;
+
+  assert( pNode->aiKeyPtr[1] );
+  assert( pNode->aiKeyPtr[iSlot] );
+  assert( iSlot==0 || iSlot==1 || iSlot==2 );
+  assert( (pCsr->iNode==(db->treehdr.root.nHeight-1))==(iNewptr==0) );
+
+  bLeaf = (pCsr->iNode==(p->nHeight-1) && p->nHeight>1);
+  
+  if( pNode->aiKeyPtr[0] || pNode->aiKeyPtr[2] ){
+    /* There are currently at least 2 keys on this node. So just create
+    ** a new copy of the node with one of the keys removed. If the node
+    ** happens to be the root node of the tree, allocate an entire 
+    ** TreeNode structure instead of just a TreeLeaf.  */
+    TreeNode *pNew;
+    u32 iNew;
+
+    if( bLeaf ){
+      pNew = (TreeNode *)newTreeLeaf(db, &iNew, &rc);
+    }else{
+      pNew = newTreeNode(db, &iNew, &rc);
+    }
+    if( pNew ){
+      int i;
+      int iOut = 1;
+      for(i=0; i<4; i++){
+        if( i==iSlot ){
+          i++;
+          if( bLeaf==0 ) pNew->aiChildPtr[iOut] = iNewptr;
+          if( i<3 ) pNew->aiKeyPtr[iOut] = pNode->aiKeyPtr[i];
+          iOut++;
+        }else if( bLeaf || p->nHeight==1 ){
+          if( i<3 && pNode->aiKeyPtr[i] ){
+            pNew->aiKeyPtr[iOut++] = pNode->aiKeyPtr[i];
+          }
+        }else{
+          if( getChildPtr(pNode, WORKING_VERSION, i) ){
+            pNew->aiChildPtr[iOut] = getChildPtr(pNode, WORKING_VERSION, i);
+            if( i<3 ) pNew->aiKeyPtr[iOut] = pNode->aiKeyPtr[i];
+            iOut++;
+          }
+        }
+      }
+      assert( iOut<=4 );
+      assert( bLeaf || pNew->aiChildPtr[0]==0 );
+      pCsr->iNode--;
+      rc = treeUpdatePtr(db, pCsr, iNew);
+    }
+
+  }else if( pCsr->iNode==0 ){
+    /* Removing the only key in the root node. iNewptr is the new root. */
+    assert( iSlot==1 );
+    db->treehdr.root.iRoot = iNewptr;
+    db->treehdr.root.nHeight--;
+
+  }else{
+    /* There is only one key on this node and the node is not the root
+    ** node. Find a peer for this node. Then redistribute the contents of
+    ** the peer and the parent cell between the parent and either one or
+    ** two new nodes.  */
+    TreeNode *pParent;            /* Parent tree node */
+    int iPSlot;
+    u32 iPeer;                    /* Pointer to peer leaf node */
+    int iDir;
+    TreeNode *pPeer;              /* The peer leaf node */
+    TreeNode *pNew1; u32 iNew1;   /* First new leaf node */
+
+    assert( iSlot==1 );
+
+    pParent = pCsr->apTreeNode[pCsr->iNode-1];
+    iPSlot = pCsr->aiCell[pCsr->iNode-1];
+
+    if( iPSlot>0 && getChildPtr(pParent, WORKING_VERSION, iPSlot-1) ){
+      iDir = -1;
+    }else{
+      iDir = +1;
+    }
+    iPeer = getChildPtr(pParent, WORKING_VERSION, iPSlot+iDir);
+    pPeer = (TreeNode *)treeShmptr(db, iPeer, &rc);
+    assertIsWorkingChild(db, pNode, pParent, iPSlot);
+
+    /* Allocate the first new leaf node. This is always required. */
+    if( bLeaf ){
+      pNew1 = (TreeNode *)newTreeLeaf(db, &iNew1, &rc);
+    }else{
+      pNew1 = (TreeNode *)newTreeNode(db, &iNew1, &rc);
+    }
+
+    if( pPeer->aiKeyPtr[0] && pPeer->aiKeyPtr[2] ){
+      /* Peer node is completely full. This means that two new leaf nodes
+      ** and a new parent node are required. */
+
+      TreeNode *pNew2; u32 iNew2; /* Second new leaf node */
+      TreeNode *pNewP; u32 iNewP; /* New parent node */
+
+      if( bLeaf ){
+        pNew2 = (TreeNode *)newTreeLeaf(db, &iNew2, &rc);
+      }else{
+        pNew2 = (TreeNode *)newTreeNode(db, &iNew2, &rc);
+      }
+      pNewP = copyTreeNode(db, pParent, &iNewP, &rc);
+
+      if( iDir==-1 ){
+        pNew1->aiKeyPtr[1] = pPeer->aiKeyPtr[0];
+        if( bLeaf==0 ){
+          pNew1->aiChildPtr[1] = getChildPtr(pPeer, WORKING_VERSION, 0);
+          pNew1->aiChildPtr[2] = getChildPtr(pPeer, WORKING_VERSION, 1);
+        }
+
+        pNewP->aiChildPtr[iPSlot-1] = iNew1;
+        pNewP->aiKeyPtr[iPSlot-1] = pPeer->aiKeyPtr[1];
+        pNewP->aiChildPtr[iPSlot] = iNew2;
+
+        pNew2->aiKeyPtr[0] = pPeer->aiKeyPtr[2];
+        pNew2->aiKeyPtr[1] = pParent->aiKeyPtr[iPSlot-1];
+        if( bLeaf==0 ){
+          pNew2->aiChildPtr[0] = getChildPtr(pPeer, WORKING_VERSION, 2);
+          pNew2->aiChildPtr[1] = getChildPtr(pPeer, WORKING_VERSION, 3);
+          pNew2->aiChildPtr[2] = iNewptr;
+        }
+      }else{
+        pNew1->aiKeyPtr[1] = pParent->aiKeyPtr[iPSlot];
+        if( bLeaf==0 ){
+          pNew1->aiChildPtr[1] = iNewptr;
+          pNew1->aiChildPtr[2] = getChildPtr(pPeer, WORKING_VERSION, 0);
+        }
+
+        pNewP->aiChildPtr[iPSlot] = iNew1;
+        pNewP->aiKeyPtr[iPSlot] = pPeer->aiKeyPtr[0];
+        pNewP->aiChildPtr[iPSlot+1] = iNew2;
+
+        pNew2->aiKeyPtr[0] = pPeer->aiKeyPtr[1];
+        pNew2->aiKeyPtr[1] = pPeer->aiKeyPtr[2];
+        if( bLeaf==0 ){
+          pNew2->aiChildPtr[0] = getChildPtr(pPeer, WORKING_VERSION, 1);
+          pNew2->aiChildPtr[1] = getChildPtr(pPeer, WORKING_VERSION, 2);
+          pNew2->aiChildPtr[2] = getChildPtr(pPeer, WORKING_VERSION, 3);
+        }
+      }
+      assert( pCsr->iNode>=1 );
+      pCsr->iNode -= 2;
+      if( rc==LSM_OK ){
+        assert( pNew1->aiKeyPtr[1] && pNew2->aiKeyPtr[1] );
+        rc = treeUpdatePtr(db, pCsr, iNewP);
+      }
+    }else{
+      int iKOut = 0;
+      int iPOut = 0;
+      int i;
+
+      pCsr->iNode--;
+
+      if( iDir==1 ){
+        pNew1->aiKeyPtr[iKOut++] = pParent->aiKeyPtr[iPSlot];
+        if( bLeaf==0 ) pNew1->aiChildPtr[iPOut++] = iNewptr;
+      }
+      for(i=0; i<3; i++){
+        if( pPeer->aiKeyPtr[i] ){
+          pNew1->aiKeyPtr[iKOut++] = pPeer->aiKeyPtr[i];
+        }
+      }
+      if( bLeaf==0 ){
+        for(i=0; i<4; i++){
+          if( getChildPtr(pPeer, WORKING_VERSION, i) ){
+            pNew1->aiChildPtr[iPOut++] = getChildPtr(pPeer, WORKING_VERSION, i);
+          }
+        }
+      }
+      if( iDir==-1 ){
+        iPSlot--;
+        pNew1->aiKeyPtr[iKOut++] = pParent->aiKeyPtr[iPSlot];
+        if( bLeaf==0 ) pNew1->aiChildPtr[iPOut++] = iNewptr;
+        pCsr->aiCell[pCsr->iNode] = iPSlot;
+      }
+
+      rc = treeDeleteEntry(db, pCsr, iNew1);
+    }
+  }
+
+  return rc;
+}
+
+/*
+** Delete a range of keys from the tree structure (i.e. the lsm_delete_range()
+** function, not lsm_delete()).
+**
+** This is a two step process: 
+**
+**     1) Remove all entries currently stored in the tree that have keys
+**        that fall into the deleted range.
+**
+**        TODO: There are surely good ways to optimize this step - removing 
+**        a range of keys from a b-tree. But for now, this function removes
+**        them one at a time using the usual approach.
+**
+**     2) Unless the largest key smaller than or equal to (pKey1/nKey1) is
+**        already marked as START_DELETE, insert a START_DELETE key. 
+**        Similarly, unless the smallest key greater than or equal to
+**        (pKey2/nKey2) is already START_END, insert a START_END key.
+*/
+int lsmTreeDelete(
+  lsm_db *db,
+  void *pKey1, int nKey1,         /* Start of range */
+  void *pKey2, int nKey2          /* End of range */
+){
+  int rc = LSM_OK;
+  int bDone = 0;
+  TreeRoot *p = &db->treehdr.root;
+  TreeBlob blob = {0, 0};
+
+  /* The range must be sensible - that (key1 < key2). */
+  assert( db->xCmp(pKey1, nKey1, pKey2, nKey2)<0 );
+  assert( assert_delete_ranges_match(db) );
+
+#if 0
+  static int nCall = 0;
+  printf("\n");
+  nCall++;
+  printf("%d delete %s .. %s\n", nCall, (char *)pKey1, (char *)pKey2);
+  dump_tree_contents(db, "before delete");
+#endif
+
+  /* Step 1. This loop runs until the tree contains no keys within the
+  ** range being deleted. Or until an error occurs. */
+  while( bDone==0 && rc==LSM_OK ){
+    int res;
+    TreeCursor csr;               /* Cursor to seek to first key in range */
+    void *pDel; int nDel;         /* Key to (possibly) delete this iteration */
+#ifndef NDEBUG
+    int nEntry = treeCountEntries(db);
+#endif
+
+    /* Seek the cursor to the first entry in the tree greater than pKey1. */
+    treeCursorInit(db, 0, &csr);
+    lsmTreeCursorSeek(&csr, pKey1, nKey1, &res);
+    if( res<=0 && lsmTreeCursorValid(&csr) ) lsmTreeCursorNext(&csr);
+
+    /* If there is no such entry, or if it is greater than pKey2, then the
+    ** tree now contains no keys in the range being deleted. In this case
+    ** break out of the loop.  */
+    bDone = 1;
+    if( lsmTreeCursorValid(&csr) ){
+      lsmTreeCursorKey(&csr, 0, &pDel, &nDel);
+      if( db->xCmp(pDel, nDel, pKey2, nKey2)<0 ) bDone = 0;
+    }
+
+    if( bDone==0 ){
+      if( csr.iNode==(p->nHeight-1) ){
+        /* The element to delete already lies on a leaf node */
+        rc = treeDeleteEntry(db, &csr, 0);
+      }else{
+        /* 1. Overwrite the current key with a copy of the next key in the 
+        **    tree (key N).
+        **
+        ** 2. Seek to key N (cursor will stop at the internal node copy of
+        **    N). Move to the next key (original copy of N). Delete
+        **    this entry. 
+        */
+        u32 iKey;
+        TreeKey *pKey;
+        int iNode = csr.iNode;
+        lsmTreeCursorNext(&csr);
+        assert( csr.iNode==(p->nHeight-1) );
+
+        iKey = csr.apTreeNode[csr.iNode]->aiKeyPtr[csr.aiCell[csr.iNode]];
+        lsmTreeCursorPrev(&csr);
+
+        treeOverwriteKey(db, &csr, iKey, &rc);
+        pKey = treeShmkey(db, iKey, TK_LOADKEY, &blob, &rc);
+        if( pKey ){
+          rc = lsmTreeCursorSeek(&csr, TK_KEY(pKey), pKey->nKey, &res);
+        }
+        if( rc==LSM_OK ){
+          assert( res==0 && csr.iNode==iNode );
+          rc = lsmTreeCursorNext(&csr);
+          if( rc==LSM_OK ){
+            rc = treeDeleteEntry(db, &csr, 0);
+          }
+        }
+      }
+    }
+
+    /* Clean up any memory allocated by the cursor. */
+    tblobFree(db, &csr.blob);
+#if 0
+    dump_tree_contents(db, "ddd delete");
+#endif
+    assert( bDone || treeCountEntries(db)==(nEntry-1) );
+  }
+
+#if 0
+  dump_tree_contents(db, "during delete");
+#endif
+
+  /* Now insert the START_DELETE and END_DELETE keys. */
+  if( rc==LSM_OK ){
+    rc = treeInsertEntry(db, LSM_START_DELETE, pKey1, nKey1, 0, -1);
+  }
+#if 0
+  dump_tree_contents(db, "during delete 2");
+#endif
+  if( rc==LSM_OK ){
+    rc = treeInsertEntry(db, LSM_END_DELETE, pKey2, nKey2, 0, -1);
+  }
+
+#if 0
+  dump_tree_contents(db, "after delete");
+#endif
+
+  tblobFree(db, &blob);
+  assert( assert_delete_ranges_match(db) );
+  return rc;
+}
 
 /*
 ** Return, in bytes, the amount of memory currently used by the tree 
 ** structure.
 */
@@ -1549,11 +2094,11 @@
   }
 
 #ifndef NDEBUG
   if( pCsr->iNode>=0 ){
     TreeKey *pK2 = csrGetKey(pCsr, &pCsr->blob, &rc);
-    assert( rc || pDb->xCmp(TK_KEY(pK2), pK2->nKey, TK_KEY(pK1), pK1->nKey)>0 );
+    assert( rc || pDb->xCmp(TK_KEY(pK2),pK2->nKey,TK_KEY(pK1),pK1->nKey)>=0 );
   }
   tblobFree(pDb, &key1);
 #endif
 
   return rc;
@@ -1631,11 +2176,10 @@
 ** Move the cursor to the first (bLast==0) or last (bLast!=0) entry in the
 ** in-memory tree.
 */
 int lsmTreeCursorEnd(TreeCursor *pCsr, int bLast){
   lsm_db *pDb = pCsr->pDb;
-  TreeHeader *pHdr = &pDb->treehdr;
   TreeRoot *pRoot = pCsr->pRoot;
   int rc = LSM_OK;
 
   u32 iNodePtr;
   pCsr->iNode = -1;
@@ -1668,11 +2212,24 @@
   }
 
   return rc;
 }
 
-int lsmTreeCursorKey(TreeCursor *pCsr, void **ppKey, int *pnKey){
+int lsmTreeCursorFlags(TreeCursor *pCsr){
+  int flags = 0;
+  if( pCsr && pCsr->iNode>=0 ){
+    int rc = LSM_OK;
+    TreeKey *pKey = (TreeKey *)treeShmptr(pCsr->pDb,
+        pCsr->apTreeNode[pCsr->iNode]->aiKeyPtr[pCsr->aiCell[pCsr->iNode]], &rc
+    );
+    assert( rc==LSM_OK );
+    flags = pKey->flags;
+  }
+  return flags;
+}
+
+int lsmTreeCursorKey(TreeCursor *pCsr, int *pFlags, void **ppKey, int *pnKey){
   TreeKey *pTreeKey;
   int rc = LSM_OK;
 
   assert( lsmTreeCursorValid(pCsr) );
 
@@ -1680,10 +2237,11 @@
   if( !pTreeKey ){
     pTreeKey = csrGetKey(pCsr, &pCsr->blob, &rc);
   }
   if( rc==LSM_OK ){
     *pnKey = pTreeKey->nKey;
+    if( pFlags ) *pFlags = pTreeKey->flags;
     *ppKey = (void *)&pTreeKey[1];
   }
 
   return rc;
 }
@@ -1694,15 +2252,16 @@
 
   rc = treeCursorRestore(pCsr, &res);
   if( res==0 ){
     TreeKey *pTreeKey = csrGetKey(pCsr, &pCsr->blob, &rc);
     if( rc==LSM_OK ){
-      *pnVal = pTreeKey->nValue;
-      if( pTreeKey->nValue>=0 ){
+      if( pTreeKey->flags & LSM_INSERT ){
+        *pnVal = pTreeKey->nValue;
         *ppVal = TK_VAL(pTreeKey);
       }else{
         *ppVal = 0;
+        *pnVal = -1;
       }
     }
   }else{
     *ppVal = 0;
     *pnVal = 0;
@@ -1840,6 +2399,49 @@
   pShm->bWriter = 0;
   intArrayFree(pDb->pEnv, &pDb->rollback);
 
   return LSM_OK;
 }
+
+#ifndef NDEBUG
+static int assert_delete_ranges_match(lsm_db *db){
+  int prev = 0;
+  TreeBlob blob = {0, 0};
+  TreeCursor csr;               /* Cursor used to iterate through tree */
+  int rc;
+
+  treeCursorInit(db, 0, &csr);
+  for( rc = lsmTreeCursorEnd(&csr, 0);
+       rc==LSM_OK && lsmTreeCursorValid(&csr);
+       rc = lsmTreeCursorNext(&csr)
+  ){
+    TreeKey *pKey = csrGetKey(&csr, &blob, &rc);
+    if( rc!=LSM_OK ) break;
+    assert( ((prev&LSM_START_DELETE)==0)==((pKey->flags&LSM_END_DELETE)==0) );
+    prev = pKey->flags;
+  }
+
+  tblobFree(csr.pDb, &csr.blob);
+
+  return 1;
+}
+
+static int treeCountEntries(lsm_db *db){
+  TreeCursor csr;               /* Cursor used to iterate through tree */
+  int rc;
+  int nEntry = 0;
+
+  treeCursorInit(db, 0, &csr);
+  for( rc = lsmTreeCursorEnd(&csr, 0);
+       rc==LSM_OK && lsmTreeCursorValid(&csr);
+       rc = lsmTreeCursorNext(&csr)
+  ){
+    nEntry++;
+  }
+
+  tblobFree(csr.pDb, &csr.blob);
+
+  return nEntry;
+}
+#endif
+