idb-bridge: faster indices, various correctness fixes and tests

12 files changed, 1414 insertions, 489 deletions

diff --git a/packages/idb-bridge/package.json b/packages/idb-bridge/package.json
index f3ed0888f..52bc872da 100644
--- a/packages/idb-bridge/package.json
+++ b/packages/idb-bridge/package.json
@@ -19,7 +19,6 @@
     "@rollup/plugin-commonjs": "^17.1.0",
     "@rollup/plugin-json": "^4.1.0",
     "@rollup/plugin-node-resolve": "^11.2.0",
-    "@types/lodash": "^4.14.178",
     "@types/node": "^14.14.22",
     "ava": "^3.15.0",
     "esm": "^3.2.25",
@@ -29,7 +28,6 @@
     "typescript": "^4.1.3"
   },
   "dependencies": {
-    "lodash": "^4.17.21",
     "tslib": "^2.1.0"
   },
   "ava": {
diff --git a/packages/idb-bridge/src/MemoryBackend.test.ts b/packages/idb-bridge/src/MemoryBackend.test.ts
index 292f1b495..ac1a9d908 100644
--- a/packages/idb-bridge/src/MemoryBackend.test.ts
+++ b/packages/idb-bridge/src/MemoryBackend.test.ts
@@ -23,6 +23,12 @@ import {
   BridgeIDBRequest,
   BridgeIDBTransaction,
 } from "./bridge-idb";
+import {
+  IDBCursorDirection,
+  IDBCursorWithValue,
+  IDBKeyRange,
+  IDBValidKey,
+} from "./idbtypes.js";
 import { MemoryBackend } from "./MemoryBackend";
 
 function promiseFromRequest(request: BridgeIDBRequest): Promise<any> {
@@ -104,6 +110,7 @@ test("Spec: Example 1 Part 2", async (t) => {
 
 test("Spec: Example 1 Part 3", async (t) => {
   const backend = new MemoryBackend();
+  backend.enableTracing = true;
   const idb = new BridgeIDBFactory(backend);
 
   const request = idb.open("library");
@@ -348,3 +355,184 @@ test("export", async (t) => {
   t.is(exportedData2.databases["library"].schema.databaseVersion, 42);
   t.pass();
 });
+
+test("range queries", async (t) => {
+  const backend = new MemoryBackend();
+  backend.enableTracing = true;
+  const idb = new BridgeIDBFactory(backend);
+
+  const request = idb.open("mydb");
+  request.onupgradeneeded = () => {
+    const db = request.result;
+    const store = db.createObjectStore("bla", { keyPath: "x" });
+    store.createIndex("by_y", "y");
+    store.createIndex("by_z", "z");
+  };
+
+  const db: BridgeIDBDatabase = await promiseFromRequest(request);
+
+  t.is(db.name, "mydb");
+
+  const tx = db.transaction("bla", "readwrite");
+
+  const store = tx.objectStore("bla");
+
+  store.put({ x: 0, y: "a" });
+  store.put({ x: 2, y: "a" });
+  store.put({ x: 4, y: "b" });
+  store.put({ x: 8, y: "b" });
+  store.put({ x: 10, y: "c" });
+  store.put({ x: 12, y: "c" });
+
+  await promiseFromTransaction(tx);
+
+  async function doCursorStoreQuery(
+    range: IDBKeyRange | IDBValidKey | undefined,
+    direction: IDBCursorDirection | undefined,
+    expected: any[],
+  ): Promise<void> {
+    const tx = db.transaction("bla", "readwrite");
+    const store = tx.objectStore("bla");
+    const vals: any[] = [];
+
+    const req = store.openCursor(range, direction);
+    while (1) {
+      await promiseFromRequest(req);
+      const cursor: IDBCursorWithValue = req.result;
+      if (!cursor) {
+        break;
+      }
+      cursor.continue();
+      vals.push(cursor.value);
+    }
+
+    await promiseFromTransaction(tx);
+
+    t.deepEqual(vals, expected);
+  }
+
+  async function doCursorIndexQuery(
+    range: IDBKeyRange | IDBValidKey | undefined,
+    direction: IDBCursorDirection | undefined,
+    expected: any[],
+  ): Promise<void> {
+    const tx = db.transaction("bla", "readwrite");
+    const store = tx.objectStore("bla");
+    const index = store.index("by_y");
+    const vals: any[] = [];
+
+    const req = index.openCursor(range, direction);
+    while (1) {
+      await promiseFromRequest(req);
+      const cursor: IDBCursorWithValue = req.result;
+      if (!cursor) {
+        break;
+      }
+      cursor.continue();
+      vals.push(cursor.value);
+    }
+
+    await promiseFromTransaction(tx);
+
+    t.deepEqual(vals, expected);
+  }
+
+  await doCursorStoreQuery(undefined, undefined, [
+    {
+      x: 0,
+      y: "a",
+    },
+    {
+      x: 2,
+      y: "a",
+    },
+    {
+      x: 4,
+      y: "b",
+    },
+    {
+      x: 8,
+      y: "b",
+    },
+    {
+      x: 10,
+      y: "c",
+    },
+    {
+      x: 12,
+      y: "c",
+    },
+  ]);
+
+  await doCursorStoreQuery(
+    BridgeIDBKeyRange.bound(0, 12, true, true),
+    undefined,
+    [
+      {
+        x: 2,
+        y: "a",
+      },
+      {
+        x: 4,
+        y: "b",
+      },
+      {
+        x: 8,
+        y: "b",
+      },
+      {
+        x: 10,
+        y: "c",
+      },
+    ],
+  );
+
+  await doCursorIndexQuery(
+    BridgeIDBKeyRange.bound("a", "c", true, true),
+    undefined,
+    [
+      {
+        x: 4,
+        y: "b",
+      },
+      {
+        x: 8,
+        y: "b",
+      },
+    ],
+  );
+
+  await doCursorIndexQuery(undefined, "nextunique", [
+    {
+      x: 0,
+      y: "a",
+    },
+    {
+      x: 4,
+      y: "b",
+    },
+    {
+      x: 10,
+      y: "c",
+    },
+  ]);
+
+  await doCursorIndexQuery(undefined, "prevunique", [
+    {
+      x: 10,
+      y: "c",
+    },
+    {
+      x: 4,
+      y: "b",
+    },
+    {
+      x: 0,
+      y: "a",
+    },
+  ]);
+
+  db.close();
+
+  t.pass();
+});
diff --git a/packages/idb-bridge/src/MemoryBackend.ts b/packages/idb-bridge/src/MemoryBackend.ts
index 41d0d7fbb..de4bca883 100644
--- a/packages/idb-bridge/src/MemoryBackend.ts
+++ b/packages/idb-bridge/src/MemoryBackend.ts
@@ -33,7 +33,7 @@ import {
   structuredRevive,
 } from "./util/structuredClone";
 import { ConstraintError, DataError } from "./util/errors";
-import BTree, { ISortedMapF } from "./tree/b+tree";
+import BTree, { ISortedMapF, ISortedSetF } from "./tree/b+tree";
 import { compareKeys } from "./util/cmp";
 import { StoreKeyResult, makeStoreKeyValue } from "./util/makeStoreKeyValue";
 import { getIndexKeys } from "./util/getIndexKeys";
@@ -96,17 +96,10 @@ interface Database {
 }
 
 /** @public */
-export interface IndexDump {
-  name: string;
-  records: IndexRecord[];
-}
-
-/** @public */
 export interface ObjectStoreDump {
   name: string;
   keyGenerator: number;
   records: ObjectStoreRecord[];
-  indexes: { [name: string]: IndexDump };
 }
 
 /** @public */
@@ -140,7 +133,7 @@ interface Connection {
 /** @public */
 export interface IndexRecord {
   indexKey: Key;
-  primaryKeys: Key[];
+  primaryKeys: ISortedSetF<Key>;
 }
 
 /** @public */
@@ -185,6 +178,27 @@ function nextStoreKey<T>(
   return res[1].primaryKey;
 }
 
+function assertInvariant(cond: boolean): asserts cond {
+  if (!cond) {
+    throw Error("invariant failed");
+  }
+}
+
+function nextKey(
+  forward: boolean,
+  tree: ISortedSetF<IDBValidKey>,
+  key: IDBValidKey | undefined,
+): IDBValidKey | undefined {
+  if (key != null) {
+    return forward ? tree.nextHigherKey(key) : tree.nextLowerKey(key);
+  }
+  return forward ? tree.minKey() : tree.maxKey();
+}
+
+/**
+ * Return the key that is furthest in
+ * the direction indicated by the 'forward' flag.
+ */
 function furthestKey(
   forward: boolean,
   key1: Key | undefined,
@@ -258,22 +272,20 @@ export class MemoryBackend implements Backend {
    * Must be called before any connections to the database backend have
    * been made.
    */
-  importDump(data: any) {
-    if (this.enableTracing) {
-      console.log("importing dump (a)");
-    }
+  importDump(dataJson: any) {
     if (this.transactionIdCounter != 1 || this.connectionIdCounter != 1) {
       throw Error(
         "data must be imported before first transaction or connection",
       );
     }
 
+    // FIXME: validate!
+    const data = structuredRevive(dataJson) as MemoryBackendDump;
+
     if (typeof data !== "object") {
       throw Error("db dump corrupt");
     }
 
-    data = structuredRevive(data);
-
     this.databases = {};
 
     for (const dbName of Object.keys(data.databases)) {
@@ -285,29 +297,10 @@ export class MemoryBackend implements Backend {
       for (const objectStoreName of Object.keys(
         data.databases[dbName].objectStores,
       )) {
-        const dumpedObjectStore =
+        const storeSchema = schema.objectStores[objectStoreName];
+        const dumpedObjectStore: ObjectStoreDump =
           data.databases[dbName].objectStores[objectStoreName];
 
-        const indexes: { [name: string]: Index } = {};
-        for (const indexName of Object.keys(dumpedObjectStore.indexes)) {
-          const dumpedIndex = dumpedObjectStore.indexes[indexName];
-          const pairs = dumpedIndex.records.map((r: any) => {
-            return structuredClone([r.indexKey, r]);
-          });
-          const indexData: ISortedMapF<Key, IndexRecord> = new BTree(
-            pairs,
-            compareKeys,
-          );
-          const index: Index = {
-            deleted: false,
-            modifiedData: undefined,
-            modifiedName: undefined,
-            originalName: indexName,
-            originalData: indexData,
-          };
-          indexes[indexName] = index;
-        }
-
         const pairs = dumpedObjectStore.records.map((r: any) => {
           return structuredClone([r.primaryKey, r]);
         });
@@ -323,10 +316,34 @@ export class MemoryBackend implements Backend {
           originalData: objectStoreData,
           originalName: objectStoreName,
           originalKeyGenerator: dumpedObjectStore.keyGenerator,
-          committedIndexes: indexes,
+          committedIndexes: {},
           modifiedIndexes: {},
         };
         objectStores[objectStoreName] = objectStore;
+
+        for (const indexName in storeSchema.indexes) {
+          const indexSchema = storeSchema.indexes[indexName];
+          const newIndex: Index = {
+            deleted: false,
+            modifiedData: undefined,
+            modifiedName: undefined,
+            originalData: new BTree([], compareKeys),
+            originalName: indexName,
+          };
+          const storeData = objectStoreData;
+
+          storeData.forEach((v, k) => {
+            try {
+              this.insertIntoIndex(newIndex, k, v.value, indexSchema);
+            } catch (e) {
+              if (e instanceof DataError) {
+                // We don't propagate this error here.
+                return;
+              }
+              throw e;
+            }
+          });
+        }
       }
       const db: Database = {
         deleted: false,
@@ -368,16 +385,6 @@ export class MemoryBackend implements Backend {
       const objectStores: { [name: string]: ObjectStoreDump } = {};
       for (const objectStoreName of Object.keys(db.committedObjectStores)) {
         const objectStore = db.committedObjectStores[objectStoreName];
-
-        const indexes: { [name: string]: IndexDump } = {};
-        for (const indexName of Object.keys(objectStore.committedIndexes)) {
-          const index = objectStore.committedIndexes[indexName];
-          const indexRecords: IndexRecord[] = [];
-          index.originalData.forEach((v: IndexRecord) => {
-            indexRecords.push(structuredClone(v));
-          });
-          indexes[indexName] = { name: indexName, records: indexRecords };
-        }
         const objectStoreRecords: ObjectStoreRecord[] = [];
         objectStore.originalData.forEach((v: ObjectStoreRecord) => {
           objectStoreRecords.push(structuredClone(v));
@@ -386,7 +393,6 @@ export class MemoryBackend implements Backend {
           name: objectStoreName,
           records: objectStoreRecords,
           keyGenerator: objectStore.originalKeyGenerator,
-          indexes: indexes,
         };
       }
       const dbDump: DatabaseDump = {
@@ -1047,17 +1053,17 @@ export class MemoryBackend implements Backend {
       indexProperties.multiEntry,
     );
     for (const indexKey of indexKeys) {
-      const existingRecord = indexData.get(indexKey);
-      if (!existingRecord) {
+      const existingIndexRecord = indexData.get(indexKey);
+      if (!existingIndexRecord) {
         throw Error("db inconsistent: expected index entry missing");
       }
-      const newPrimaryKeys = existingRecord.primaryKeys.filter(
-        (x) => compareKeys(x, primaryKey) !== 0,
+      const newPrimaryKeys = existingIndexRecord.primaryKeys.without(
+        primaryKey,
       );
-      if (newPrimaryKeys.length === 0) {
+      if (newPrimaryKeys.size === 0) {
         index.modifiedData = indexData.without(indexKey);
       } else {
-        const newIndexRecord = {
+        const newIndexRecord: IndexRecord = {
           indexKey,
           primaryKeys: newPrimaryKeys,
         };
@@ -1117,11 +1123,6 @@ export class MemoryBackend implements Backend {
       );
     }
 
-    let numResults = 0;
-    let indexKeys: Key[] = [];
-    let primaryKeys: Key[] = [];
-    let values: Value[] = [];
-
     const forward: boolean =
       req.direction === "next" || req.direction === "nextunique";
     const unique: boolean =
@@ -1133,280 +1134,44 @@ export class MemoryBackend implements Backend {
 
     const haveIndex = req.indexName !== undefined;
 
+    let resp: RecordGetResponse;
+
     if (haveIndex) {
       const index =
         myConn.objectStoreMap[req.objectStoreName].indexMap[req.indexName!];
       const indexData = index.modifiedData || index.originalData;
-      let indexPos = req.lastIndexPosition;
-
-      if (indexPos === undefined) {
-        // First time we iterate!  So start at the beginning (lower/upper)
-        // of our allowed range.
-        indexPos = forward ? range.lower : range.upper;
-      }
-
-      let primaryPos = req.lastObjectStorePosition;
-
-      // We might have to advance the index key further!
-      if (req.advanceIndexKey !== undefined) {
-        const compareResult = compareKeys(req.advanceIndexKey, indexPos);
-        if ((forward && compareResult > 0) || (!forward && compareResult > 0)) {
-          indexPos = req.advanceIndexKey;
-        } else if (compareResult == 0 && req.advancePrimaryKey !== undefined) {
-          // index keys are the same, so advance the primary key
-          if (primaryPos === undefined) {
-            primaryPos = req.advancePrimaryKey;
-          } else {
-            const primCompareResult = compareKeys(
-              req.advancePrimaryKey,
-              primaryPos,
-            );
-            if (
-              (forward && primCompareResult > 0) ||
-              (!forward && primCompareResult < 0)
-            ) {
-              primaryPos = req.advancePrimaryKey;
-            }
-          }
-        }
-      }
-
-      if (indexPos === undefined || indexPos === null) {
-        indexPos = forward ? indexData.minKey() : indexData.maxKey();
-      }
-
-      if (indexPos === undefined) {
-        throw Error("invariant violated");
-      }
-
-      let indexEntry: IndexRecord | undefined;
-      indexEntry = indexData.get(indexPos);
-      if (!indexEntry) {
-        const res = forward
-          ? indexData.nextHigherPair(indexPos)
-          : indexData.nextLowerPair(indexPos);
-        if (res) {
-          indexEntry = res[1];
-          indexPos = indexEntry.indexKey;
-        }
-      }
-
-      if (unique) {
-        while (1) {
-          if (req.limit != 0 && numResults == req.limit) {
-            break;
-          }
-          if (indexPos === undefined) {
-            break;
-          }
-          if (!range.includes(indexPos)) {
-            break;
-          }
-          if (indexEntry === undefined) {
-            break;
-          }
-
-          if (
-            req.lastIndexPosition === null ||
-            req.lastIndexPosition === undefined ||
-            compareKeys(indexEntry.indexKey, req.lastIndexPosition) !== 0
-          ) {
-            indexKeys.push(indexEntry.indexKey);
-            primaryKeys.push(indexEntry.primaryKeys[0]);
-            numResults++;
-          }
-
-          const res: any = forward
-            ? indexData.nextHigherPair(indexPos)
-            : indexData.nextLowerPair(indexPos);
-          if (res) {
-            indexPos = res[1].indexKey;
-            indexEntry = res[1] as IndexRecord;
-          } else {
-            break;
-          }
-        }
-      } else {
-        let primkeySubPos = 0;
-
-        // Sort out the case where the index key is the same, so we have
-        // to get the prev/next primary key
-        if (
-          indexEntry !== undefined &&
-          req.lastIndexPosition !== undefined &&
-          compareKeys(indexEntry.indexKey, req.lastIndexPosition) === 0
-        ) {
-          let pos = forward ? 0 : indexEntry.primaryKeys.length - 1;
-          this.enableTracing &&
-            console.log(
-              "number of primary keys",
-              indexEntry.primaryKeys.length,
-            );
-          this.enableTracing && console.log("start pos is", pos);
-          // Advance past the lastObjectStorePosition
-          do {
-            const cmpResult = compareKeys(
-              req.lastObjectStorePosition,
-              indexEntry.primaryKeys[pos],
-            );
-            this.enableTracing && console.log("cmp result is", cmpResult);
-            if ((forward && cmpResult < 0) || (!forward && cmpResult > 0)) {
-              break;
-            }
-            pos += forward ? 1 : -1;
-            this.enableTracing && console.log("now pos is", pos);
-          } while (pos >= 0 && pos < indexEntry.primaryKeys.length);
-
-          // Make sure we're at least at advancedPrimaryPos
-          while (
-            primaryPos !== undefined &&
-            pos >= 0 &&
-            pos < indexEntry.primaryKeys.length
-          ) {
-            const cmpResult = compareKeys(
-              primaryPos,
-              indexEntry.primaryKeys[pos],
-            );
-            if ((forward && cmpResult <= 0) || (!forward && cmpResult >= 0)) {
-              break;
-            }
-            pos += forward ? 1 : -1;
-          }
-          primkeySubPos = pos;
-        } else if (indexEntry !== undefined) {
-          primkeySubPos = forward ? 0 : indexEntry.primaryKeys.length - 1;
-        }
-
-        if (this.enableTracing) {
-          console.log("subPos=", primkeySubPos);
-          console.log("indexPos=", indexPos);
-        }
-
-        while (1) {
-          if (req.limit != 0 && numResults == req.limit) {
-            break;
-          }
-          if (indexPos === undefined) {
-            break;
-          }
-          if (!range.includes(indexPos)) {
-            break;
-          }
-          if (indexEntry === undefined) {
-            break;
-          }
-          if (
-            primkeySubPos < 0 ||
-            primkeySubPos >= indexEntry.primaryKeys.length
-          ) {
-            const res: any = forward
-              ? indexData.nextHigherPair(indexPos)
-              : indexData.nextLowerPair(indexPos);
-            if (res) {
-              indexPos = res[1].indexKey;
-              indexEntry = res[1];
-              primkeySubPos = forward ? 0 : indexEntry!.primaryKeys.length - 1;
-              continue;
-            } else {
-              break;
-            }
-          }
-          indexKeys.push(indexEntry.indexKey);
-          primaryKeys.push(indexEntry.primaryKeys[primkeySubPos]);
-          numResults++;
-          primkeySubPos += forward ? 1 : -1;
-        }
-      }
-
-      // Now we can collect the values based on the primary keys,
-      // if requested.
-      if (req.resultLevel === ResultLevel.Full) {
-        for (let i = 0; i < numResults; i++) {
-          const result = storeData.get(primaryKeys[i]);
-          if (!result) {
-            console.error("invariant violated during read");
-            console.error("request was", req);
-            throw Error("invariant violated during read");
-          }
-          values.push(result.value);
-        }
-      }
+      resp = getIndexRecords({
+        forward,
+        indexData,
+        storeData,
+        limit: req.limit,
+        unique,
+        range,
+        resultLevel: req.resultLevel,
+        advanceIndexKey: req.advanceIndexKey,
+        advancePrimaryKey: req.advancePrimaryKey,
+        lastIndexPosition: req.lastIndexPosition,
+        lastObjectStorePosition: req.lastObjectStorePosition,
+      });
     } else {
-      // only based on object store, no index involved, phew!
-      let storePos = req.lastObjectStorePosition;
-      if (storePos === undefined) {
-        storePos = forward ? range.lower : range.upper;
-      }
-
       if (req.advanceIndexKey !== undefined) {
         throw Error("unsupported request");
       }
-
-      storePos = furthestKey(forward, req.advancePrimaryKey, storePos);
-
-      if (storePos !== null && storePos !== undefined) {
-        // Advance store position if we are either still at the last returned
-        // store key, or if we are currently not on a key.
-        const storeEntry = storeData.get(storePos);
-        if (this.enableTracing) {
-          console.log("store entry:", storeEntry);
-        }
-        if (
-          !storeEntry ||
-          (req.lastObjectStorePosition !== undefined &&
-            compareKeys(req.lastObjectStorePosition, storePos) === 0)
-        ) {
-          storePos = storeData.nextHigherKey(storePos);
-        }
-      } else {
-        storePos = forward ? storeData.minKey() : storeData.maxKey();
-        if (this.enableTracing) {
-          console.log("setting starting store pos to", storePos);
-        }
-      }
-
-      while (1) {
-        if (req.limit != 0 && numResults == req.limit) {
-          break;
-        }
-        if (storePos === null || storePos === undefined) {
-          break;
-        }
-        if (!range.includes(storePos)) {
-          break;
-        }
-
-        const res = storeData.get(storePos);
-
-        if (res === undefined) {
-          break;
-        }
-
-        if (req.resultLevel >= ResultLevel.OnlyKeys) {
-          primaryKeys.push(structuredClone(storePos));
-        }
-
-        if (req.resultLevel >= ResultLevel.Full) {
-          values.push(structuredClone(res.value));
-        }
-
-        numResults++;
-        storePos = nextStoreKey(forward, storeData, storePos);
-      }
+      resp = getObjectStoreRecords({
+        forward,
+        storeData,
+        limit: req.limit,
+        range,
+        resultLevel: req.resultLevel,
+        advancePrimaryKey: req.advancePrimaryKey,
+        lastIndexPosition: req.lastIndexPosition,
+        lastObjectStorePosition: req.lastObjectStorePosition,
+      });
     }
     if (this.enableTracing) {
-      console.log(`TRACING: getRecords got ${numResults} results`);
+      console.log(`TRACING: getRecords got ${resp.count} results`);
     }
-    return {
-      count: numResults,
-      indexKeys:
-        req.resultLevel >= ResultLevel.OnlyKeys && haveIndex
-          ? indexKeys
-          : undefined,
-      primaryKeys:
-        req.resultLevel >= ResultLevel.OnlyKeys ? primaryKeys : undefined,
-      values: req.resultLevel >= ResultLevel.Full ? values : undefined,
-    };
+    return resp;
   }
 
   async storeRecord(
@@ -1586,21 +1351,20 @@ export class MemoryBackend implements Backend {
         if (indexProperties.unique) {
           throw new ConstraintError();
         } else {
-          const pred = (x: Key) => compareKeys(x, primaryKey) === 0;
-          if (existingRecord.primaryKeys.findIndex(pred) === -1) {
-            const newIndexRecord = {
-              indexKey: indexKey,
-              primaryKeys: [...existingRecord.primaryKeys, primaryKey].sort(
-                compareKeys,
-              ),
-            };
-            index.modifiedData = indexData.with(indexKey, newIndexRecord, true);
-          }
+          const newIndexRecord: IndexRecord = {
+            indexKey: indexKey,
+            primaryKeys: existingRecord.primaryKeys.with(primaryKey),
+          };
+          index.modifiedData = indexData.with(indexKey, newIndexRecord, true);
         }
       } else {
+        const primaryKeys: ISortedSetF<IDBValidKey> = new BTree(
+          [[primaryKey, undefined]],
+          compareKeys,
+        );
         const newIndexRecord: IndexRecord = {
           indexKey: indexKey,
-          primaryKeys: [primaryKey],
+          primaryKeys,
         };
         index.modifiedData = indexData.with(indexKey, newIndexRecord, true);
       }
@@ -1699,3 +1463,286 @@ export class MemoryBackend implements Backend {
     }
   }
 }
+
+function getIndexRecords(req: {
+  indexData: ISortedMapF<IDBValidKey, IndexRecord>;
+  storeData: ISortedMapF<IDBValidKey, ObjectStoreRecord>;
+  lastIndexPosition?: IDBValidKey;
+  forward: boolean;
+  unique: boolean;
+  range: IDBKeyRange;
+  lastObjectStorePosition?: IDBValidKey;
+  advancePrimaryKey?: IDBValidKey;
+  advanceIndexKey?: IDBValidKey;
+  limit: number;
+  resultLevel: ResultLevel;
+}): RecordGetResponse {
+  let numResults = 0;
+  const indexKeys: Key[] = [];
+  const primaryKeys: Key[] = [];
+  const values: Value[] = [];
+  const { unique, range, forward, indexData } = req;
+  let indexPos = req.lastIndexPosition;
+  let objectStorePos: IDBValidKey | undefined = undefined;
+  let indexEntry: IndexRecord | undefined = undefined;
+  const rangeStart = forward ? range.lower : range.upper;
+  const dataStart = forward ? indexData.minKey() : indexData.maxKey();
+  indexPos = furthestKey(forward, indexPos, rangeStart);
+  indexPos = furthestKey(forward, indexPos, dataStart);
+
+  function nextIndexEntry(): IndexRecord | undefined {
+    assertInvariant(indexPos != null);
+    const res: [IDBValidKey, IndexRecord] | undefined = forward
+      ? indexData.nextHigherPair(indexPos)
+      : indexData.nextLowerPair(indexPos);
+    if (res) {
+      indexEntry = res[1];
+      indexPos = indexEntry.indexKey;
+      return indexEntry;
+    } else {
+      indexEntry = undefined;
+      indexPos = undefined;
+      return undefined;
+    }
+  }
+
+  function packResult(): RecordGetResponse {
+    return {
+      count: numResults,
+      indexKeys:
+        req.resultLevel >= ResultLevel.OnlyKeys ? indexKeys : undefined,
+      primaryKeys:
+        req.resultLevel >= ResultLevel.OnlyKeys ? primaryKeys : undefined,
+      values: req.resultLevel >= ResultLevel.Full ? values : undefined,
+    };
+  }
+
+  if (indexPos == null) {
+    return packResult();
+  }
+
+  // Now we align at indexPos and after objectStorePos
+
+  indexEntry = indexData.get(indexPos);
+  if (!indexEntry) {
+    // We're not aligned to an index key, go to next index entry
+    nextIndexEntry();
+  }
+  if (indexEntry) {
+    objectStorePos = nextKey(
+      true,
+      indexEntry.primaryKeys,
+      req.lastObjectStorePosition,
+    );
+  }
+
+  if (
+    forward &&
+    range.lowerOpen &&
+    range.lower != null &&
+    compareKeys(range.lower, indexPos) === 0
+  ) {
+    const e = nextIndexEntry();
+    objectStorePos = e?.primaryKeys.minKey();
+  }
+
+  if (
+    !forward &&
+    range.upperOpen &&
+    range.upper != null &&
+    compareKeys(range.upper, indexPos) === 0
+  ) {
+    const e = nextIndexEntry();
+    objectStorePos = e?.primaryKeys.minKey();
+  }
+
+  if (
+    unique &&
+    indexPos != null &&
+    req.lastIndexPosition != null &&
+    compareKeys(indexPos, req.lastIndexPosition) === 0
+  ) {
+    const e = nextIndexEntry();
+    objectStorePos = e?.primaryKeys.minKey();
+  }
+
+  if (req.advancePrimaryKey) {
+    indexPos = furthestKey(forward, indexPos, req.advanceIndexKey);
+    if (indexPos) {
+      indexEntry = indexData.get(indexPos);
+      if (!indexEntry) {
+        nextIndexEntry();
+      }
+    }
+  }
+
+  // Use advancePrimaryKey if necessary
+  if (
+    req.advanceIndexKey != null &&
+    req.advancePrimaryKey &&
+    indexPos != null &&
+    indexEntry &&
+    compareKeys(indexPos, req.advanceIndexKey) == 0
+  ) {
+    if (
+      objectStorePos == null ||
+      compareKeys(req.advancePrimaryKey, objectStorePos) > 0
+    ) {
+      objectStorePos = nextKey(
+        true,
+        indexEntry.primaryKeys,
+        req.advancePrimaryKey,
+      );
+    }
+  }
+
+  while (1) {
+    if (indexPos === undefined) {
+      break;
+    }
+    if (req.limit != 0 && numResults == req.limit) {
+      break;
+    }
+    if (!range.includes(indexPos)) {
+      break;
+    }
+    if (indexEntry === undefined) {
+      break;
+    }
+    if (objectStorePos == null) {
+      // We don't have any more records with the current index key.
+      nextIndexEntry();
+      if (indexEntry) {
+        objectStorePos = indexEntry.primaryKeys.minKey();
+      }
+      continue;
+    }
+    indexKeys.push(indexEntry.indexKey);
+    primaryKeys.push(objectStorePos);
+    numResults++;
+    if (unique) {
+      objectStorePos = undefined;
+    } else {
+      objectStorePos = indexEntry.primaryKeys.nextHigherKey(objectStorePos);
+    }
+  }
+
+  // Now we can collect the values based on the primary keys,
+  // if requested.
+  if (req.resultLevel === ResultLevel.Full) {
+    for (let i = 0; i < numResults; i++) {
+      const result = req.storeData.get(primaryKeys[i]);
+      if (!result) {
+        console.error("invariant violated during read");
+        console.error("request was", req);
+        throw Error("invariant violated during read");
+      }
+      values.push(result.value);
+    }
+  }
+
+  return packResult();
+}
+
+function getObjectStoreRecords(req: {
+  storeData: ISortedMapF<IDBValidKey, ObjectStoreRecord>;
+  lastIndexPosition?: IDBValidKey;
+  forward: boolean;
+  range: IDBKeyRange;
+  lastObjectStorePosition?: IDBValidKey;
+  advancePrimaryKey?: IDBValidKey;
+  limit: number;
+  resultLevel: ResultLevel;
+}): RecordGetResponse {
+  let numResults = 0;
+  const indexKeys: Key[] = [];
+  const primaryKeys: Key[] = [];
+  const values: Value[] = [];
+  const { storeData, range, forward } = req;
+
+  function packResult(): RecordGetResponse {
+    return {
+      count: numResults,
+      indexKeys:
+        req.resultLevel >= ResultLevel.OnlyKeys ? indexKeys : undefined,
+      primaryKeys:
+        req.resultLevel >= ResultLevel.OnlyKeys ? primaryKeys : undefined,
+      values: req.resultLevel >= ResultLevel.Full ? values : undefined,
+    };
+  }
+
+  const rangeStart = forward ? range.lower : range.upper;
+  const dataStart = forward ? storeData.minKey() : storeData.maxKey();
+  let storePos = req.lastObjectStorePosition;
+  storePos = furthestKey(forward, storePos, rangeStart);
+  storePos = furthestKey(forward, storePos, dataStart);
+  storePos = furthestKey(forward, storePos, req.advancePrimaryKey);
+
+  if (storePos != null) {
+    // Advance store position if we are either still at the last returned
+    // store key, or if we are currently not on a key.
+    const storeEntry = storeData.get(storePos);
+    if (
+      !storeEntry ||
+      (req.lastObjectStorePosition != null &&
+        compareKeys(req.lastObjectStorePosition, storePos) === 0)
+    ) {
+      storePos = forward
+        ? storeData.nextHigherKey(storePos)
+        : storeData.nextLowerKey(storePos);
+    }
+  } else {
+    storePos = forward ? storeData.minKey() : storeData.maxKey();
+  }
+
+  if (
+    storePos != null &&
+    forward &&
+    range.lowerOpen &&
+    range.lower != null &&
+    compareKeys(range.lower, storePos) === 0
+  ) {
+    storePos = storeData.nextHigherKey(storePos);
+  }
+
+  if (
+    storePos != null &&
+    !forward &&
+    range.upperOpen &&
+    range.upper != null &&
+    compareKeys(range.upper, storePos) === 0
+  ) {
+    storePos = storeData.nextLowerKey(storePos);
+  }
+
+  while (1) {
+    if (req.limit != 0 && numResults == req.limit) {
+      break;
+    }
+    if (storePos === null || storePos === undefined) {
+      break;
+    }
+    if (!range.includes(storePos)) {
+      break;
+    }
+
+    const res = storeData.get(storePos);
+
+    if (res === undefined) {
+      break;
+    }
+
+    if (req.resultLevel >= ResultLevel.OnlyKeys) {
+      primaryKeys.push(structuredClone(storePos));
+    }
+
+    if (req.resultLevel >= ResultLevel.Full) {
+      values.push(structuredClone(res.value));
+    }
+
+    numResults++;
+    storePos = nextStoreKey(forward, storeData, storePos);
+  }
+
+  return packResult();
+}
diff --git a/packages/idb-bridge/src/backend-interface.ts b/packages/idb-bridge/src/backend-interface.ts
index ae43c9df7..1b9883d2b 100644
--- a/packages/idb-bridge/src/backend-interface.ts
+++ b/packages/idb-bridge/src/backend-interface.ts
@@ -103,7 +103,7 @@ export interface RecordGetRequest {
   advancePrimaryKey?: IDBValidKey;
   /**
    * Maximum number of results to return.
-   * If -1, return all available results
+   * If 0, return all available results
    */
   limit: number;
   resultLevel: ResultLevel;
diff --git a/packages/idb-bridge/src/bridge-idb.ts b/packages/idb-bridge/src/bridge-idb.ts
index f015d2a9f..9ea258fd2 100644
--- a/packages/idb-bridge/src/bridge-idb.ts
+++ b/packages/idb-bridge/src/bridge-idb.ts
@@ -1132,8 +1132,6 @@ export class BridgeIDBIndex implements IDBIndex {
       );
     }
 
-    BridgeIDBFactory.enableTracing && console.log("opening cursor on", this);
-
     this._confirmActiveTransaction();
 
     range = simplifyRange(range);
diff --git a/packages/idb-bridge/src/idb-wpt-ported/idbcursor-update-index.test.ts b/packages/idb-bridge/src/idb-wpt-ported/idbcursor-update-index.test.ts
index 363ef4afa..538665457 100644
--- a/packages/idb-bridge/src/idb-wpt-ported/idbcursor-update-index.test.ts
+++ b/packages/idb-bridge/src/idb-wpt-ported/idbcursor-update-index.test.ts
@@ -1,7 +1,5 @@
 import test from "ava";
 import { BridgeIDBCursor, BridgeIDBKeyRange } from "..";
-import { BridgeIDBCursorWithValue } from "../bridge-idb";
-import { IDBDatabase } from "../idbtypes";
 import {
   createDatabase,
   createdb,
diff --git a/packages/idb-bridge/src/index.ts b/packages/idb-bridge/src/index.ts
index fa9edaea6..0abbf1056 100644
--- a/packages/idb-bridge/src/index.ts
+++ b/packages/idb-bridge/src/index.ts
@@ -16,7 +16,6 @@ import { Listener } from "./util/FakeEventTarget";
 import {
   DatabaseDump,
   ObjectStoreDump,
-  IndexDump,
   IndexRecord,
   ObjectStoreRecord,
   MemoryBackendDump,
@@ -64,7 +63,6 @@ export type {
   RequestObj,
   DatabaseDump,
   ObjectStoreDump,
-  IndexDump,
   IndexRecord,
   ObjectStoreRecord,
   IndexProperties,
diff --git a/packages/idb-bridge/src/tree/b+tree.ts b/packages/idb-bridge/src/tree/b+tree.ts
index abe65e355..76dd79dda 100644
--- a/packages/idb-bridge/src/tree/b+tree.ts
+++ b/packages/idb-bridge/src/tree/b+tree.ts
@@ -1,30 +1,6 @@
-/*
-Copyright (c) 2018 David Piepgrass
-
-Permission is hereby granted, free of charge, to any person obtaining a copy
-of this software and associated documentation files (the "Software"), to deal
-in the Software without restriction, including without limitation the rights
-to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
-copies of the Software, and to permit persons to whom the Software is
-furnished to do so, subject to the following conditions:
-
-The above copyright notice and this permission notice shall be included in all
-copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
-AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
-LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
-OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
-SOFTWARE.
-
-SPDX-License-Identifier: MIT
-*/
-
-// Original repository: https://github.com/qwertie/btree-typescript
-
+// B+ tree by David Piepgrass. License: MIT
 import { ISortedMap, ISortedMapF } from "./interfaces";
+
 export type {
   ISetSource,
   ISetSink,
@@ -71,17 +47,108 @@ type index = number;
 //   - Objects can be used like arrays (e.g. have length property) but are slower
 //   - V8 source (NewElementsCapacity in src/objects.h): arrays grow by 50% + 16 elements
 
-/** Compares two numbers, strings, arrays of numbers/strings, Dates,
- *  or objects that have a valueOf() method returning a number or string.
- *  Optimized for numbers. Returns 1 if a>b, -1 if a<b, and 0 if a===b.
+/**
+ * Types that BTree supports by default
+ */
+export type DefaultComparable =
+  | number
+  | string
+  | Date
+  | boolean
+  | null
+  | undefined
+  | (number | string)[]
+  | {
+      valueOf: () =>
+        | number
+        | string
+        | Date
+        | boolean
+        | null
+        | undefined
+        | (number | string)[];
+    };
+
+/**
+ * Compares DefaultComparables to form a strict partial ordering.
+ *
+ * Handles +/-0 and NaN like Map: NaN is equal to NaN, and -0 is equal to +0.
+ *
+ * Arrays are compared using '<' and '>', which may cause unexpected equality:
+ * for example [1] will be considered equal to ['1'].
+ *
+ * Two objects with equal valueOf compare the same, but compare unequal to
+ * primitives that have the same value.
  */
-export function defaultComparator(a: any, b: any) {
-  var c = a - b;
-  if (c === c) return c; // a & b are number
-  // General case (c is NaN): string / arrays / Date / incomparable things
-  if (a) a = a.valueOf();
-  if (b) b = b.valueOf();
-  return a < b ? -1 : a > b ? 1 : a == b ? 0 : c;
+export function defaultComparator(
+  a: DefaultComparable,
+  b: DefaultComparable,
+): number {
+  // Special case finite numbers first for performance.
+  // Note that the trick of using 'a - b' and checking for NaN to detect non-numbers
+  // does not work if the strings are numeric (ex: "5"). This would leading most
+  // comparison functions using that approach to fail to have transitivity.
+  if (Number.isFinite(a as any) && Number.isFinite(b as any)) {
+    return (a as number) - (b as number);
+  }
+
+  // The default < and > operators are not totally ordered. To allow types to be mixed
+  // in a single collection, compare types and order values of different types by type.
+  let ta = typeof a;
+  let tb = typeof b;
+  if (ta !== tb) {
+    return ta < tb ? -1 : 1;
+  }
+
+  if (ta === "object") {
+    // standardized JavaScript bug: null is not an object, but typeof says it is
+    if (a === null) return b === null ? 0 : -1;
+    else if (b === null) return 1;
+
+    a = a!.valueOf() as DefaultComparable;
+    b = b!.valueOf() as DefaultComparable;
+    ta = typeof a;
+    tb = typeof b;
+    // Deal with the two valueOf()s producing different types
+    if (ta !== tb) {
+      return ta < tb ? -1 : 1;
+    }
+  }
+
+  // a and b are now the same type, and will be a number, string or array
+  // (which we assume holds numbers or strings), or something unsupported.
+  if (a! < b!) return -1;
+  if (a! > b!) return 1;
+  if (a === b) return 0;
+
+  // Order NaN less than other numbers
+  if (Number.isNaN(a as any)) return Number.isNaN(b as any) ? 0 : -1;
+  else if (Number.isNaN(b as any)) return 1;
+  // This could be two objects (e.g. [7] and ['7']) that aren't ordered
+  return Array.isArray(a) ? 0 : Number.NaN;
+}
+
+/**
+ * Compares items using the < and > operators. This function is probably slightly
+ * faster than the defaultComparator for Dates and strings, but has not been benchmarked.
+ * Unlike defaultComparator, this comparator doesn't support mixed types correctly,
+ * i.e. use it with `BTree<string>` or `BTree<number>` but not `BTree<string|number>`.
+ *
+ * NaN is not supported.
+ *
+ * Note: null is treated like 0 when compared with numbers or Date, but in general
+ *   null is not ordered with respect to strings (neither greater nor less), and
+ *   undefined is not ordered with other types.
+ */
+export function simpleComparator(a: string, b: string): number;
+export function simpleComparator(a: number | null, b: number | null): number;
+export function simpleComparator(a: Date | null, b: Date | null): number;
+export function simpleComparator(
+  a: (number | string)[],
+  b: (number | string)[],
+): number;
+export function simpleComparator(a: any, b: any): number {
+  return a > b ? 1 : a < b ? -1 : 0;
 }
 
 /**
@@ -153,12 +220,17 @@ export default class BTree<K = any, V = any>
   private _root: BNode<K, V> = EmptyLeaf as BNode<K, V>;
   _size: number = 0;
   _maxNodeSize: number;
+
+  /**
+   * provides a total order over keys (and a strict partial order over the type K)
+   * @returns a negative value if a < b, 0 if a === b and a positive value if a > b
+   */
   _compare: (a: K, b: K) => number;
 
   /**
    * Initializes an empty B+ tree.
    * @param compare Custom function to compare pairs of elements in the tree.
-   *   This is not required for numbers, strings and arrays of numbers/strings.
+   *   If not specified, defaultComparator will be used which is valid as long as K extends DefaultComparable.
    * @param entries A set of key-value pairs to initialize the tree
    * @param maxNodeSize Branching factor (maximum items or children per node)
    *   Must be in range 4..256. If undefined or <4 then default is used; if >256 then 256.
@@ -169,11 +241,13 @@ export default class BTree<K = any, V = any>
     maxNodeSize?: number,
   ) {
     this._maxNodeSize = maxNodeSize! >= 4 ? Math.min(maxNodeSize!, 256) : 32;
-    this._compare = compare || defaultComparator;
+    this._compare =
+      compare || ((defaultComparator as any) as (a: K, b: K) => number);
     if (entries) this.setPairs(entries);
   }
 
-  // ES6 Map<K,V> methods ///////////////////////////////////////////////////
+  /////////////////////////////////////////////////////////////////////////////
+  // ES6 Map<K,V> methods /////////////////////////////////////////////////////
 
   /** Gets the number of key-value pairs in the tree. */
   get size() {
@@ -292,7 +366,8 @@ export default class BTree<K = any, V = any>
     return this.editRange(key, key, true, DeleteRange) !== 0;
   }
 
-  // Clone-mutators /////////////////////////////////////////////////////////
+  /////////////////////////////////////////////////////////////////////////////
+  // Clone-mutators ///////////////////////////////////////////////////////////
 
   /** Returns a copy of the tree with the specified key set (the value is undefined). */
   with(key: K): BTree<K, V | undefined>;
@@ -437,7 +512,8 @@ export default class BTree<K = any, V = any>
     return p;
   }
 
-  // Iterator methods ///////////////////////////////////////////////////////
+  /////////////////////////////////////////////////////////////////////////////
+  // Iterator methods /////////////////////////////////////////////////////////
 
   /** Returns an iterator that provides items in order (ascending order if
    *  the collection's comparator uses ascending order, as is the default.)
@@ -500,7 +576,7 @@ export default class BTree<K = any, V = any>
 
   /** Returns an iterator that provides items in reversed order.
    *  @param highestKey Key at which to start iterating, or undefined to
-   *         start at minKey(). If the specified key doesn't exist then iteration
+   *         start at maxKey(). If the specified key doesn't exist then iteration
    *         starts at the next lower key (according to the comparator).
    *  @param reusedArray Optional array used repeatedly to store key-value
    *         pairs, to avoid creating a new array on every iteration.
@@ -512,13 +588,21 @@ export default class BTree<K = any, V = any>
     reusedArray?: (K | V)[],
     skipHighest?: boolean,
   ): IterableIterator<[K, V]> {
-    if ((highestKey = highestKey || this.maxKey()) === undefined)
-      return iterator<[K, V]>(); // collection is empty
+    if (highestKey === undefined) {
+      highestKey = this.maxKey();
+      skipHighest = undefined;
+      if (highestKey === undefined) return iterator<[K, V]>(); // collection is empty
+    }
     var { nodequeue, nodeindex, leaf } =
       this.findPath(highestKey) || this.findPath(this.maxKey())!;
     check(!nodequeue[0] || leaf === nodequeue[0][nodeindex[0]], "wat!");
     var i = leaf.indexOf(highestKey, 0, this._compare);
-    if (!(skipHighest || this._compare(leaf.keys[i], highestKey) > 0)) i++;
+    if (
+      !skipHighest &&
+      i < leaf.keys.length &&
+      this._compare(leaf.keys[i], highestKey) <= 0
+    )
+      i++;
     var state = reusedArray !== undefined ? 1 : 0;
 
     return iterator<[K, V]>(() => {
@@ -596,6 +680,319 @@ export default class BTree<K = any, V = any>
     return { nodequeue, nodeindex, leaf: nextnode };
   }
 
+  /**
+   * Computes the differences between `this` and `other`.
+   * For efficiency, the diff is returned via invocations of supplied handlers.
+   * The computation is optimized for the case in which the two trees have large amounts
+   * of shared data (obtained by calling the `clone` or `with` APIs) and will avoid
+   * any iteration of shared state.
+   * The handlers can cause computation to early exit by returning {break: R}.
+   * Neither of the collections should be changed during the comparison process (in your callbacks), as this method assumes they will not be mutated.
+   * @param other The tree to compute a diff against.
+   * @param onlyThis Callback invoked for all keys only present in `this`.
+   * @param onlyOther Callback invoked for all keys only present in `other`.
+   * @param different Callback invoked for all keys with differing values.
+   */
+  diffAgainst<R>(
+    other: BTree<K, V>,
+    onlyThis?: (k: K, v: V) => { break?: R } | void,
+    onlyOther?: (k: K, v: V) => { break?: R } | void,
+    different?: (k: K, vThis: V, vOther: V) => { break?: R } | void,
+  ): R | undefined {
+    if (other._compare !== this._compare) {
+      throw new Error("Tree comparators are not the same.");
+    }
+
+    if (this.isEmpty || other.isEmpty) {
+      if (this.isEmpty && other.isEmpty) return undefined;
+      // If one tree is empty, everything will be an onlyThis/onlyOther.
+      if (this.isEmpty)
+        return onlyOther === undefined
+          ? undefined
+          : BTree.stepToEnd(BTree.makeDiffCursor(other), onlyOther);
+      return onlyThis === undefined
+        ? undefined
+        : BTree.stepToEnd(BTree.makeDiffCursor(this), onlyThis);
+    }
+
+    // Cursor-based diff algorithm is as follows:
+    // - Until neither cursor has navigated to the end of the tree, do the following:
+    //  - If the `this` cursor is "behind" the `other` cursor (strictly <, via compare), advance it.
+    //  - Otherwise, advance the `other` cursor.
+    //  - Any time a cursor is stepped, perform the following:
+    //    - If either cursor points to a key/value pair:
+    //      - If thisCursor === otherCursor and the values differ, it is a Different.
+    //      - If thisCursor > otherCursor and otherCursor is at a key/value pair, it is an OnlyOther.
+    //      - If thisCursor < otherCursor and thisCursor is at a key/value pair, it is an OnlyThis as long as the most recent
+    //        cursor step was *not* otherCursor advancing from a tie. The extra condition avoids erroneous OnlyOther calls
+    //        that would occur due to otherCursor being the "leader".
+    //    - Otherwise, if both cursors point to nodes, compare them. If they are equal by reference (shared), skip
+    //      both cursors to the next node in the walk.
+    // - Once one cursor has finished stepping, any remaining steps (if any) are taken and key/value pairs are logged
+    //   as OnlyOther (if otherCursor is stepping) or OnlyThis (if thisCursor is stepping).
+    // This algorithm gives the critical guarantee that all locations (both nodes and key/value pairs) in both trees that
+    // are identical by value (and possibly by reference) will be visited *at the same time* by the cursors.
+    // This removes the possibility of emitting incorrect diffs, as well as allowing for skipping shared nodes.
+    const { _compare } = this;
+    const thisCursor = BTree.makeDiffCursor(this);
+    const otherCursor = BTree.makeDiffCursor(other);
+    // It doesn't matter how thisSteppedLast is initialized.
+    // Step order is only used when either cursor is at a leaf, and cursors always start at a node.
+    let thisSuccess = true,
+      otherSuccess = true,
+      prevCursorOrder = BTree.compare(thisCursor, otherCursor, _compare);
+    while (thisSuccess && otherSuccess) {
+      const cursorOrder = BTree.compare(thisCursor, otherCursor, _compare);
+      const {
+        leaf: thisLeaf,
+        internalSpine: thisInternalSpine,
+        levelIndices: thisLevelIndices,
+      } = thisCursor;
+      const {
+        leaf: otherLeaf,
+        internalSpine: otherInternalSpine,
+        levelIndices: otherLevelIndices,
+      } = otherCursor;
+      if (thisLeaf || otherLeaf) {
+        // If the cursors were at the same location last step, then there is no work to be done.
+        if (prevCursorOrder !== 0) {
+          if (cursorOrder === 0) {
+            if (thisLeaf && otherLeaf && different) {
+              // Equal keys, check for modifications
+              const valThis =
+                thisLeaf.values[thisLevelIndices[thisLevelIndices.length - 1]];
+              const valOther =
+                otherLeaf.values[
+                  otherLevelIndices[otherLevelIndices.length - 1]
+                ];
+              if (!Object.is(valThis, valOther)) {
+                const result = different(
+                  thisCursor.currentKey,
+                  valThis,
+                  valOther,
+                );
+                if (result && result.break) return result.break;
+              }
+            }
+          } else if (cursorOrder > 0) {
+            // If this is the case, we know that either:
+            // 1. otherCursor stepped last from a starting position that trailed thisCursor, and is still behind, or
+            // 2. thisCursor stepped last and leapfrogged otherCursor
+            // Either of these cases is an "only other"
+            if (otherLeaf && onlyOther) {
+              const otherVal =
+                otherLeaf.values[
+                  otherLevelIndices[otherLevelIndices.length - 1]
+                ];
+              const result = onlyOther(otherCursor.currentKey, otherVal);
+              if (result && result.break) return result.break;
+            }
+          } else if (onlyThis) {
+            if (thisLeaf && prevCursorOrder !== 0) {
+              const valThis =
+                thisLeaf.values[thisLevelIndices[thisLevelIndices.length - 1]];
+              const result = onlyThis(thisCursor.currentKey, valThis);
+              if (result && result.break) return result.break;
+            }
+          }
+        }
+      } else if (!thisLeaf && !otherLeaf && cursorOrder === 0) {
+        const lastThis = thisInternalSpine.length - 1;
+        const lastOther = otherInternalSpine.length - 1;
+        const nodeThis =
+          thisInternalSpine[lastThis][thisLevelIndices[lastThis]];
+        const nodeOther =
+          otherInternalSpine[lastOther][otherLevelIndices[lastOther]];
+        if (nodeOther === nodeThis) {
+          prevCursorOrder = 0;
+          thisSuccess = BTree.step(thisCursor, true);
+          otherSuccess = BTree.step(otherCursor, true);
+          continue;
+        }
+      }
+      prevCursorOrder = cursorOrder;
+      if (cursorOrder < 0) {
+        thisSuccess = BTree.step(thisCursor);
+      } else {
+        otherSuccess = BTree.step(otherCursor);
+      }
+    }
+
+    if (thisSuccess && onlyThis)
+      return BTree.finishCursorWalk(
+        thisCursor,
+        otherCursor,
+        _compare,
+        onlyThis,
+      );
+    if (otherSuccess && onlyOther)
+      return BTree.finishCursorWalk(
+        otherCursor,
+        thisCursor,
+        _compare,
+        onlyOther,
+      );
+  }
+
+  ///////////////////////////////////////////////////////////////////////////
+  // Helper methods for diffAgainst /////////////////////////////////////////
+
+  private static finishCursorWalk<K, V, R>(
+    cursor: DiffCursor<K, V>,
+    cursorFinished: DiffCursor<K, V>,
+    compareKeys: (a: K, b: K) => number,
+    callback: (k: K, v: V) => { break?: R } | void,
+  ): R | undefined {
+    const compared = BTree.compare(cursor, cursorFinished, compareKeys);
+    if (compared === 0) {
+      if (!BTree.step(cursor)) return undefined;
+    } else if (compared < 0) {
+      check(false, "cursor walk terminated early");
+    }
+    return BTree.stepToEnd(cursor, callback);
+  }
+
+  private static stepToEnd<K, V, R>(
+    cursor: DiffCursor<K, V>,
+    callback: (k: K, v: V) => { break?: R } | void,
+  ): R | undefined {
+    let canStep: boolean = true;
+    while (canStep) {
+      const { leaf, levelIndices, currentKey } = cursor;
+      if (leaf) {
+        const value = leaf.values[levelIndices[levelIndices.length - 1]];
+        const result = callback(currentKey, value);
+        if (result && result.break) return result.break;
+      }
+      canStep = BTree.step(cursor);
+    }
+    return undefined;
+  }
+
+  private static makeDiffCursor<K, V>(tree: BTree<K, V>): DiffCursor<K, V> {
+    const { _root, height } = tree;
+    return {
+      height: height,
+      internalSpine: [[_root]],
+      levelIndices: [0],
+      leaf: undefined,
+      currentKey: _root.maxKey(),
+    };
+  }
+
+  /**
+   * Advances the cursor to the next step in the walk of its tree.
+   * Cursors are walked backwards in sort order, as this allows them to leverage maxKey() in order to be compared in O(1).
+   * @param cursor The cursor to step
+   * @param stepToNode If true, the cursor will be advanced to the next node (skipping values)
+   * @returns true if the step was completed and false if the step would have caused the cursor to move beyond the end of the tree.
+   */
+  private static step<K, V>(
+    cursor: DiffCursor<K, V>,
+    stepToNode?: boolean,
+  ): boolean {
+    const { internalSpine, levelIndices, leaf } = cursor;
+    if (stepToNode === true || leaf) {
+      const levelsLength = levelIndices.length;
+      // Step to the next node only if:
+      // - We are explicitly directed to via stepToNode, or
+      // - There are no key/value pairs left to step to in this leaf
+      if (stepToNode === true || levelIndices[levelsLength - 1] === 0) {
+        const spineLength = internalSpine.length;
+        // Root is leaf
+        if (spineLength === 0) return false;
+        // Walk back up the tree until we find a new subtree to descend into
+        const nodeLevelIndex = spineLength - 1;
+        let levelIndexWalkBack = nodeLevelIndex;
+        while (levelIndexWalkBack >= 0) {
+          if (levelIndices[levelIndexWalkBack] > 0) {
+            if (levelIndexWalkBack < levelsLength - 1) {
+              // Remove leaf state from cursor
+              cursor.leaf = undefined;
+              levelIndices.pop();
+            }
+            // If we walked upwards past any internal node, slice them out
+            if (levelIndexWalkBack < nodeLevelIndex)
+              cursor.internalSpine = internalSpine.slice(
+                0,
+                levelIndexWalkBack + 1,
+              );
+            // Move to new internal node
+            cursor.currentKey = internalSpine[levelIndexWalkBack][
+              --levelIndices[levelIndexWalkBack]
+            ].maxKey();
+            return true;
+          }
+          levelIndexWalkBack--;
+        }
+        // Cursor is in the far left leaf of the tree, no more nodes to enumerate
+        return false;
+      } else {
+        // Move to new leaf value
+        const valueIndex = --levelIndices[levelsLength - 1];
+        cursor.currentKey = ((leaf as unknown) as BNode<K, V>).keys[valueIndex];
+        return true;
+      }
+    } else {
+      // Cursor does not point to a value in a leaf, so move downwards
+      const nextLevel = internalSpine.length;
+      const currentLevel = nextLevel - 1;
+      const node = internalSpine[currentLevel][levelIndices[currentLevel]];
+      if (node.isLeaf) {
+        // Entering into a leaf. Set the cursor to point at the last key/value pair.
+        cursor.leaf = node;
+        const valueIndex = (levelIndices[nextLevel] = node.values.length - 1);
+        cursor.currentKey = node.keys[valueIndex];
+      } else {
+        const children = (node as BNodeInternal<K, V>).children;
+        internalSpine[nextLevel] = children;
+        const childIndex = children.length - 1;
+        levelIndices[nextLevel] = childIndex;
+        cursor.currentKey = children[childIndex].maxKey();
+      }
+      return true;
+    }
+  }
+
+  /**
+   * Compares the two cursors. Returns a value indicating which cursor is ahead in a walk.
+   * Note that cursors are advanced in reverse sorting order.
+   */
+  private static compare<K, V>(
+    cursorA: DiffCursor<K, V>,
+    cursorB: DiffCursor<K, V>,
+    compareKeys: (a: K, b: K) => number,
+  ): number {
+    const {
+      height: heightA,
+      currentKey: currentKeyA,
+      levelIndices: levelIndicesA,
+    } = cursorA;
+    const {
+      height: heightB,
+      currentKey: currentKeyB,
+      levelIndices: levelIndicesB,
+    } = cursorB;
+    // Reverse the comparison order, as cursors are advanced in reverse sorting order
+    const keyComparison = compareKeys(currentKeyB, currentKeyA);
+    if (keyComparison !== 0) {
+      return keyComparison;
+    }
+
+    // Normalize depth values relative to the shortest tree.
+    // This ensures that concurrent cursor walks of trees of differing heights can reliably land on shared nodes at the same time.
+    // To accomplish this, a cursor that is on an internal node at depth D1 with maxKey X is considered "behind" a cursor on an
+    // internal node at depth D2 with maxKey Y, when D1 < D2. Thus, always walking the cursor that is "behind" will allow the cursor
+    // at shallower depth (but equal maxKey) to "catch up" and land on shared nodes.
+    const heightMin = heightA < heightB ? heightA : heightB;
+    const depthANormalized = levelIndicesA.length - (heightA - heightMin);
+    const depthBNormalized = levelIndicesB.length - (heightB - heightMin);
+    return depthANormalized - depthBNormalized;
+  }
+
+  // End of helper methods for diffAgainst //////////////////////////////////
+  ///////////////////////////////////////////////////////////////////////////
+
   /** Returns a new iterator for iterating the keys of each pair in ascending order.
    *  @param firstKey: Minimum key to include in the output. */
   keys(firstKey?: K): IterableIterator<K> {
@@ -618,7 +1015,8 @@ export default class BTree<K = any, V = any>
     });
   }
 
-  // Additional methods /////////////////////////////////////////////////////
+  /////////////////////////////////////////////////////////////////////////////
+  // Additional methods ///////////////////////////////////////////////////////
 
   /** Returns the maximum number of children/values before nodes will split. */
   get maxNodeSize() {
@@ -714,30 +1112,90 @@ export default class BTree<K = any, V = any>
     return this.set(key, value, false);
   }
 
-  /** Returns the next pair whose key is larger than the specified key (or undefined if there is none) */
-  nextHigherPair(key: K): [K, V] | undefined {
-    var it = this.entries(key, ReusedArray);
-    var r = it.next();
-    if (!r.done && this._compare(r.value[0], key) <= 0) r = it.next();
-    return r.value;
+  /** Returns the next pair whose key is larger than the specified key (or undefined if there is none).
+   * If key === undefined, this function returns the lowest pair.
+   * @param key The key to search for.
+   * @param reusedArray Optional array used repeatedly to store key-value pairs, to
+   * avoid creating a new array on every iteration.
+   */
+  nextHigherPair(key: K | undefined, reusedArray?: [K, V]): [K, V] | undefined {
+    reusedArray = reusedArray || (([] as unknown) as [K, V]);
+    if (key === undefined) {
+      return this._root.minPair(reusedArray);
+    }
+    return this._root.getPairOrNextHigher(
+      key,
+      this._compare,
+      false,
+      reusedArray,
+    );
   }
 
-  /** Returns the next key larger than the specified key (or undefined if there is none) */
-  nextHigherKey(key: K): K | undefined {
-    var p = this.nextHigherPair(key);
-    return p ? p[0] : p;
+  /** Returns the next key larger than the specified key, or undefined if there is none.
+   *  Also, nextHigherKey(undefined) returns the lowest key.
+   */
+  nextHigherKey(key: K | undefined): K | undefined {
+    var p = this.nextHigherPair(key, ReusedArray as [K, V]);
+    return p && p[0];
   }
 
-  /** Returns the next pair whose key is smaller than the specified key (or undefined if there is none) */
-  nextLowerPair(key: K): [K, V] | undefined {
-    var it = this.entriesReversed(key, ReusedArray, true);
-    return it.next().value;
+  /** Returns the next pair whose key is smaller than the specified key (or undefined if there is none).
+   *  If key === undefined, this function returns the highest pair.
+   * @param key The key to search for.
+   * @param reusedArray Optional array used repeatedly to store key-value pairs, to
+   *        avoid creating a new array each time you call this method.
+   */
+  nextLowerPair(key: K | undefined, reusedArray?: [K, V]): [K, V] | undefined {
+    reusedArray = reusedArray || (([] as unknown) as [K, V]);
+    if (key === undefined) {
+      return this._root.maxPair(reusedArray);
+    }
+    return this._root.getPairOrNextLower(
+      key,
+      this._compare,
+      false,
+      reusedArray,
+    );
   }
 
-  /** Returns the next key smaller than the specified key (or undefined if there is none) */
-  nextLowerKey(key: K): K | undefined {
-    var p = this.nextLowerPair(key);
-    return p ? p[0] : p;
+  /** Returns the next key smaller than the specified key, or undefined if there is none.
+   *  Also, nextLowerKey(undefined) returns the highest key.
+   */
+  nextLowerKey(key: K | undefined): K | undefined {
+    var p = this.nextLowerPair(key, ReusedArray as [K, V]);
+    return p && p[0];
+  }
+
+  /** Returns the key-value pair associated with the supplied key if it exists
+   *  or the pair associated with the next lower pair otherwise. If there is no
+   *  next lower pair, undefined is returned.
+   * @param key The key to search for.
+   * @param reusedArray Optional array used repeatedly to store key-value pairs, to
+   *        avoid creating a new array each time you call this method.
+   * */
+  getPairOrNextLower(key: K, reusedArray?: [K, V]): [K, V] | undefined {
+    return this._root.getPairOrNextLower(
+      key,
+      this._compare,
+      true,
+      reusedArray || (([] as unknown) as [K, V]),
+    );
+  }
+
+  /** Returns the key-value pair associated with the supplied key if it exists
+   *  or the pair associated with the next lower pair otherwise. If there is no
+   *  next lower pair, undefined is returned.
+   * @param key The key to search for.
+   * @param reusedArray Optional array used repeatedly to store key-value pairs, to
+   *        avoid creating a new array each time you call this method.
+   * */
+  getPairOrNextHigher(key: K, reusedArray?: [K, V]): [K, V] | undefined {
+    return this._root.getPairOrNextHigher(
+      key,
+      this._compare,
+      true,
+      reusedArray || (([] as unknown) as [K, V]),
+    );
   }
 
   /** Edits the value associated with a key in the tree, if it already exists.
@@ -836,7 +1294,7 @@ export default class BTree<K = any, V = any>
   /**
    * Scans and potentially modifies values for a subsequence of keys.
    * Note: the callback `onFound` should ideally be a pure function.
-   *   Specifically, it must not insert items, call clone(), or change
+   *   Specfically, it must not insert items, call clone(), or change
    *   the collection except via return value; out-of-band editing may
    *   cause an exception or may cause incorrect data to be sent to
    *   the callback (duplicate or missed items). It must not cause a
@@ -926,9 +1384,15 @@ export default class BTree<K = any, V = any>
   /** Gets the height of the tree: the number of internal nodes between the
    *  BTree object and its leaf nodes (zero if there are no internal nodes). */
   get height(): number {
-    for (var node = this._root, h = -1; node != null; h++)
-      node = (node as any).children;
-    return h;
+    let node: BNode<K, V> | undefined = this._root;
+    let height = -1;
+    while (node) {
+      height++;
+      node = node.isLeaf
+        ? undefined
+        : ((node as unknown) as BNodeInternal<K, V>).children[0];
+    }
+    return height;
   }
 
   /** Makes the object read-only to ensure it is not accidentally modified.
@@ -948,7 +1412,8 @@ export default class BTree<K = any, V = any>
 
   /** Ensures mutations are allowed, reversing the effect of freeze(). */
   unfreeze() {
-    // @ts-ignore
+    // @ts-ignore "The operand of a 'delete' operator must be optional."
+    //            (wrong: delete does not affect the prototype.)
     delete this.clear;
     // @ts-ignore
     delete this.set;
@@ -967,7 +1432,7 @@ export default class BTree<K = any, V = any>
    *  skips the most expensive test - whether all keys are sorted - but it
    *  does check that maxKey() of the children of internal nodes are sorted. */
   checkValid() {
-    var size = this._root.checkValid(0, this);
+    var size = this._root.checkValid(0, this, 0);
     check(
       size === this.size,
       "size mismatch: counted ",
@@ -987,10 +1452,7 @@ if (Symbol && Symbol.iterator)
 (BTree as any).prototype.add = BTree.prototype.set;
 
 function iterator<T>(
-  next: () => { done?: boolean; value?: T } = () => ({
-    done: true,
-    value: undefined,
-  }),
+  next: () => IteratorResult<T> = () => ({ done: true, value: undefined }),
 ): IterableIterator<T> {
   var result: any = { next };
   if (Symbol && Symbol.iterator)
@@ -1016,6 +1478,7 @@ class BNode<K, V> {
     this.isShared = undefined;
   }
 
+  ///////////////////////////////////////////////////////////////////////////
   // Shared methods /////////////////////////////////////////////////////////
 
   maxKey() {
@@ -1025,7 +1488,6 @@ class BNode<K, V> {
   // If key not found, returns i^failXor where i is the insertion index.
   // Callers that don't care whether there was a match will set failXor=0.
   indexOf(key: K, failXor: number, cmp: (a: K, b: K) => number): index {
-    // TODO: benchmark multiple search strategies
     const keys = this.keys;
     var lo = 0,
       hi = keys.length,
@@ -1094,12 +1556,28 @@ class BNode<K, V> {
     return c === 0 ? i : i ^ failXor;*/
   }
 
+  /////////////////////////////////////////////////////////////////////////////
   // Leaf Node: misc //////////////////////////////////////////////////////////
 
-  minKey() {
+  minKey(): K | undefined {
     return this.keys[0];
   }
 
+  minPair(reusedArray: [K, V]): [K, V] | undefined {
+    if (this.keys.length === 0) return undefined;
+    reusedArray[0] = this.keys[0];
+    reusedArray[1] = this.values[0];
+    return reusedArray;
+  }
+
+  maxPair(reusedArray: [K, V]): [K, V] | undefined {
+    if (this.keys.length === 0) return undefined;
+    const lastIndex = this.keys.length - 1;
+    reusedArray[0] = this.keys[lastIndex];
+    reusedArray[1] = this.values[lastIndex];
+    return reusedArray;
+  }
+
   clone(): BNode<K, V> {
     var v = this.values;
     return new BNode<K, V>(
@@ -1117,7 +1595,40 @@ class BNode<K, V> {
     return i < 0 ? defaultValue : this.values[i];
   }
 
-  checkValid(depth: number, tree: BTree<K, V>): number {
+  getPairOrNextLower(
+    key: K,
+    compare: (a: K, b: K) => number,
+    inclusive: boolean,
+    reusedArray: [K, V],
+  ): [K, V] | undefined {
+    var i = this.indexOf(key, -1, compare);
+    const indexOrLower = i < 0 ? ~i - 1 : inclusive ? i : i - 1;
+    if (indexOrLower >= 0) {
+      reusedArray[0] = this.keys[indexOrLower];
+      reusedArray[1] = this.values[indexOrLower];
+      return reusedArray;
+    }
+    return undefined;
+  }
+
+  getPairOrNextHigher(
+    key: K,
+    compare: (a: K, b: K) => number,
+    inclusive: boolean,
+    reusedArray: [K, V],
+  ): [K, V] | undefined {
+    var i = this.indexOf(key, -1, compare);
+    const indexOrLower = i < 0 ? ~i : inclusive ? i : i + 1;
+    const keys = this.keys;
+    if (indexOrLower < keys.length) {
+      reusedArray[0] = keys[indexOrLower];
+      reusedArray[1] = this.values[indexOrLower];
+      return reusedArray;
+    }
+    return undefined;
+  }
+
+  checkValid(depth: number, tree: BTree<K, V>, baseIndex: number): number {
     var kL = this.keys.length,
       vL = this.values.length;
     check(
@@ -1127,16 +1638,25 @@ class BNode<K, V> {
       "with lengths",
       kL,
       vL,
+      "and baseIndex",
+      baseIndex,
     );
     // Note: we don't check for "node too small" because sometimes a node
     // can legitimately have size 1. This occurs if there is a batch
     // deletion, leaving a node of size 1, and the siblings are full so
     // it can't be merged with adjacent nodes. However, the parent will
     // verify that the average node size is at least half of the maximum.
-    check(depth == 0 || kL > 0, "empty leaf at depth", depth);
+    check(
+      depth == 0 || kL > 0,
+      "empty leaf at depth",
+      depth,
+      "and baseIndex",
+      baseIndex,
+    );
     return kL;
   }
 
+  /////////////////////////////////////////////////////////////////////////////
   // Leaf Node: set & node splitting //////////////////////////////////////////
 
   set(
@@ -1233,6 +1753,7 @@ class BNode<K, V> {
     return new BNode<K, V>(keys, values);
   }
 
+  /////////////////////////////////////////////////////////////////////////////
   // Leaf Node: scanning & deletions //////////////////////////////////////////
 
   forRange<R>(
@@ -1331,6 +1852,14 @@ class BNodeInternal<K, V> extends BNode<K, V> {
     return this.children[0].minKey();
   }
 
+  minPair(reusedArray: [K, V]): [K, V] | undefined {
+    return this.children[0].minPair(reusedArray);
+  }
+
+  maxPair(reusedArray: [K, V]): [K, V] | undefined {
+    return this.children[this.children.length - 1].maxPair(reusedArray);
+  }
+
   get(key: K, defaultValue: V | undefined, tree: BTree<K, V>): V | undefined {
     var i = this.indexOf(key, 0, tree._compare),
       children = this.children;
@@ -1339,8 +1868,51 @@ class BNodeInternal<K, V> extends BNode<K, V> {
       : undefined;
   }
 
-  checkValid(depth: number, tree: BTree<K, V>): number {
-    var kL = this.keys.length,
+  getPairOrNextLower(
+    key: K,
+    compare: (a: K, b: K) => number,
+    inclusive: boolean,
+    reusedArray: [K, V],
+  ): [K, V] | undefined {
+    var i = this.indexOf(key, 0, compare),
+      children = this.children;
+    if (i >= children.length) return this.maxPair(reusedArray);
+    const result = children[i].getPairOrNextLower(
+      key,
+      compare,
+      inclusive,
+      reusedArray,
+    );
+    if (result === undefined && i > 0) {
+      return children[i - 1].maxPair(reusedArray);
+    }
+    return result;
+  }
+
+  getPairOrNextHigher(
+    key: K,
+    compare: (a: K, b: K) => number,
+    inclusive: boolean,
+    reusedArray: [K, V],
+  ): [K, V] | undefined {
+    var i = this.indexOf(key, 0, compare),
+      children = this.children,
+      length = children.length;
+    if (i >= length) return undefined;
+    const result = children[i].getPairOrNextHigher(
+      key,
+      compare,
+      inclusive,
+      reusedArray,
+    );
+    if (result === undefined && i < length - 1) {
+      return children[i + 1].minPair(reusedArray);
+    }
+    return result;
+  }
+
+  checkValid(depth: number, tree: BTree<K, V>, baseIndex: number): number {
+    let kL = this.keys.length,
       cL = this.children.length;
     check(
       kL === cL,
@@ -1349,19 +1921,30 @@ class BNodeInternal<K, V> extends BNode<K, V> {
       "lengths",
       kL,
       cL,
+      "baseIndex",
+      baseIndex,
+    );
+    check(
+      kL > 1 || depth > 0,
+      "internal node has length",
+      kL,
+      "at depth",
+      depth,
+      "baseIndex",
+      baseIndex,
     );
-    check(kL > 1, "internal node has length", kL, "at depth", depth);
-    var size = 0,
+    let size = 0,
       c = this.children,
       k = this.keys,
       childSize = 0;
     for (var i = 0; i < cL; i++) {
-      size += c[i].checkValid(depth + 1, tree);
+      size += c[i].checkValid(depth + 1, tree, baseIndex + size);
       childSize += c[i].keys.length;
-      check(size >= childSize, "wtf"); // no way this will ever fail
+      check(size >= childSize, "wtf", baseIndex); // no way this will ever fail
       check(
         i === 0 || c[i - 1].constructor === c[i].constructor,
-        "type mismatch",
+        "type mismatch, baseIndex:",
+        baseIndex,
       );
       if (c[i].maxKey() != k[i])
         check(
@@ -1374,6 +1957,8 @@ class BNodeInternal<K, V> extends BNode<K, V> {
           c[i].maxKey(),
           "at depth",
           depth,
+          "baseIndex",
+          baseIndex,
         );
       if (!(i === 0 || tree._compare(k[i - 1], k[i]) < 0))
         check(
@@ -1387,7 +1972,9 @@ class BNodeInternal<K, V> extends BNode<K, V> {
           k[i],
         );
     }
-    var toofew = childSize < (tree.maxNodeSize >> 1) * cL;
+    // 2020/08: BTree doesn't always avoid grossly undersized nodes,
+    // but AFAIK such nodes are pretty harmless, so accept them.
+    let toofew = childSize === 0; // childSize < (tree.maxNodeSize >> 1)*cL;
     if (toofew || childSize > tree.maxNodeSize * cL)
       check(
         false,
@@ -1397,14 +1984,17 @@ class BNodeInternal<K, V> extends BNode<K, V> {
         size,
         ") at depth",
         depth,
-        ", maxNodeSize:",
+        "maxNodeSize:",
         tree.maxNodeSize,
         "children.length:",
         cL,
+        "baseIndex:",
+        baseIndex,
       );
     return size;
   }
 
+  /////////////////////////////////////////////////////////////////////////////
   // Internal Node: set & node splitting //////////////////////////////////////
 
   set(
@@ -1497,8 +2087,12 @@ class BNodeInternal<K, V> extends BNode<K, V> {
     this.children.unshift((lhs as BNodeInternal<K, V>).children.pop()!);
   }
 
+  /////////////////////////////////////////////////////////////////////////////
   // Internal Node: scanning & deletions //////////////////////////////////////
 
+  // Note: `count` is the next value of the third argument to `onFound`.
+  //       A leaf node's `forRange` function returns a new value for this counter,
+  //       unless the operation is to stop early.
   forRange<R>(
     low: K,
     high: K,
@@ -1509,14 +2103,14 @@ class BNodeInternal<K, V> extends BNode<K, V> {
     onFound?: (k: K, v: V, counter: number) => EditRangeResult<V, R> | void,
   ): EditRangeResult<V, R> | number {
     var cmp = tree._compare;
+    var keys = this.keys,
+      children = this.children;
     var iLow = this.indexOf(low, 0, cmp),
       i = iLow;
     var iHigh = Math.min(
       high === low ? iLow : this.indexOf(high, 0, cmp),
-      this.keys.length - 1,
+      keys.length - 1,
     );
-    var keys = this.keys,
-      children = this.children;
     if (!editMode) {
       // Simple case
       for (; i <= iHigh; i++) {
@@ -1545,6 +2139,8 @@ class BNodeInternal<K, V> extends BNode<K, V> {
             count,
             onFound,
           );
+          // Note: if children[i] is empty then keys[i]=undefined.
+          //       This is an invalid state, but it is fixed below.
           keys[i] = children[i].maxKey();
           if (typeof result !== "number") return result;
           count = result;
@@ -1554,15 +2150,18 @@ class BNodeInternal<K, V> extends BNode<K, V> {
         var half = tree._maxNodeSize >> 1;
         if (iLow > 0) iLow--;
         for (i = iHigh; i >= iLow; i--) {
-          if (children[i].keys.length <= half)
-            this.tryMerge(i, tree._maxNodeSize);
-        }
-        // Are we completely empty?
-        if (children[0].keys.length === 0) {
-          check(children.length === 1 && keys.length === 1, "emptiness bug");
-          children.shift();
-          keys.shift();
+          if (children[i].keys.length <= half) {
+            if (children[i].keys.length !== 0) {
+              this.tryMerge(i, tree._maxNodeSize);
+            } else {
+              // child is empty! delete it!
+              keys.splice(i, 1);
+              children.splice(i, 1);
+            }
+          }
         }
+        if (children.length !== 0 && children[0].keys.length === 0)
+          check(false, "emptiness bug");
       }
     }
     return count;
@@ -1601,6 +2200,27 @@ class BNodeInternal<K, V> extends BNode<K, V> {
   }
 }
 
+/**
+ * A walkable pointer into a BTree for computing efficient diffs between trees with shared data.
+ * - A cursor points to either a key/value pair (KVP) or a node (which can be either a leaf or an internal node).
+ *    As a consequence, a cursor cannot be created for an empty tree.
+ * - A cursor can be walked forwards using `step`. A cursor can be compared to another cursor to
+ *    determine which is ahead in advancement.
+ * - A cursor is valid only for the tree it was created from, and only until the first edit made to
+ *    that tree since the cursor's creation.
+ * - A cursor contains a key for the current location, which is the maxKey when the cursor points to a node
+ *    and a key corresponding to a value when pointing to a leaf.
+ * - Leaf is only populated if the cursor points to a KVP. If this is the case, levelIndices.length === internalSpine.length + 1
+ *    and levelIndices[levelIndices.length - 1] is the index of the value.
+ */
+type DiffCursor<K, V> = {
+  height: number;
+  internalSpine: BNode<K, V>[][];
+  levelIndices: number[];
+  leaf: BNode<K, V> | undefined;
+  currentKey: K;
+};
+
 // Optimization: this array of `undefined`s is used instead of a normal
 // array of values in nodes where `undefined` is the only value.
 // Its length is extended to max node size on first use; since it can
@@ -1608,6 +2228,10 @@ class BNodeInternal<K, V> extends BNode<K, V> {
 // increase, never decrease. Its type should be undefined[] but strangely
 // TypeScript won't allow the comparison V[] === undefined[]. To prevent
 // users from making this array too large, BTree has a maximum node size.
+//
+// FAQ: undefVals[i] is already undefined, so why increase the array size?
+// Reading outside the bounds of an array is relatively slow because it
+// has the side effect of scanning the prototype chain.
 var undefVals: any[] = [];
 
 const Delete = { delete: true },
@@ -1623,7 +2247,7 @@ const ReusedArray: any[] = []; // assumed thread-local
 
 function check(fact: boolean, ...args: any[]) {
   if (!fact) {
-    args.unshift("B+ tree "); // at beginning of message
+    args.unshift("B+ tree"); // at beginning of message
     throw new Error(args.join(" "));
   }
 }
diff --git a/packages/idb-bridge/src/tree/interfaces.ts b/packages/idb-bridge/src/tree/interfaces.ts
index ce8808d09..01013c038 100644
--- a/packages/idb-bridge/src/tree/interfaces.ts
+++ b/packages/idb-bridge/src/tree/interfaces.ts
@@ -1,28 +1,4 @@
-/*
-Copyright (c) 2018 David Piepgrass
-
-Permission is hereby granted, free of charge, to any person obtaining a copy
-of this software and associated documentation files (the "Software"), to deal
-in the Software without restriction, including without limitation the rights
-to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
-copies of the Software, and to permit persons to whom the Software is
-furnished to do so, subject to the following conditions:
-
-The above copyright notice and this permission notice shall be included in all
-copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
-AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
-LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
-OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
-SOFTWARE.
-
-SPDX-License-Identifier: MIT
-*/
-
-// Original repository: https://github.com/qwertie/btree-typescript
+// B+ tree by David Piepgrass. License: MIT
 
 /** Read-only set interface (subinterface of IMapSource<K,any>).
  *  The word "set" usually means that each item in the collection is unique
@@ -350,6 +326,8 @@ export interface IMapF<K = any, V = any> extends IMapSource<K, V>, ISetF<K> {
 export interface ISortedSetF<K = any> extends ISetF<K>, ISortedSetSource<K> {
   // TypeScript requires this method of ISortedSetSource to be repeated
   keys(firstKey?: K): IterableIterator<K>;
+  without(key: K): ISortedSetF<K>;
+  with(key: K): ISortedSetF<K>;
 }
 
 export interface ISortedMapF<K = any, V = any>
diff --git a/packages/idb-bridge/src/util/structuredClone.test.ts b/packages/idb-bridge/src/util/structuredClone.test.ts
index 352c2c30b..a14260daa 100644
--- a/packages/idb-bridge/src/util/structuredClone.test.ts
+++ b/packages/idb-bridge/src/util/structuredClone.test.ts
@@ -46,9 +46,16 @@ test("structured clone", (t) => {
   });
 });
 
-test("structured clone (cycles)", (t) => {
+test("structured clone (array cycles)", (t) => {
   const obj1: any[] = [1, 2];
   obj1.push(obj1);
   const obj1Clone = structuredClone(obj1);
   t.is(obj1Clone, obj1Clone[2]);
 });
+
+test("structured clone (object cycles)", (t) => {
+  const obj1: any = { a: 1, b: 2 };
+  obj1.c = obj1;
+  const obj1Clone = structuredClone(obj1);
+  t.is(obj1Clone, obj1Clone.c);
+});
diff --git a/packages/idb-bridge/src/util/structuredClone.ts b/packages/idb-bridge/src/util/structuredClone.ts
index b6b537433..51e4483e1 100644
--- a/packages/idb-bridge/src/util/structuredClone.ts
+++ b/packages/idb-bridge/src/util/structuredClone.ts
@@ -14,7 +14,7 @@
  permissions and limitations under the License.
 */
 
-import cloneDeep from "lodash/cloneDeep";
+import { DataCloneError } from "./errors.js";
 
 const { toString: toStr } = {};
 const hasOwn = {}.hasOwnProperty;
@@ -77,6 +77,100 @@ function isRegExp(val: any): boolean {
   return toStringTag(val) === "RegExp";
 }
 
+function copyBuffer(cur: any) {
+  if (cur instanceof Buffer) {
+    return Buffer.from(cur);
+  }
+
+  return new cur.constructor(cur.buffer.slice(), cur.byteOffset, cur.length);
+}
+
+function checkCloneableOrThrow(x: any) {
+  if (x == null) return;
+  if (typeof x !== "object" && typeof x !== "function") return;
+  if (x instanceof Date) return;
+  if (Array.isArray(x)) return;
+  if (x instanceof Map) return;
+  if (x instanceof Set) return;
+  if (isUserObject(x)) return;
+  if (isPlainObject(x)) return;
+  throw new DataCloneError();
+}
+
+export function mkDeepClone() {
+  const refs = [] as any;
+  const refsNew = [] as any;
+
+  return clone;
+
+  function cloneArray(a: any) {
+    var keys = Object.keys(a);
+    var a2 = new Array(keys.length);
+    refs.push(a);
+    refsNew.push(a2);
+    for (var i = 0; i < keys.length; i++) {
+      var k = keys[i] as any;
+      var cur = a[k];
+      checkCloneableOrThrow(cur);
+      if (typeof cur !== "object" || cur === null) {
+        a2[k] = cur;
+      } else if (cur instanceof Date) {
+        a2[k] = new Date(cur);
+      } else if (ArrayBuffer.isView(cur)) {
+        a2[k] = copyBuffer(cur);
+      } else {
+        var index = refs.indexOf(cur);
+        if (index !== -1) {
+          a2[k] = refsNew[index];
+        } else {
+          a2[k] = clone(cur);
+        }
+      }
+    }
+    refs.pop();
+    refsNew.pop();
+    return a2;
+  }
+
+  function clone(o: any) {
+    checkCloneableOrThrow(o);
+    if (typeof o !== "object" || o === null) return o;
+    if (o instanceof Date) return new Date(o);
+    if (Array.isArray(o)) return cloneArray(o);
+    if (o instanceof Map) return new Map(cloneArray(Array.from(o)));
+    if (o instanceof Set) return new Set(cloneArray(Array.from(o)));
+    var o2 = {} as any;
+    refs.push(o);
+    refsNew.push(o2);
+    for (var k in o) {
+      if (Object.hasOwnProperty.call(o, k) === false) continue;
+      var cur = o[k] as any;
+      checkCloneableOrThrow(cur);
+      if (typeof cur !== "object" || cur === null) {
+        o2[k] = cur;
+      } else if (cur instanceof Date) {
+        o2[k] = new Date(cur);
+      } else if (cur instanceof Map) {
+        o2[k] = new Map(cloneArray(Array.from(cur)));
+      } else if (cur instanceof Set) {
+        o2[k] = new Set(cloneArray(Array.from(cur)));
+      } else if (ArrayBuffer.isView(cur)) {
+        o2[k] = copyBuffer(cur);
+      } else {
+        var i = refs.indexOf(cur);
+        if (i !== -1) {
+          o2[k] = refsNew[i];
+        } else {
+          o2[k] = clone(cur);
+        }
+      }
+    }
+    refs.pop();
+    refsNew.pop();
+    return o2;
+  }
+}
+
 function internalEncapsulate(
   val: any,
   outRoot: any,
@@ -262,5 +356,5 @@ export function structuredRevive(val: any): any {
  * Structured clone for IndexedDB.
  */
 export function structuredClone(val: any): any {
-  return cloneDeep(val);
+  return mkDeepClone()(val);
 }
diff --git a/pnpm-lock.yaml b/pnpm-lock.yaml
index bad5c0968..923659f3b 100644
--- a/pnpm-lock.yaml
+++ b/pnpm-lock.yaml
@@ -129,24 +129,20 @@ importers:
       '@rollup/plugin-commonjs': ^17.1.0
       '@rollup/plugin-json': ^4.1.0
       '@rollup/plugin-node-resolve': ^11.2.0
-      '@types/lodash': ^4.14.178
       '@types/node': ^14.14.22
       ava: ^3.15.0
       esm: ^3.2.25
-      lodash: ^4.17.21
       prettier: ^2.2.1
       rimraf: ^3.0.2
       rollup: ^2.37.1
       tslib: ^2.1.0
       typescript: ^4.1.3
     dependencies:
-      lodash: 4.17.21
       tslib: 2.1.0
     devDependencies:
       '@rollup/plugin-commonjs': 17.1.0_rollup@2.37.1
       '@rollup/plugin-json': 4.1.0_rollup@2.37.1
       '@rollup/plugin-node-resolve': 11.2.0_rollup@2.37.1
-      '@types/lodash': 4.14.178
       '@types/node': 14.14.22
       ava: 3.15.0
       esm: 3.2.25
@@ -10169,10 +10165,6 @@ packages:
     resolution: {integrity: sha1-7ihweulOEdK4J7y+UnC86n8+ce4=}
     dev: true
 
-  /@types/lodash/4.14.178:
-    resolution: {integrity: sha512-0d5Wd09ItQWH1qFbEyQ7oTQ3GZrMfth5JkbN3EvTKLXcHLRDSXeLnlvlOn0wvxVIwK5o2M8JzP/OWz7T3NRsbw==}
-    dev: true
-
   /@types/markdown-to-jsx/6.11.3:
     resolution: {integrity: sha512-30nFYpceM/ZEvhGiqWjm5quLUxNeld0HCzJEXMZZDpq53FPkS85mTwkWtCXzCqq8s5JYLgM5W392a02xn8Bdaw==}
     dependencies:
@@ -11573,7 +11565,7 @@ packages:
   /axios/0.21.4:
     resolution: {integrity: sha512-ut5vewkiu8jjGBdqpM44XxjuCjq9LAKeHVmoVfHVzy8eHgxxq8SbAVQNovDA8mVi05kP0Ea/n/UzcSHcTJQfNg==}
     dependencies:
-      follow-redirects: 1.14.5
+      follow-redirects: 1.14.5_debug@4.3.2
     transitivePeerDependencies:
       - debug
     dev: true
@@ -15713,16 +15705,6 @@ packages:
         optional: true
     dev: false
 
-  /follow-redirects/1.14.5:
-    resolution: {integrity: sha512-wtphSXy7d4/OR+MvIFbCVBDzZ5520qV8XfPklSN5QtxuMUJZ+b0Wnst1e1lCDocfzuCkHqj8k0FpZqO+UIaKNA==}
-    engines: {node: '>=4.0'}
-    peerDependencies:
-      debug: '*'
-    peerDependenciesMeta:
-      debug:
-        optional: true
-    dev: true
-
   /follow-redirects/1.14.5_debug@4.3.2:
     resolution: {integrity: sha512-wtphSXy7d4/OR+MvIFbCVBDzZ5520qV8XfPklSN5QtxuMUJZ+b0Wnst1e1lCDocfzuCkHqj8k0FpZqO+UIaKNA==}
     engines: {node: '>=4.0'}
@@ -19335,6 +19317,7 @@ packages:
 
   /lodash/4.17.21:
     resolution: {integrity: sha512-v2kDEe57lecTulaDIuNTPy3Ry4gLGJ6Z1O3vE1krgXZNrsQ+LFTGHVxVjcXPs17LhbZVGedAJv8XZ1tvj5FvSg==}
+    dev: true
 
   /log-symbols/4.1.0:
     resolution: {integrity: sha512-8XPvpAA8uyhfteu8pIvQxpJZ7SYYdpUivZpGy6sFsBuKRY/7rQGavedeB8aK+Zkyq6upMFVL/9AW6vOYzfRyLg==}
@@ -20948,7 +20931,7 @@ packages:
     resolution: {integrity: sha512-7Wjy+9E3WwLOEL30D+m8TSTF7qJJUJLONBnwQp0518siuMxUQUbgZwssaFX+QKlZkjHZcw/IpZCt/H0srrntSg==}
     engines: {node: '>=6'}
     dependencies:
-      ts-pnp: 1.2.0_typescript@4.4.3
+      ts-pnp: 1.2.0_typescript@4.3.5
     transitivePeerDependencies:
       - typescript
     dev: true
@@ -25024,6 +25007,18 @@ packages:
       tslib: 2.3.1
     dev: true
 
+  /ts-pnp/1.2.0_typescript@4.3.5:
+    resolution: {integrity: sha512-csd+vJOb/gkzvcCHgTGSChYpy5f1/XKNsmvBGO4JXS+z1v2HobugDz4s1IeFXM3wZB44uczs+eazB5Q/ccdhQw==}
+    engines: {node: '>=6'}
+    peerDependencies:
+      typescript: '*'
+    peerDependenciesMeta:
+      typescript:
+        optional: true
+    dependencies:
+      typescript: 4.3.5
+    dev: true
+
   /ts-pnp/1.2.0_typescript@4.4.3:
     resolution: {integrity: sha512-csd+vJOb/gkzvcCHgTGSChYpy5f1/XKNsmvBGO4JXS+z1v2HobugDz4s1IeFXM3wZB44uczs+eazB5Q/ccdhQw==}
     engines: {node: '>=6'}