idb wip

33 files changed, 5784 insertions, 0 deletions

diff --git a/packages/idb-bridge/src/BridgeIDBCursor.ts b/packages/idb-bridge/src/BridgeIDBCursor.ts
new file mode 100644
index 000000000..0120bb7d5
--- /dev/null
+++ b/packages/idb-bridge/src/BridgeIDBCursor.ts
@@ -0,0 +1,315 @@
+/*
+ Copyright 2019 Florian Dold
+ Copyright 2017 Jeremy Scheff
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ or implied. See the License for the specific language governing
+ permissions and limitations under the License.
+ */
+
+import BridgeIDBKeyRange from "./BridgeIDBKeyRange";
+import BridgeIDBObjectStore from "./BridgeIDBObjectStore";
+import BridgeIDBRequest from "./BridgeIDBRequest";
+import cmp from "./util/cmp";
+import {
+  DataError,
+  InvalidAccessError,
+  InvalidStateError,
+  ReadOnlyError,
+  TransactionInactiveError,
+} from "./util/errors";
+import extractKey from "./util/extractKey";
+import structuredClone from "./util/structuredClone";
+import {
+  CursorRange,
+  CursorSource,
+  Key,
+  Value,
+  BridgeIDBCursorDirection,
+} from "./util/types";
+import valueToKey from "./util/valueToKey";
+import {
+  RecordGetRequest,
+  ResultLevel,
+  Backend,
+  DatabaseTransaction,
+  RecordStoreRequest,
+} from "./backend-interface";
+
+/**
+ * http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#cursor
+ */
+class BridgeIDBCursor {
+  _request: BridgeIDBRequest | undefined;
+
+  private _gotValue: boolean = false;
+  private _range: CursorRange;
+  private _position = undefined; // Key of previously returned record
+  private _objectStorePosition = undefined;
+  private _keyOnly: boolean = false;
+
+  private _source: CursorSource;
+  private _direction: BridgeIDBCursorDirection;
+  private _key = undefined;
+  private _primaryKey: Key | undefined = undefined;
+  private _indexName: string | undefined;
+  private _objectStoreName: string;
+
+  constructor(
+    source: CursorSource,
+    objectStoreName: string,
+    indexName: string | undefined,
+    range: CursorRange,
+    direction: BridgeIDBCursorDirection,
+    request: BridgeIDBRequest,
+    keyOnly: boolean,
+  ) {
+    this._indexName = indexName;
+    this._objectStoreName = objectStoreName;
+    this._range = range;
+    this._source = source;
+    this._direction = direction;
+    this._request = request;
+    this._keyOnly = keyOnly;
+  }
+
+  get _effectiveObjectStore(): BridgeIDBObjectStore {
+    if (this.source instanceof BridgeIDBObjectStore) {
+      return this.source;
+    }
+    return this.source.objectStore;
+  }
+
+  get _backend(): Backend {
+    return this._source._backend;
+  }
+
+  // Read only properties
+  get source() {
+    return this._source;
+  }
+  set source(val) {
+    /* For babel */
+  }
+
+  get direction() {
+    return this._direction;
+  }
+  set direction(val) {
+    /* For babel */
+  }
+
+  get key() {
+    return this._key;
+  }
+  set key(val) {
+    /* For babel */
+  }
+
+  get primaryKey() {
+    return this._primaryKey;
+  }
+  set primaryKey(val) {
+    /* For babel */
+  }
+
+  /**
+   * https://w3c.github.io/IndexedDB/#iterate-a-cursor
+   */
+  async _iterate(key?: Key, primaryKey?: Key): Promise<any> {
+    const recordGetRequest: RecordGetRequest = {
+      direction: this.direction,
+      indexName: this._indexName,
+      lastIndexPosition: this._position,
+      lastObjectStorePosition: this._objectStorePosition,
+      limit: 1,
+      range: this._range,
+      objectStoreName: this._objectStoreName,
+      advanceIndexKey: key,
+      advancePrimaryKey: primaryKey,
+      resultLevel: this._keyOnly ? ResultLevel.OnlyKeys : ResultLevel.Full,
+    };
+
+    const { btx } = this.source._confirmActiveTransaction();
+
+    let response = await this._backend.getRecords(
+      btx,
+      recordGetRequest,
+    );
+
+    if (response.count === 0) {
+      return null;
+    }
+
+    return this;
+  }
+
+  // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBCursor-update-IDBRequest-any-value
+  public update(value: Value) {
+    if (value === undefined) {
+      throw new TypeError();
+    }
+
+    const transaction = this._effectiveObjectStore.transaction;
+
+    if (transaction._state !== "active") {
+      throw new TransactionInactiveError();
+    }
+
+    if (transaction.mode === "readonly") {
+      throw new ReadOnlyError();
+    }
+
+    if (this._effectiveObjectStore._deleted) {
+      throw new InvalidStateError();
+    }
+    if (
+      !(this.source instanceof BridgeIDBObjectStore) &&
+      this.source._deleted
+    ) {
+      throw new InvalidStateError();
+    }
+
+    if (!this._gotValue || !this.hasOwnProperty("value")) {
+      throw new InvalidStateError();
+    }
+
+    const storeReq: RecordStoreRequest = {
+      overwrite: true,
+      key: this._primaryKey,
+      value: value,
+      objectStoreName: this._objectStoreName,
+    };
+
+    const operation = async () => {
+      const { btx } = this.source._confirmActiveTransaction();
+      this._backend.storeRecord(btx, storeReq);
+    };
+    return transaction._execRequestAsync({
+      operation,
+      source: this,
+    });
+  }
+
+  /**
+   * http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBCursor-advance-void-unsigned-long-count
+   */
+  public advance(count: number) {
+    throw Error("not implemented");
+  }
+
+  /**
+   * http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBCursor-continue-void-any-key
+   */
+  public continue(key?: Key) {
+    const transaction = this._effectiveObjectStore.transaction;
+
+    if (transaction._state !== "active") {
+      throw new TransactionInactiveError();
+    }
+
+    if (this._effectiveObjectStore._deleted) {
+      throw new InvalidStateError();
+    }
+    if (
+      !(this.source instanceof BridgeIDBObjectStore) &&
+      this.source._deleted
+    ) {
+      throw new InvalidStateError();
+    }
+
+    if (!this._gotValue) {
+      throw new InvalidStateError();
+    }
+
+    if (key !== undefined) {
+      key = valueToKey(key);
+
+      const cmpResult = cmp(key, this._position);
+
+      if (
+        (cmpResult <= 0 &&
+          (this.direction === "next" || this.direction === "nextunique")) ||
+        (cmpResult >= 0 &&
+          (this.direction === "prev" || this.direction === "prevunique"))
+      ) {
+        throw new DataError();
+      }
+    }
+
+    if (this._request) {
+      this._request.readyState = "pending";
+    }
+
+    const operation = async () => {
+      this._iterate(key);
+    };
+
+    transaction._execRequestAsync({
+      operation,
+      request: this._request,
+      source: this.source,
+    });
+
+    this._gotValue = false;
+  }
+
+  // https://w3c.github.io/IndexedDB/#dom-idbcursor-continueprimarykey
+  public continuePrimaryKey(key: Key, primaryKey: Key) {
+    throw Error("not implemented");
+  }
+
+  public delete() {
+    const transaction = this._effectiveObjectStore.transaction;
+
+    if (transaction._state !== "active") {
+      throw new TransactionInactiveError();
+    }
+
+    if (transaction.mode === "readonly") {
+      throw new ReadOnlyError();
+    }
+
+    if (this._effectiveObjectStore._deleted) {
+      throw new InvalidStateError();
+    }
+    if (
+      !(this.source instanceof BridgeIDBObjectStore) &&
+      this.source._deleted
+    ) {
+      throw new InvalidStateError();
+    }
+
+    if (!this._gotValue || !this.hasOwnProperty("value")) {
+      throw new InvalidStateError();
+    }
+
+    const operation = async () => {
+      const { btx } = this.source._confirmActiveTransaction();
+      this._backend.deleteRecord(
+        btx,
+        this._objectStoreName,
+        BridgeIDBKeyRange._valueToKeyRange(this._primaryKey),
+      );
+    };
+
+    return transaction._execRequestAsync({
+      operation,
+      source: this,
+    });
+  }
+
+  public toString() {
+    return "[object IDBCursor]";
+  }
+}
+
+export default BridgeIDBCursor;
diff --git a/packages/idb-bridge/src/BridgeIDBCursorWithValue.ts b/packages/idb-bridge/src/BridgeIDBCursorWithValue.ts
new file mode 100644
index 000000000..2739a6f14
--- /dev/null
+++ b/packages/idb-bridge/src/BridgeIDBCursorWithValue.ts
@@ -0,0 +1,44 @@
+/*
+ Copyright 2017 Jeremy Scheff
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ or implied. See the License for the specific language governing
+ permissions and limitations under the License.
+ */
+
+import BridgeIDBCursor from "./BridgeIDBCursor";
+import {
+    CursorRange,
+    CursorSource,
+    BridgeIDBCursorDirection,
+    Value,
+} from "./util/types";
+
+class FDBCursorWithValue extends BridgeIDBCursor {
+    public value: Value = undefined;
+
+    constructor(
+        source: CursorSource,
+        objectStoreName: string,
+        indexName: string | undefined,
+        range: CursorRange,
+        direction: BridgeIDBCursorDirection,
+        request?: any,
+    ) {
+        super(source, objectStoreName, indexName, range, direction, request, true);
+    }
+
+    public toString() {
+        return "[object IDBCursorWithValue]";
+    }
+}
+
+export default FDBCursorWithValue;
diff --git a/packages/idb-bridge/src/BridgeIDBDatabase.ts b/packages/idb-bridge/src/BridgeIDBDatabase.ts
new file mode 100644
index 000000000..cff2fd6e3
--- /dev/null
+++ b/packages/idb-bridge/src/BridgeIDBDatabase.ts
@@ -0,0 +1,239 @@
+/*
+ * Copyright 2017 Jeremy Scheff
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ * or implied. See the License for the specific language governing
+ * permissions and limitations under the License.
+ */
+
+import BridgeIDBTransaction from "./BridgeIDBTransaction";
+import {
+  ConstraintError,
+  InvalidAccessError,
+  InvalidStateError,
+  NotFoundError,
+  TransactionInactiveError,
+} from "./util/errors";
+import fakeDOMStringList from "./util/fakeDOMStringList";
+import FakeEventTarget from "./util/FakeEventTarget";
+import { FakeDOMStringList, KeyPath, TransactionMode } from "./util/types";
+import validateKeyPath from "./util/validateKeyPath";
+import queueTask from "./util/queueTask";
+import {
+  Backend,
+  DatabaseConnection,
+  Schema,
+  DatabaseTransaction,
+} from "./backend-interface";
+
+/**
+ * Ensure that an active version change transaction is currently running.
+ */
+const confirmActiveVersionchangeTransaction = (database: BridgeIDBDatabase) => {
+  if (!database._runningVersionchangeTransaction) {
+    throw new InvalidStateError();
+  }
+
+  // Find the latest versionchange transaction
+  const transactions = database._transactions.filter(
+    (tx: BridgeIDBTransaction) => {
+      return tx.mode === "versionchange";
+    },
+  );
+  const transaction = transactions[transactions.length - 1];
+
+  if (!transaction || transaction._state === "finished") {
+    throw new InvalidStateError();
+  }
+
+  if (transaction._state !== "active") {
+    throw new TransactionInactiveError();
+  }
+
+  return transaction;
+};
+
+
+// http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#database-interface
+class BridgeIDBDatabase extends FakeEventTarget {
+  _closePending = false;
+  _closed = false;
+  _runningVersionchangeTransaction = false;
+  _transactions: Array<BridgeIDBTransaction> = [];
+
+  _backendConnection: DatabaseConnection;
+  _backend: Backend;
+
+  _schema: Schema;
+
+  get name(): string {
+    return this._schema.databaseName;
+  }
+
+  get version(): number {
+    return this._schema.databaseVersion;
+  }
+
+  get objectStoreNames(): FakeDOMStringList {
+    return fakeDOMStringList(Object.keys(this._schema.objectStores)).sort();
+  }
+
+  /**
+   * http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#database-closing-steps
+   */
+  _closeConnection() {
+    this._closePending = true;
+
+    const transactionsComplete = this._transactions.every(
+      (transaction: BridgeIDBTransaction) => {
+        return transaction._state === "finished";
+      },
+    );
+
+    if (transactionsComplete) {
+      this._closed = true;
+      this._backend.close(this._backendConnection);
+    } else {
+      queueTask(() => {
+        this._closeConnection();
+      });
+    }
+  }
+
+  constructor(backend: Backend, backendConnection: DatabaseConnection) {
+    super();
+
+    this._schema = backend.getSchema(backendConnection);
+
+    this._backend = backend;
+    this._backendConnection = backendConnection;
+  }
+
+  // http://w3c.github.io/IndexedDB/#dom-idbdatabase-createobjectstore
+  public createObjectStore(
+    name: string,
+    options: { autoIncrement?: boolean; keyPath?: KeyPath } | null = {},
+  ) {
+    if (name === undefined) {
+      throw new TypeError();
+    }
+    const transaction = confirmActiveVersionchangeTransaction(this);
+    const backendTx = transaction._backendTransaction;
+    if (!backendTx) {
+      throw Error("invariant violated");
+    }
+
+    const keyPath =
+      options !== null && options.keyPath !== undefined
+        ? options.keyPath
+        : null;
+    const autoIncrement =
+      options !== null && options.autoIncrement !== undefined
+        ? options.autoIncrement
+        : false;
+
+    if (keyPath !== null) {
+      validateKeyPath(keyPath);
+    }
+
+    if (!Object.keys(this._schema.objectStores).includes(name)) {
+      throw new ConstraintError();
+    }
+
+    if (autoIncrement && (keyPath === "" || Array.isArray(keyPath))) {
+      throw new InvalidAccessError();
+    }
+
+    transaction._backend.createObjectStore(backendTx, name, keyPath, autoIncrement);
+
+    this._schema = this._backend.getSchema(this._backendConnection);
+
+    return transaction.objectStore("name");
+  }
+
+  public deleteObjectStore(name: string): void {
+    if (name === undefined) {
+      throw new TypeError();
+    }
+    const transaction = confirmActiveVersionchangeTransaction(this);
+    transaction._objectStoresCache.delete(name);
+  }
+
+  public _internalTransaction(
+    storeNames: string | string[],
+    mode?: TransactionMode,
+    backendTransaction?: DatabaseTransaction,
+  ): BridgeIDBTransaction {
+    mode = mode !== undefined ? mode : "readonly";
+    if (
+      mode !== "readonly" &&
+      mode !== "readwrite" &&
+      mode !== "versionchange"
+    ) {
+      throw new TypeError("Invalid mode: " + mode);
+    }
+
+    const hasActiveVersionchange = this._transactions.some(
+      (transaction: BridgeIDBTransaction) => {
+        return (
+          transaction._state === "active" &&
+          transaction.mode === "versionchange" &&
+          transaction.db === this
+        );
+      },
+    );
+    if (hasActiveVersionchange) {
+      throw new InvalidStateError();
+    }
+
+    if (this._closePending) {
+      throw new InvalidStateError();
+    }
+
+    if (!Array.isArray(storeNames)) {
+      storeNames = [storeNames];
+    }
+    if (storeNames.length === 0 && mode !== "versionchange") {
+      throw new InvalidAccessError();
+    }
+    for (const storeName of storeNames) {
+      if (this.objectStoreNames.indexOf(storeName) < 0) {
+        throw new NotFoundError(
+          "No objectStore named " + storeName + " in this database",
+        );
+      }
+    }
+
+    const tx = new BridgeIDBTransaction(storeNames, mode, this, backendTransaction);
+    this._transactions.push(tx);
+    return tx;
+  }
+
+  public transaction(
+    storeNames: string | string[],
+    mode?: TransactionMode,
+  ): BridgeIDBTransaction {
+    if (mode === "versionchange") {
+      throw new TypeError("Invalid mode: " + mode);
+    }
+    return this._internalTransaction(storeNames, mode);
+  }
+
+  public close() {
+    this._closeConnection();
+  }
+
+  public toString() {
+    return "[object IDBDatabase]";
+  }
+}
+
+export default BridgeIDBDatabase;
diff --git a/packages/idb-bridge/src/BridgeIDBFactory.ts b/packages/idb-bridge/src/BridgeIDBFactory.ts
new file mode 100644
index 000000000..c2747238e
--- /dev/null
+++ b/packages/idb-bridge/src/BridgeIDBFactory.ts
@@ -0,0 +1,192 @@
+/*
+ * Copyright 2019 Florian Dold
+ * Copyright 2017 Jeremy Scheff
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ * or implied. See the License for the specific language governing
+ * permissions and limitations under the License.
+ */
+
+import BridgeIDBDatabase from "./BridgeIDBDatabase";
+import BridgeIDBOpenDBRequest from "./BridgeIDBOpenDBRequest";
+import BridgeIDBVersionChangeEvent from "./BridgeIDBVersionChangeEvent";
+import compareKeys from "./util/cmp";
+import enforceRange from "./util/enforceRange";
+import { AbortError, VersionError } from "./util/errors";
+import FakeEvent from "./util/FakeEvent";
+import { Backend, DatabaseConnection } from "./backend-interface";
+import queueTask from "./util/queueTask";
+
+type DatabaseList = Array<{ name: string; version: number }>;
+
+class BridgeIDBFactory {
+  public cmp = compareKeys;
+  private backend: Backend;
+  private connections: BridgeIDBDatabase[] = [];
+
+  public constructor(backend: Backend) {
+    this.backend = backend;
+  }
+
+  // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBFactory-deleteDatabase-IDBOpenDBRequest-DOMString-name
+  public deleteDatabase(name: string): BridgeIDBOpenDBRequest {
+    const request = new BridgeIDBOpenDBRequest();
+    request.source = null;
+
+    queueTask(async () => {
+      const databases = await this.backend.getDatabases();
+      const dbInfo = databases.find((x) => x.name == name);
+      if (!dbInfo) {
+        // Database already doesn't exist, success!
+        const event = new BridgeIDBVersionChangeEvent("success", {
+          newVersion: null,
+          oldVersion: 0,
+        });
+        request.dispatchEvent(event);
+        return;
+      }
+      const oldVersion = dbInfo.version;
+
+      try {
+        const dbconn = await this.backend.connectDatabase(name);
+        const backendTransaction = await this.backend.enterVersionChange(dbconn, 0);
+        await this.backend.deleteDatabase(backendTransaction, name);
+        await this.backend.commit(backendTransaction);
+        await this.backend.close(dbconn);
+
+        request.result = undefined;
+        request.readyState = "done";
+
+        const event2 = new BridgeIDBVersionChangeEvent("success", {
+          newVersion: null,
+          oldVersion,
+        });
+        request.dispatchEvent(event2);
+      } catch (err) {
+        request.error = new Error();
+        request.error.name = err.name;
+        request.readyState = "done";
+
+        const event = new FakeEvent("error", {
+          bubbles: true,
+          cancelable: true,
+        });
+        event.eventPath = [];
+        request.dispatchEvent(event);
+      }
+    });
+
+    return request;
+  }
+
+  // tslint:disable-next-line max-line-length
+  // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBFactory-open-IDBOpenDBRequest-DOMString-name-unsigned-long-long-version
+  public open(name: string, version?: number) {
+    if (arguments.length > 1 && version !== undefined) {
+      // Based on spec, not sure why "MAX_SAFE_INTEGER" instead of "unsigned long long", but it's needed to pass
+      // tests
+      version = enforceRange(version, "MAX_SAFE_INTEGER");
+    }
+    if (version === 0) {
+      throw new TypeError();
+    }
+
+    const request = new BridgeIDBOpenDBRequest();
+
+    queueTask(async () => {
+      let dbconn: DatabaseConnection;
+      try {
+        dbconn = await this.backend.connectDatabase(name);
+      } catch (err) {
+        request._finishWithError(err);
+        return;
+      }
+
+      const schema = this.backend.getSchema(dbconn);
+      const existingVersion = schema.databaseVersion;
+
+      if (version === undefined) {
+        version = existingVersion !== 0 ? existingVersion : 1;
+      }
+
+      const requestedVersion = version;
+
+      if (existingVersion > requestedVersion) {
+        request._finishWithError(new VersionError());
+        return;
+      }
+
+      const db = new BridgeIDBDatabase(this.backend, dbconn);
+
+      if (existingVersion < requestedVersion) {
+        // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#dfn-steps-for-running-a-versionchange-transaction
+
+        for (const otherConn of this.connections) {
+          const event = new BridgeIDBVersionChangeEvent("versionchange", {
+            newVersion: version,
+            oldVersion: existingVersion,
+          });
+          otherConn.dispatchEvent(event);
+        }
+
+        if (this._anyOpen()) {
+          const event = new BridgeIDBVersionChangeEvent("blocked", {
+            newVersion: version,
+            oldVersion: existingVersion,
+          });
+          request.dispatchEvent(event);
+        }
+
+        const backendTransaction = await this.backend.enterVersionChange(dbconn, requestedVersion);
+        db._runningVersionchangeTransaction = true;
+
+        const transaction = db._internalTransaction(
+          [],
+          "versionchange",
+          backendTransaction,
+        );
+        const event = new BridgeIDBVersionChangeEvent("upgradeneeded", {
+          newVersion: version,
+          oldVersion: existingVersion,
+        });
+
+        request.result = db;
+        request.readyState = "done";
+        request.transaction = transaction;
+        request.dispatchEvent(event);
+
+        await transaction._waitDone();
+
+        db._runningVersionchangeTransaction = false;
+      }
+
+      this.connections.push(db);
+      return db;
+    });
+
+    return request;
+  }
+
+  // https://w3c.github.io/IndexedDB/#dom-idbfactory-databases
+  public databases(): Promise<DatabaseList> {
+    return this.backend.getDatabases();
+  }
+
+  public toString(): string {
+    return "[object IDBFactory]";
+  }
+
+  private _anyOpen(): boolean {
+    return this.connections.some(c => !c._closed && !c._closePending);
+  }
+}
+
+export default BridgeIDBFactory;
diff --git a/packages/idb-bridge/src/BridgeIDBIndex.ts b/packages/idb-bridge/src/BridgeIDBIndex.ts
new file mode 100644
index 000000000..6001bc051
--- /dev/null
+++ b/packages/idb-bridge/src/BridgeIDBIndex.ts
@@ -0,0 +1,316 @@
+/*
+ Copyright 2017 Jeremy Scheff
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ or implied. See the License for the specific language governing
+ permissions and limitations under the License.
+ */
+
+import BridgeIDBCursor from "./BridgeIDBCursor";
+import BridgeIDBCursorWithValue from "./BridgeIDBCursorWithValue";
+import BridgeIDBKeyRange from "./BridgeIDBKeyRange";
+import BridgeIDBObjectStore from "./BridgeIDBObjectStore";
+import BridgeIDBRequest from "./BridgeIDBRequest";
+import enforceRange from "./util/enforceRange";
+import {
+  ConstraintError,
+  InvalidStateError,
+  TransactionInactiveError,
+} from "./util/errors";
+import { BridgeIDBCursorDirection, Key, KeyPath } from "./util/types";
+import valueToKey from "./util/valueToKey";
+import BridgeIDBTransaction from "./BridgeIDBTransaction";
+import {
+  Schema,
+  Backend,
+  DatabaseTransaction,
+  RecordGetRequest,
+  ResultLevel,
+} from "./backend-interface";
+
+const confirmActiveTransaction = (
+  index: BridgeIDBIndex,
+): BridgeIDBTransaction => {
+  if (index._deleted || index.objectStore._deleted) {
+    throw new InvalidStateError();
+  }
+
+  if (index.objectStore.transaction._state !== "active") {
+    throw new TransactionInactiveError();
+  }
+
+  return index.objectStore.transaction;
+};
+
+// http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#idl-def-IDBIndex
+class BridgeIDBIndex {
+  objectStore: BridgeIDBObjectStore;
+
+  get _schema(): Schema {
+    return this.objectStore.transaction.db._schema;
+  }
+
+  get keyPath(): KeyPath {
+    return this._schema.indexes[this._name].keyPath;
+  }
+
+  get multiEntry(): boolean {
+    return this._schema.indexes[this._name].multiEntry;
+  }
+
+  get unique(): boolean {
+    return this._schema.indexes[this._name].unique;
+  }
+
+  get _backend(): Backend {
+    return this.objectStore._backend;
+  }
+
+  _confirmActiveTransaction(): { btx: DatabaseTransaction } {
+    return this.objectStore._confirmActiveTransaction();
+  }
+
+  private _name: string;
+
+  public _deleted: boolean = false;
+
+  constructor(objectStore: BridgeIDBObjectStore, name: string) {
+    this._name = name;
+    this.objectStore = objectStore;
+  }
+
+  get name() {
+    return this._name;
+  }
+
+  // https://w3c.github.io/IndexedDB/#dom-idbindex-name
+  set name(name: any) {
+    const transaction = this.objectStore.transaction;
+
+    if (!transaction.db._runningVersionchangeTransaction) {
+      throw new InvalidStateError();
+    }
+
+    if (transaction._state !== "active") {
+      throw new TransactionInactiveError();
+    }
+
+    const { btx } = this._confirmActiveTransaction();
+
+    const oldName = this._name;
+    const newName = String(name);
+
+    if (newName === oldName) {
+      return;
+    }
+
+    this._backend.renameIndex(btx, oldName, newName);
+
+    if (this.objectStore.indexNames.indexOf(name) >= 0) {
+      throw new ConstraintError();
+    }
+  }
+
+  // tslint:disable-next-line max-line-length
+  // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBIndex-openCursor-IDBRequest-any-range-IDBCursorDirection-direction
+  public openCursor(
+    range?: BridgeIDBKeyRange | Key | null | undefined,
+    direction: BridgeIDBCursorDirection = "next",
+  ) {
+    confirmActiveTransaction(this);
+
+    if (range === null) {
+      range = undefined;
+    }
+    if (range !== undefined && !(range instanceof BridgeIDBKeyRange)) {
+      range = BridgeIDBKeyRange.only(valueToKey(range));
+    }
+
+    const request = new BridgeIDBRequest();
+    request.source = this;
+    request.transaction = this.objectStore.transaction;
+
+    const cursor = new BridgeIDBCursorWithValue(
+      this,
+      this.objectStore.name,
+      this._name,
+      range,
+      direction,
+      request,
+    );
+
+    const operation = async () => {
+      return cursor._iterate();
+    };
+
+    return this.objectStore.transaction._execRequestAsync({
+      operation,
+      request,
+      source: this,
+    });
+  }
+
+  // tslint:disable-next-line max-line-length
+  // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBIndex-openKeyCursor-IDBRequest-any-range-IDBCursorDirection-direction
+  public openKeyCursor(
+    range?: BridgeIDBKeyRange | Key | null | undefined,
+    direction: BridgeIDBCursorDirection = "next",
+  ) {
+    confirmActiveTransaction(this);
+
+    if (range === null) {
+      range = undefined;
+    }
+    if (range !== undefined && !(range instanceof BridgeIDBKeyRange)) {
+      range = BridgeIDBKeyRange.only(valueToKey(range));
+    }
+
+    const request = new BridgeIDBRequest();
+    request.source = this;
+    request.transaction = this.objectStore.transaction;
+
+    const cursor = new BridgeIDBCursor(
+      this,
+      this.objectStore.name,
+      this._name,
+      range,
+      direction,
+      request,
+      true,
+    );
+
+    return this.objectStore.transaction._execRequestAsync({
+      operation: cursor._iterate.bind(cursor),
+      request,
+      source: this,
+    });
+  }
+
+  public get(key: BridgeIDBKeyRange | Key) {
+    confirmActiveTransaction(this);
+
+    if (!(key instanceof BridgeIDBKeyRange)) {
+      key = BridgeIDBKeyRange._valueToKeyRange(key);
+    }
+
+    const getReq: RecordGetRequest = {
+      direction: "next",
+      indexName: this._name,
+      limit: 1,
+      range: key,
+      objectStoreName: this.objectStore._name,
+      resultLevel: ResultLevel.Full,
+    };
+
+    const operation = async () => {
+      const { btx } = this._confirmActiveTransaction();
+      const result = await this._backend.getRecords(btx, getReq);
+      if (result.count == 0) {
+        return undefined;
+      }
+      const values = result.values;
+      if (!values) {
+        throw Error("invariant violated");
+      }
+      return values[0];
+    };
+
+    return this.objectStore.transaction._execRequestAsync({
+      operation,
+      source: this,
+    });
+  }
+
+  // http://w3c.github.io/IndexedDB/#dom-idbindex-getall
+  public getAll(query?: BridgeIDBKeyRange | Key, count?: number) {
+    throw Error("not implemented");
+  }
+
+  // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBIndex-getKey-IDBRequest-any-key
+  public getKey(key: BridgeIDBKeyRange | Key) {
+    confirmActiveTransaction(this);
+
+    if (!(key instanceof BridgeIDBKeyRange)) {
+      key = BridgeIDBKeyRange._valueToKeyRange(key);
+    }
+
+    const getReq: RecordGetRequest = {
+      direction: "next",
+      indexName: this._name,
+      limit: 1,
+      range: key,
+      objectStoreName: this.objectStore._name,
+      resultLevel: ResultLevel.OnlyKeys,
+    };
+
+    const operation = async () => {
+      const { btx } = this._confirmActiveTransaction();
+      const result = await this._backend.getRecords(btx, getReq);
+      if (result.count == 0) {
+        return undefined;
+      }
+      const primaryKeys = result.primaryKeys;
+      if (!primaryKeys) {
+        throw Error("invariant violated");
+      }
+      return primaryKeys[0];
+    };
+
+    return this.objectStore.transaction._execRequestAsync({
+      operation,
+      source: this,
+    });
+  }
+
+  // http://w3c.github.io/IndexedDB/#dom-idbindex-getallkeys
+  public getAllKeys(query?: BridgeIDBKeyRange | Key, count?: number) {
+    throw Error("not implemented");
+  }
+
+  // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBIndex-count-IDBRequest-any-key
+  public count(key: BridgeIDBKeyRange | Key | null | undefined) {
+    confirmActiveTransaction(this);
+
+    if (key === null) {
+      key = undefined;
+    }
+    if (key !== undefined && !(key instanceof BridgeIDBKeyRange)) {
+      key = BridgeIDBKeyRange.only(valueToKey(key));
+    }
+
+    const getReq: RecordGetRequest = {
+      direction: "next",
+      indexName: this._name,
+      limit: 1,
+      range: key,
+      objectStoreName: this.objectStore._name,
+      resultLevel: ResultLevel.OnlyCount,
+    };
+
+    const operation = async () => {
+      const { btx } = this._confirmActiveTransaction();
+      const result = await this._backend.getRecords(btx, getReq);
+      return result.count;
+    };
+
+    return this.objectStore.transaction._execRequestAsync({
+      operation,
+      source: this,
+    });
+
+  }
+
+  public toString() {
+    return "[object IDBIndex]";
+  }
+}
+
+export default BridgeIDBIndex;
diff --git a/packages/idb-bridge/src/BridgeIDBKeyRange.ts b/packages/idb-bridge/src/BridgeIDBKeyRange.ts
new file mode 100644
index 000000000..2b32c7e0a
--- /dev/null
+++ b/packages/idb-bridge/src/BridgeIDBKeyRange.ts
@@ -0,0 +1,133 @@
+/*
+  Copyright 2019 Florian Dold
+  Copyright 2017 Jeremy Scheff
+
+  Licensed under the Apache License, Version 2.0 (the "License");
+  you may not use this file except in compliance with the License.
+  You may obtain a copy of the License at
+
+  http://www.apache.org/licenses/LICENSE-2.0
+
+  Unless required by applicable law or agreed to in writing, software
+  distributed under the License is distributed on an "AS IS" BASIS,
+  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+  or implied. See the License for the specific language governing
+  permissions and limitations under the License.
+ */
+
+import compareKeys from "./util/cmp";
+import { DataError } from "./util/errors";
+import { Key } from "./util/types";
+import valueToKey from "./util/valueToKey";
+
+// http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#range-concept
+class BridgeIDBKeyRange {
+  public static only(value: Key) {
+    if (arguments.length === 0) {
+      throw new TypeError();
+    }
+    value = valueToKey(value);
+    return new BridgeIDBKeyRange(value, value, false, false);
+  }
+
+  static lowerBound(lower: Key, open: boolean = false) {
+    if (arguments.length === 0) {
+      throw new TypeError();
+    }
+    lower = valueToKey(lower);
+    return new BridgeIDBKeyRange(lower, undefined, open, true);
+  }
+
+  static upperBound(upper: Key, open: boolean = false) {
+    if (arguments.length === 0) {
+      throw new TypeError();
+    }
+    upper = valueToKey(upper);
+    return new BridgeIDBKeyRange(undefined, upper, true, open);
+  }
+
+  static bound(
+    lower: Key,
+    upper: Key,
+    lowerOpen: boolean = false,
+    upperOpen: boolean = false,
+  ) {
+    if (arguments.length < 2) {
+      throw new TypeError();
+    }
+
+    const cmpResult = compareKeys(lower, upper);
+    if (cmpResult === 1 || (cmpResult === 0 && (lowerOpen || upperOpen))) {
+      throw new DataError();
+    }
+
+    lower = valueToKey(lower);
+    upper = valueToKey(upper);
+    return new BridgeIDBKeyRange(lower, upper, lowerOpen, upperOpen);
+  }
+
+  readonly lower: Key | undefined;
+  readonly upper: Key | undefined;
+  readonly lowerOpen: boolean;
+  readonly upperOpen: boolean;
+
+  constructor(
+    lower: Key | undefined,
+    upper: Key | undefined,
+    lowerOpen: boolean,
+    upperOpen: boolean,
+  ) {
+    this.lower = lower;
+    this.upper = upper;
+    this.lowerOpen = lowerOpen;
+    this.upperOpen = upperOpen;
+  }
+
+  // https://w3c.github.io/IndexedDB/#dom-idbkeyrange-includes
+  includes(key: Key) {
+    if (arguments.length === 0) {
+      throw new TypeError();
+    }
+    key = valueToKey(key);
+
+    if (this.lower !== undefined) {
+      const cmpResult = compareKeys(this.lower, key);
+
+      if (cmpResult === 1 || (cmpResult === 0 && this.lowerOpen)) {
+        return false;
+      }
+    }
+    if (this.upper !== undefined) {
+      const cmpResult = compareKeys(this.upper, key);
+
+      if (cmpResult === -1 || (cmpResult === 0 && this.upperOpen)) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  toString() {
+    return "[object IDBKeyRange]";
+  }
+
+  static _valueToKeyRange(value: any, nullDisallowedFlag: boolean = false) {
+    if (value instanceof BridgeIDBKeyRange) {
+        return value;
+    }
+
+    if (value === null || value === undefined) {
+        if (nullDisallowedFlag) {
+            throw new DataError();
+        }
+        return new BridgeIDBKeyRange(undefined, undefined, false, false);
+    }
+
+    const key = valueToKey(value);
+
+    return BridgeIDBKeyRange.only(key);
+  }
+
+}
+
+export default BridgeIDBKeyRange;
diff --git a/packages/idb-bridge/src/BridgeIDBObjectStore.ts b/packages/idb-bridge/src/BridgeIDBObjectStore.ts
new file mode 100644
index 000000000..197f06d86
--- /dev/null
+++ b/packages/idb-bridge/src/BridgeIDBObjectStore.ts
@@ -0,0 +1,441 @@
+/*
+ Copyright 2017 Jeremy Scheff
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ or implied. See the License for the specific language governing
+ permissions and limitations under the License.
+ */
+
+import BridgeIDBCursor from "./BridgeIDBCursor";
+import BridgeIDBCursorWithValue from "./BridgeIDBCursorWithValue";
+import BridgeIDBIndex from "./BridgeIDBIndex";
+import BridgeIDBKeyRange from "./BridgeIDBKeyRange";
+import BridgeIDBRequest from "./BridgeIDBRequest";
+import BridgeIDBTransaction from "./BridgeIDBTransaction";
+
+import {
+  ConstraintError,
+  DataError,
+  InvalidAccessError,
+  InvalidStateError,
+  NotFoundError,
+  ReadOnlyError,
+  TransactionInactiveError,
+} from "./util/errors";
+import extractKey from "./util/extractKey";
+import fakeDOMStringList from "./util/fakeDOMStringList";
+import structuredClone from "./util/structuredClone";
+import {
+  FakeDOMStringList,
+  BridgeIDBCursorDirection,
+  Key,
+  KeyPath,
+  Value,
+} from "./util/types";
+import validateKeyPath from "./util/validateKeyPath";
+import valueToKey from "./util/valueToKey";
+import {
+  DatabaseTransaction,
+  RecordGetRequest,
+  ResultLevel,
+} from "./backend-interface";
+
+
+// http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#object-store
+class BridgeIDBObjectStore {
+  _indexesCache: Map<string, BridgeIDBIndex> = new Map();
+
+  transaction: BridgeIDBTransaction;
+
+  get autoIncrement(): boolean {
+    return this._schema.objectStores[this._name].autoIncrement;
+  }
+
+  get indexNames(): FakeDOMStringList {
+    return fakeDOMStringList(this._schema.objectStores[this._name].indexes).sort();
+  }
+
+  get keyPath(): KeyPath | null {
+    return this._schema.objectStores[this._name].keyPath;
+  }
+
+  _name: string;
+
+  get _schema() {
+    return this.transaction.db._schema;
+  }
+
+  _deleted: boolean = false;
+
+  constructor(transaction: BridgeIDBTransaction, name: string) {
+    this._name = name;
+    this.transaction = transaction;
+  }
+
+  get name() {
+    return this._name;
+  }
+
+  get _backend() {
+    return this.transaction.db._backend;
+  }
+
+  get _backendConnection() {
+    return this.transaction.db._backendConnection;
+  }
+
+  _confirmActiveTransaction(): { btx: DatabaseTransaction } {
+    const btx = this.transaction._backendTransaction;
+    if (!btx) {
+      throw new InvalidStateError();
+    }
+    return { btx };
+  }
+
+  // http://w3c.github.io/IndexedDB/#dom-idbobjectstore-name
+  set name(newName: any) {
+    const transaction = this.transaction;
+
+    if (!transaction.db._runningVersionchangeTransaction) {
+      throw new InvalidStateError();
+    }
+
+    let { btx } = this._confirmActiveTransaction();
+
+
+    newName = String(newName);
+
+    const oldName = this._name;
+
+    if (newName === oldName) {
+      return;
+    }
+
+    this._backend.renameObjectStore(btx, oldName, newName);
+    this.transaction.db._schema = this._backend.getSchema(this._backendConnection);
+  }
+
+  public _store(value: Value, key: Key | undefined, overwrite: boolean) {
+    if (this.transaction.mode === "readonly") {
+      throw new ReadOnlyError();
+    }
+    const operation = async () => {
+      const { btx } = this._confirmActiveTransaction();
+      return this._backend.storeRecord(btx, {
+        objectStoreName: this._name,
+        key: key,
+        value: value,
+        overwrite,
+      });
+    };
+
+    return this.transaction._execRequestAsync({ operation, source: this });
+  }
+
+  public put(value: Value, key?: Key) {
+    if (arguments.length === 0) {
+      throw new TypeError();
+    }
+    return this._store(value, key, true);
+  }
+
+  public add(value: Value, key?: Key) {
+    if (arguments.length === 0) {
+      throw new TypeError();
+    }
+    return this._store(value, key, false);
+  }
+
+  public delete(key: Key) {
+    if (arguments.length === 0) {
+      throw new TypeError();
+    }
+
+    if (this.transaction.mode === "readonly") {
+      throw new ReadOnlyError();
+    }
+
+    if (!(key instanceof BridgeIDBKeyRange)) {
+      key = valueToKey(key);
+    }
+
+    const operation = async () => {
+      const { btx } = this._confirmActiveTransaction();
+      return this._backend.deleteRecord(btx, this._name, key);
+    }
+      
+    return this.transaction._execRequestAsync({
+      operation,
+      source: this,
+    });
+  }
+
+  public get(key?: BridgeIDBKeyRange | Key) {
+    if (arguments.length === 0) {
+      throw new TypeError();
+    }
+
+    if (!(key instanceof BridgeIDBKeyRange)) {
+      key = valueToKey(key);
+    }
+
+    const recordRequest: RecordGetRequest = {
+      objectStoreName: this._name,
+      indexName: undefined,
+      lastIndexPosition: undefined,
+      lastObjectStorePosition: undefined,
+      direction: "next",
+      limit: 1,
+      resultLevel: ResultLevel.Full,
+      range: key,
+    };
+
+    const operation = async () => {
+      const { btx } = this._confirmActiveTransaction();
+      const result = await this._backend.getRecords(
+        btx,
+        recordRequest,
+      );
+      if (result.count == 0) {
+        return undefined;
+      }
+      const values = result.values;
+      if (!values) {
+        throw Error("invariant violated");
+      }
+      return values[0];
+    };
+
+    return this.transaction._execRequestAsync({
+      operation,
+      source: this,
+    });
+  }
+
+  // http://w3c.github.io/IndexedDB/#dom-idbobjectstore-getall
+  public getAll(query?: BridgeIDBKeyRange | Key, count?: number) {
+    throw Error("not implemented");
+  }
+
+  // http://w3c.github.io/IndexedDB/#dom-idbobjectstore-getkey
+  public getKey(key?: BridgeIDBKeyRange | Key) {
+    throw Error("not implemented");
+  }
+
+  // http://w3c.github.io/IndexedDB/#dom-idbobjectstore-getallkeys
+  public getAllKeys(query?: BridgeIDBKeyRange | Key, count?: number) {
+    throw Error("not implemented");
+  }
+
+  public clear() {
+    throw Error("not implemented");
+  }
+
+  public openCursor(
+    range?: BridgeIDBKeyRange | Key,
+    direction: BridgeIDBCursorDirection = "next",
+  ) {
+
+    if (range === null) {
+      range = undefined;
+    }
+    if (range !== undefined && !(range instanceof BridgeIDBKeyRange)) {
+      range = BridgeIDBKeyRange.only(valueToKey(range));
+    }
+
+    const request = new BridgeIDBRequest();
+    request.source = this;
+    request.transaction = this.transaction;
+
+    const cursor = new BridgeIDBCursorWithValue(
+      this,
+      this._name,
+      undefined,
+      range,
+      direction,
+      request,
+    );
+
+    return this.transaction._execRequestAsync({
+      operation: () => cursor._iterate(),
+      request,
+      source: this,
+    });
+  }
+
+  public openKeyCursor(
+    range?: BridgeIDBKeyRange | Key,
+    direction?: BridgeIDBCursorDirection,
+  ) {
+    if (range === null) {
+      range = undefined;
+    }
+    if (range !== undefined && !(range instanceof BridgeIDBKeyRange)) {
+      range = BridgeIDBKeyRange.only(valueToKey(range));
+    }
+
+    if (!direction) {
+      direction = "next";
+    }
+
+    const request = new BridgeIDBRequest();
+    request.source = this;
+    request.transaction = this.transaction;
+
+    const cursor = new BridgeIDBCursor(
+      this,
+      this._name,
+      undefined,
+      range,
+      direction,
+      request,
+      true,
+    );
+
+    return this.transaction._execRequestAsync({
+      operation: cursor._iterate.bind(cursor),
+      request,
+      source: this,
+    });
+  }
+
+  // tslint:disable-next-line max-line-length
+  // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBObjectStore-createIndex-IDBIndex-DOMString-name-DOMString-sequence-DOMString--keyPath-IDBIndexParameters-optionalParameters
+  public createIndex(
+    indexName: string,
+    keyPath: KeyPath,
+    optionalParameters: { multiEntry?: boolean; unique?: boolean } = {},
+  ) {
+    if (arguments.length < 2) {
+      throw new TypeError();
+    }
+
+    if (!this.transaction.db._runningVersionchangeTransaction) {
+      throw new InvalidStateError();
+    }
+
+    const { btx } = this._confirmActiveTransaction();
+
+    const multiEntry =
+      optionalParameters.multiEntry !== undefined
+        ? optionalParameters.multiEntry
+        : false;
+    const unique =
+      optionalParameters.unique !== undefined
+        ? optionalParameters.unique
+        : false;
+
+    if (this.transaction.mode !== "versionchange") {
+      throw new InvalidStateError();
+    }
+
+    if (this.indexNames.indexOf(indexName) >= 0) {
+      throw new ConstraintError();
+    }
+
+    validateKeyPath(keyPath);
+
+    if (Array.isArray(keyPath) && multiEntry) {
+      throw new InvalidAccessError();
+    }
+
+    this._backend.createIndex(
+      btx,
+      indexName,
+      this._name,
+      keyPath,
+      multiEntry,
+      unique,
+    );
+
+    return new BridgeIDBIndex(this, indexName);
+  }
+
+  // https://w3c.github.io/IndexedDB/#dom-idbobjectstore-index
+  public index(name: string) {
+    if (arguments.length === 0) {
+      throw new TypeError();
+    }
+
+    if (this.transaction._state === "finished") {
+      throw new InvalidStateError();
+    }
+
+    const index = this._indexesCache.get(name);
+    if (index !== undefined) {
+      return index;
+    }
+
+    return new BridgeIDBIndex(this, name);
+  }
+
+  public deleteIndex(name: string) {
+    if (arguments.length === 0) {
+      throw new TypeError();
+    }
+
+    if (this.transaction.mode !== "versionchange") {
+      throw new InvalidStateError();
+    }
+
+    if (!this.transaction.db._runningVersionchangeTransaction) {
+      throw new InvalidStateError();
+    }
+
+    const { btx } = this._confirmActiveTransaction();
+
+    const index = this._indexesCache.get(name);
+    if (index !== undefined) {
+      index._deleted = true;
+    }
+
+    this._backend.deleteIndex(btx, name);
+  }
+
+  // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#widl-IDBObjectStore-count-IDBRequest-any-key
+  public count(key?: Key | BridgeIDBKeyRange) {
+
+    if (key === null) {
+      key = undefined;
+    }
+    if (key !== undefined && !(key instanceof BridgeIDBKeyRange)) {
+      key = BridgeIDBKeyRange.only(valueToKey(key));
+    }
+
+    const recordGetRequest: RecordGetRequest = {
+      direction: "next",
+      indexName: undefined,
+      lastIndexPosition: undefined,
+      limit: -1,
+      objectStoreName: this._name,
+      lastObjectStorePosition: undefined,
+      range: key,
+      resultLevel: ResultLevel.OnlyCount,
+    };
+
+    const operation = async () => {
+      const { btx } = this._confirmActiveTransaction();
+      const result = await this._backend.getRecords(
+        btx,
+        recordGetRequest,
+      );
+      return result.count;
+    };
+
+    return this.transaction._execRequestAsync({ operation, source: this });
+  }
+
+  public toString() {
+    return "[object IDBObjectStore]";
+  }
+}
+
+export default BridgeIDBObjectStore;
diff --git a/packages/idb-bridge/src/BridgeIDBOpenDBRequest.ts b/packages/idb-bridge/src/BridgeIDBOpenDBRequest.ts
new file mode 100644
index 000000000..7b636193f
--- /dev/null
+++ b/packages/idb-bridge/src/BridgeIDBOpenDBRequest.ts
@@ -0,0 +1,36 @@
+/*
+  Copyright 2019 Florian Dold
+  Copyright 2017 Jeremy Scheff
+
+  Licensed under the Apache License, Version 2.0 (the "License");
+  you may not use this file except in compliance with the License.
+  You may obtain a copy of the License at
+
+  http://www.apache.org/licenses/LICENSE-2.0
+
+  Unless required by applicable law or agreed to in writing, software
+  distributed under the License is distributed on an "AS IS" BASIS,
+  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+  or implied. See the License for the specific language governing
+  permissions and limitations under the License.
+*/
+
+import BridgeIDBRequest from "./BridgeIDBRequest";
+import { EventCallback } from "./util/types";
+
+class BridgeIDBOpenDBRequest extends BridgeIDBRequest {
+    public onupgradeneeded: EventCallback | null = null;
+    public onblocked: EventCallback | null = null;
+
+    constructor() {
+      super();
+      // https://www.w3.org/TR/IndexedDB/#open-requests
+      this.source = null;
+    }
+
+    public toString() {
+        return "[object IDBOpenDBRequest]";
+    }
+}
+
+export default BridgeIDBOpenDBRequest;
diff --git a/packages/idb-bridge/src/BridgeIDBRequest.ts b/packages/idb-bridge/src/BridgeIDBRequest.ts
new file mode 100644
index 000000000..cd0092859
--- /dev/null
+++ b/packages/idb-bridge/src/BridgeIDBRequest.ts
@@ -0,0 +1,86 @@
+/*
+ * Copyright 2017 Jeremy Scheff
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ * or implied. See the License for the specific language governing
+ * permissions and limitations under the License.
+ */
+
+import BridgeFDBCursor from "./BridgeIDBCursor";
+import BridgeIDBIndex from "./BridgeIDBIndex";
+import BridgeIDBObjectStore from "./BridgeIDBObjectStore";
+import BridgeIDBTransaction from "./BridgeIDBTransaction";
+import { InvalidStateError } from "./util/errors";
+import FakeEventTarget from "./util/FakeEventTarget";
+import { EventCallback } from "./util/types";
+import FakeEvent from "./util/FakeEvent";
+
+class BridgeIDBRequest extends FakeEventTarget {
+  _result: any = null;
+  _error: Error | null | undefined = null;
+  source: BridgeFDBCursor | BridgeIDBIndex | BridgeIDBObjectStore | null = null;
+  transaction: BridgeIDBTransaction | null = null;
+  readyState: "done" | "pending" = "pending";
+  onsuccess: EventCallback | null = null;
+  onerror: EventCallback | null = null;
+
+  get error() {
+    if (this.readyState === "pending") {
+      throw new InvalidStateError();
+    }
+    return this._error;
+  }
+
+  set error(value: any) {
+    this._error = value;
+  }
+
+  get result() {
+    if (this.readyState === "pending") {
+      throw new InvalidStateError();
+    }
+    return this._result;
+  }
+
+  set result(value: any) {
+    this._result = value;
+  }
+
+  toString() {
+    return "[object IDBRequest]";
+  }
+
+  _finishWithError(err: Error) {
+    this.result = undefined;
+    this.readyState = "done";
+
+    this.error = new Error(err.message);
+    this.error.name = err.name;
+
+    const event = new FakeEvent("error", {
+      bubbles: true,
+      cancelable: true,
+    });
+    event.eventPath = [];
+    this.dispatchEvent(event);
+  }
+
+  _finishWithResult(result: any) {
+    this.result = result;
+    this.readyState = "done";
+
+    const event = new FakeEvent("success");
+    event.eventPath = [];
+    this.dispatchEvent(event);
+  }
+}
+
+export default BridgeIDBRequest;
diff --git a/packages/idb-bridge/src/BridgeIDBTransaction.ts b/packages/idb-bridge/src/BridgeIDBTransaction.ts
new file mode 100644
index 000000000..a7057e297
--- /dev/null
+++ b/packages/idb-bridge/src/BridgeIDBTransaction.ts
@@ -0,0 +1,301 @@
+import BridgeIDBDatabase from "./BridgeIDBDatabase";
+import BridgeIDBObjectStore from "./BridgeIDBObjectStore";
+import BridgeIDBRequest from "./BridgeIDBRequest";
+import {
+  AbortError,
+  InvalidStateError,
+  NotFoundError,
+  TransactionInactiveError,
+} from "./util/errors";
+import fakeDOMStringList from "./util/fakeDOMStringList";
+import FakeEvent from "./util/FakeEvent";
+import FakeEventTarget from "./util/FakeEventTarget";
+import {
+  EventCallback,
+  FakeDOMStringList,
+  RequestObj,
+  TransactionMode,
+} from "./util/types";
+import queueTask from "./util/queueTask";
+import openPromise from "./util/openPromise";
+import { DatabaseTransaction, Backend } from "./backend-interface";
+import { array } from "prop-types";
+
+// http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#transaction
+class BridgeIDBTransaction extends FakeEventTarget {
+  public _state: "active" | "inactive" | "committing" | "finished" = "active";
+  public _started = false;
+  public _objectStoresCache: Map<string, BridgeIDBObjectStore> = new Map();
+
+  public _backendTransaction?: DatabaseTransaction;
+
+  public objectStoreNames: FakeDOMStringList;
+  public mode: TransactionMode;
+  public db: BridgeIDBDatabase;
+  public error: Error | null = null;
+  public onabort: EventCallback | null = null;
+  public oncomplete: EventCallback | null = null;
+  public onerror: EventCallback | null = null;
+
+  private _waitPromise: Promise<void>;
+  private _resolveWait: () => void;
+
+  public _scope: Set<string>;
+  private _requests: Array<{
+    operation: () => void;
+    request: BridgeIDBRequest;
+  }> = [];
+
+  get _backend(): Backend {
+    return this.db._backend;
+  }
+
+  constructor(
+    storeNames: string[],
+    mode: TransactionMode,
+    db: BridgeIDBDatabase,
+    backendTransaction?: DatabaseTransaction,
+  ) {
+    super();
+
+    const myOpenPromise = openPromise<void>();
+    this._waitPromise = myOpenPromise.promise;
+    this._resolveWait = myOpenPromise.resolve;
+
+    this._scope = new Set(storeNames);
+    this._backendTransaction = backendTransaction;
+    this.mode = mode;
+    this.db = db;
+    this.objectStoreNames = fakeDOMStringList(Array.from(this._scope).sort());
+
+    this.db._transactions.push(this);
+  }
+
+  // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#dfn-steps-for-aborting-a-transaction
+  async _abort(errName: string | null) {
+    this._state = "finished";
+
+    if (errName !== null) {
+      const e = new Error();
+      e.name = errName;
+      this.error = e;
+    }
+
+    // Should this directly remove from _requests?
+    for (const { request } of this._requests) {
+      if (request.readyState !== "done") {
+        request.readyState = "done"; // This will cancel execution of this request's operation
+        if (request.source) {
+          request.result = undefined;
+          request.error = new AbortError();
+
+          const event = new FakeEvent("error", {
+            bubbles: true,
+            cancelable: true,
+          });
+          event.eventPath = [this.db, this];
+          request.dispatchEvent(event);
+        }
+      }
+    }
+
+    // Only roll back if we actually executed the scheduled operations.
+    const maybeBtx = this._backendTransaction;
+    if (maybeBtx) {
+      await this._backend.rollback(maybeBtx);
+    }
+
+    queueTask(() => {
+      const event = new FakeEvent("abort", {
+        bubbles: true,
+        cancelable: false,
+      });
+      event.eventPath = [this.db];
+      this.dispatchEvent(event);
+    });
+
+  }
+
+  public abort() {
+    if (this._state === "committing" || this._state === "finished") {
+      throw new InvalidStateError();
+    }
+    this._state = "active";
+
+    this._abort(null);
+  }
+
+  // http://w3c.github.io/IndexedDB/#dom-idbtransaction-objectstore
+  public objectStore(name: string) {
+    if (this._state !== "active") {
+      throw new InvalidStateError();
+    }
+
+    const objectStore = this._objectStoresCache.get(name);
+    if (objectStore !== undefined) {
+      return objectStore;
+    }
+
+    return new BridgeIDBObjectStore(this, name);
+  }
+
+  // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#dfn-steps-for-asynchronously-executing-a-request
+  public _execRequestAsync(obj: RequestObj) {
+    const source = obj.source;
+    const operation = obj.operation;
+    let request = obj.hasOwnProperty("request") ? obj.request : null;
+
+    if (this._state !== "active") {
+      throw new TransactionInactiveError();
+    }
+
+    // Request should only be passed for cursors
+    if (!request) {
+      if (!source) {
+        // Special requests like indexes that just need to run some code
+        request = new BridgeIDBRequest();
+      } else {
+        request = new BridgeIDBRequest();
+        request.source = source;
+        request.transaction = (source as any).transaction;
+      }
+    }
+
+    this._requests.push({
+      operation,
+      request,
+    });
+
+    return request;
+  }
+
+  public async _start() {
+    this._started = true;
+
+    if (!this._backendTransaction) {
+      this._backendTransaction = await this._backend.beginTransaction(
+        this.db._backendConnection,
+        Array.from(this._scope),
+        this.mode,
+      );
+    }
+
+    // Remove from request queue - cursor ones will be added back if necessary by cursor.continue and such
+    let operation;
+    let request;
+    while (this._requests.length > 0) {
+      const r = this._requests.shift();
+
+      // This should only be false if transaction was aborted
+      if (r && r.request.readyState !== "done") {
+        request = r.request;
+        operation = r.operation;
+        break;
+      }
+    }
+
+    if (request && operation) {
+      if (!request.source) {
+        // Special requests like indexes that just need to run some code, with error handling already built into
+        // operation
+        await operation();
+      } else {
+        let defaultAction;
+        let event;
+        try {
+          const result = await operation();
+          request.readyState = "done";
+          request.result = result;
+          request.error = undefined;
+
+          // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#dfn-fire-a-success-event
+          if (this._state === "inactive") {
+            this._state = "active";
+          }
+          event = new FakeEvent("success", {
+            bubbles: false,
+            cancelable: false,
+          });
+        } catch (err) {
+          request.readyState = "done";
+          request.result = undefined;
+          request.error = err;
+
+          // http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#dfn-fire-an-error-event
+          if (this._state === "inactive") {
+            this._state = "active";
+          }
+          event = new FakeEvent("error", {
+            bubbles: true,
+            cancelable: true,
+          });
+
+          defaultAction = this._abort.bind(this, err.name);
+        }
+
+        try {
+          event.eventPath = [this.db, this];
+          request.dispatchEvent(event);
+        } catch (err) {
+          if (this._state !== "committing") {
+            this._abort("AbortError");
+          }
+          throw err;
+        }
+
+        // Default action of event
+        if (!event.canceled) {
+          if (defaultAction) {
+            defaultAction();
+          }
+        }
+      }
+
+      // On to the next one
+      if (this._requests.length > 0) {
+        this._start();
+      } else {
+        // Give it another chance for new handlers to be set before finishing
+        queueTask(() => this._start());
+      }
+      return;
+    }
+
+    // Check if transaction complete event needs to be fired
+    if (this._state !== "finished") {
+      // Either aborted or committed already
+      this._state = "finished";
+
+      if (!this.error) {
+        const event = new FakeEvent("complete");
+        this.dispatchEvent(event);
+      }
+
+      const idx = this.db._transactions.indexOf(this);
+      if (idx < 0) {
+        throw Error("invariant failed");
+      }
+      this.db._transactions.splice(idx, 1);
+
+      this._resolveWait();
+    }
+  }
+
+  public commit() {
+    if (this._state !== "active") {
+      throw new InvalidStateError();
+    }
+
+    this._state = "committing";
+  }
+
+  public toString() {
+    return "[object IDBRequest]";
+  }
+
+  _waitDone(): Promise<void> {
+    return this._waitPromise;
+  }
+}
+
+export default BridgeIDBTransaction;
diff --git a/packages/idb-bridge/src/BridgeIDBVersionChangeEvent.ts b/packages/idb-bridge/src/BridgeIDBVersionChangeEvent.ts
new file mode 100644
index 000000000..6fc63ee35
--- /dev/null
+++ b/packages/idb-bridge/src/BridgeIDBVersionChangeEvent.ts
@@ -0,0 +1,41 @@
+/*
+  Copyright 2019 Florian Dold
+  Copyright 2017 Jeremy Scheff
+
+  Licensed under the Apache License, Version 2.0 (the "License");
+  you may not use this file except in compliance with the License.
+  You may obtain a copy of the License at
+
+  http://www.apache.org/licenses/LICENSE-2.0
+
+  Unless required by applicable law or agreed to in writing, software
+  distributed under the License is distributed on an "AS IS" BASIS,
+  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+  or implied. See the License for the specific language governing
+  permissions and limitations under the License.
+ */
+
+import FakeEvent from "./util/FakeEvent";
+
+class BridgeIDBVersionChangeEvent extends FakeEvent {
+    public newVersion: number | null;
+    public oldVersion: number;
+
+    constructor(
+        type: "blocked" | "success" | "upgradeneeded" | "versionchange",
+        parameters: { newVersion?: number | null; oldVersion?: number } = {},
+    ) {
+        super(type);
+
+        this.newVersion =
+            parameters.newVersion !== undefined ? parameters.newVersion : null;
+        this.oldVersion =
+            parameters.oldVersion !== undefined ? parameters.oldVersion : 0;
+    }
+
+    public toString() {
+        return "[object IDBVersionChangeEvent]";
+    }
+}
+
+export default BridgeIDBVersionChangeEvent;
diff --git a/packages/idb-bridge/src/MemoryBackend.test.ts b/packages/idb-bridge/src/MemoryBackend.test.ts
new file mode 100644
index 000000000..3d2d0fbc9
--- /dev/null
+++ b/packages/idb-bridge/src/MemoryBackend.test.ts
@@ -0,0 +1,31 @@
+import test from 'ava';
+import MemoryBackend from './MemoryBackend';
+import BridgeIDBFactory from './BridgeIDBFactory';
+
+test.cb("basics", (t) => {
+
+  const backend = new MemoryBackend();
+  const idb = new BridgeIDBFactory(backend);
+
+  const request = idb.open("library");
+  request.onupgradeneeded = () => {
+    const db = request.result;
+    const store = db.createObjectStore("books", {keyPath: "isbn"});
+    const titleIndex = store.createIndex("by_title", "title", {unique: true});
+    const authorIndex = store.createIndex("by_author", "author");
+  
+    // Populate with initial data.
+    store.put({title: "Quarry Memories", author: "Fred", isbn: 123456});
+    store.put({title: "Water Buffaloes", author: "Fred", isbn: 234567});
+    store.put({title: "Bedrock Nights", author: "Barney", isbn: 345678});
+  };
+
+  request.onsuccess = () => {
+    t.end();
+  };
+
+  request.onerror = () => {
+    t.fail();
+  };
+
+});
diff --git a/packages/idb-bridge/src/MemoryBackend.ts b/packages/idb-bridge/src/MemoryBackend.ts
new file mode 100644
index 000000000..2d4b8ab93
--- /dev/null
+++ b/packages/idb-bridge/src/MemoryBackend.ts
@@ -0,0 +1,662 @@
+import {
+  Backend,
+  DatabaseConnection,
+  DatabaseTransaction,
+  Schema,
+  RecordStoreRequest,
+  IndexProperties,
+} from "./backend-interface";
+import structuredClone from "./util/structuredClone";
+import { InvalidStateError, InvalidAccessError } from "./util/errors";
+import BTree, { ISortedMap, ISortedMapF } from "./tree/b+tree";
+import BridgeIDBFactory from "./BridgeIDBFactory";
+import compareKeys from "./util/cmp";
+import extractKey from "./util/extractKey";
+import { Key, Value, KeyPath } from "./util/types";
+
+enum TransactionLevel {
+  Disconnected = 0,
+  Connected = 1,
+  Read = 2,
+  Write = 3,
+  VersionChange = 4,
+}
+
+interface ObjectStore {
+  originalName: string;
+  modifiedName: string | undefined;
+  originalData: ISortedMapF;
+  modifiedData: ISortedMapF | undefined;
+  deleted: boolean;
+  originalKeyGenerator: number;
+  modifiedKeyGenerator: number | undefined;
+}
+
+interface Index {
+  originalName: string;
+  modifiedName: string | undefined;
+  originalData: ISortedMapF;
+  modifiedData: ISortedMapF | undefined;
+  deleted: boolean;
+}
+
+interface Database {
+  committedObjectStores: { [name: string]: ObjectStore };
+  modifiedObjectStores: { [name: string]: ObjectStore };
+  committedIndexes: { [name: string]: Index };
+  modifiedIndexes: { [name: string]: Index };
+  committedSchema: Schema;
+  /**
+   * Was the transaction deleted during the running transaction?
+   */
+  deleted: boolean;
+
+  txLevel: TransactionLevel;
+
+  connectionCookie: string | undefined;
+}
+
+interface Connection {
+  dbName: string;
+
+  modifiedSchema: Schema | undefined;
+
+  /**
+   * Has the underlying database been deleted?
+   */
+  deleted: boolean;
+
+  /**
+   * Map from the effective name of an object store during
+   * the transaction to the real name.
+   */
+  objectStoreMap: { [currentName: string]: ObjectStore };
+  indexMap: { [currentName: string]: Index };
+}
+
+class AsyncCondition {
+  wait(): Promise<void> {
+    throw Error("not implemented");
+  }
+
+  trigger(): void {}
+}
+
+
+
+
+function insertIntoIndex(
+  index: Index,
+  value: Value,
+  indexProperties: IndexProperties,
+) {
+  if (indexProperties.multiEntry) {
+
+  } else {
+    const key = extractKey(value, indexProperties.keyPath);
+  }
+  throw Error("not implemented");
+}
+
+/**
+ * Primitive in-memory backend.
+ */
+export class MemoryBackend implements Backend {
+  databases: { [name: string]: Database } = {};
+
+  connectionIdCounter = 1;
+
+  transactionIdCounter = 1;
+
+  /**
+   * Connections by connection cookie.
+   */
+  connections: { [name: string]: Connection } = {};
+
+  /**
+   * Connections by transaction (!!) cookie.  In this implementation,
+   * at most one transaction can run at the same time per connection.
+   */
+  connectionsByTransaction: { [tx: string]: Connection } = {};
+
+  /**
+   * Condition that is triggered whenever a client disconnects.
+   */
+  disconnectCond: AsyncCondition = new AsyncCondition();
+
+  /**
+   * Conditation that is triggered whenever a transaction finishes.
+   */
+  transactionDoneCond: AsyncCondition = new AsyncCondition();
+
+  async getDatabases(): Promise<{ name: string; version: number }[]> {
+    const dbList = [];
+    for (const name in this.databases) {
+      dbList.push({
+        name,
+        version: this.databases[name].committedSchema.databaseVersion,
+      });
+    }
+    return dbList;
+  }
+
+  async deleteDatabase(tx: DatabaseTransaction, name: string): Promise<void> {
+    const myConn = this.connectionsByTransaction[tx.transactionCookie];
+    if (!myConn) {
+      throw Error("no connection associated with transaction");
+    }
+    const myDb = this.databases[name];
+    if (!myDb) {
+      throw Error("db not found");
+    }
+    if (myDb.committedSchema.databaseName !== name) {
+      throw Error("name does not match");
+    }
+    if (myDb.txLevel < TransactionLevel.VersionChange) {
+      throw new InvalidStateError();
+    }
+    if (myDb.connectionCookie !== tx.transactionCookie) {
+      throw new InvalidAccessError();
+    }
+    myDb.deleted = true;
+  }
+
+  async connectDatabase(name: string): Promise<DatabaseConnection> {
+    const connectionId = this.connectionIdCounter++;
+    const connectionCookie = `connection-${connectionId}`;
+
+    let database = this.databases[name];
+    if (!database) {
+      const schema: Schema = {
+        databaseName: name,
+        indexes: {},
+        databaseVersion: 0,
+        objectStores: {},
+      };
+      database = {
+        committedSchema: schema,
+        deleted: false,
+        modifiedIndexes: {},
+        committedIndexes: {},
+        committedObjectStores: {},
+        modifiedObjectStores: {},
+        txLevel: TransactionLevel.Disconnected,
+        connectionCookie: undefined,
+      };
+      this.databases[name] = database;
+    }
+
+    while (database.txLevel !== TransactionLevel.Disconnected) {
+      await this.disconnectCond.wait();
+    }
+
+    database.txLevel = TransactionLevel.Connected;
+    database.connectionCookie = connectionCookie;
+
+    return { connectionCookie };
+  }
+
+  async beginTransaction(
+    conn: DatabaseConnection,
+    objectStores: string[],
+    mode: import("./util/types").TransactionMode,
+  ): Promise<DatabaseTransaction> {
+    const transactionCookie = `tx-${this.transactionIdCounter++}`;
+    const myConn = this.connections[conn.connectionCookie];
+    if (!myConn) {
+      throw Error("connection not found");
+    }
+    const myDb = this.databases[myConn.dbName];
+    if (!myDb) {
+      throw Error("db not found");
+    }
+
+    while (myDb.txLevel !== TransactionLevel.Connected) {
+      await this.transactionDoneCond.wait();
+    }
+
+    if (mode === "readonly") {
+      myDb.txLevel = TransactionLevel.Read;
+    } else if (mode === "readwrite") {
+      myDb.txLevel = TransactionLevel.Write;
+    } else {
+      throw Error("unsupported transaction mode");
+    }
+
+    this.connectionsByTransaction[transactionCookie] = myConn;
+
+    return { transactionCookie };
+  }
+
+  async enterVersionChange(
+    conn: DatabaseConnection,
+    newVersion: number,
+  ): Promise<DatabaseTransaction> {
+    const transactionCookie = `tx-vc-${this.transactionIdCounter++}`;
+    const myConn = this.connections[conn.connectionCookie];
+    if (!myConn) {
+      throw Error("connection not found");
+    }
+    const myDb = this.databases[myConn.dbName];
+    if (!myDb) {
+      throw Error("db not found");
+    }
+
+    while (myDb.txLevel !== TransactionLevel.Connected) {
+      await this.transactionDoneCond.wait();
+    }
+
+    myDb.txLevel = TransactionLevel.VersionChange;
+
+    this.connectionsByTransaction[transactionCookie] = myConn;
+
+    return { transactionCookie };
+  }
+
+  async close(conn: DatabaseConnection): Promise<void> {
+    const myConn = this.connections[conn.connectionCookie];
+    if (!myConn) {
+      throw Error("connection not found - already closed?");
+    }
+    if (!myConn.deleted) {
+      const myDb = this.databases[myConn.dbName];
+      if (myDb.txLevel != TransactionLevel.Connected) {
+        throw Error("invalid state");
+      }
+      myDb.txLevel = TransactionLevel.Disconnected;
+    }
+    delete this.connections[conn.connectionCookie];
+  }
+
+  getSchema(dbConn: DatabaseConnection): Schema {
+    const myConn = this.connections[dbConn.connectionCookie];
+    if (!myConn) {
+      throw Error("unknown connection");
+    }
+    const db = this.databases[myConn.dbName];
+    if (!db) {
+      throw Error("db not found");
+    }
+    if (myConn.modifiedSchema) {
+      return myConn.modifiedSchema;
+    }
+    return db.committedSchema;
+  }
+
+  renameIndex(
+    btx: DatabaseTransaction,
+    oldName: string,
+    newName: string,
+  ): void {
+    const myConn = this.connections[btx.transactionCookie];
+    if (!myConn) {
+      throw Error("unknown connection");
+    }
+    const db = this.databases[myConn.dbName];
+    if (!db) {
+      throw Error("db not found");
+    }
+    if (db.txLevel < TransactionLevel.VersionChange) {
+      throw Error("only allowed in versionchange transaction");
+    }
+    let schema = myConn.modifiedSchema;
+    if (!schema) {
+      throw Error();
+    }
+    if (schema.indexes[newName]) {
+      throw new Error("new index name already used");
+    }
+    if (!schema.indexes[oldName]) {
+      throw new Error("new index name already used");
+    }
+    const index: Index = myConn.indexMap[oldName];
+    if (!index) {
+      throw Error("old index missing in connection's index map");
+    }
+    schema.indexes[newName] = schema.indexes[newName];
+    delete schema.indexes[oldName];
+    for (const storeName in schema.objectStores) {
+      const store = schema.objectStores[storeName];
+      store.indexes = store.indexes.map(x => {
+        if (x == oldName) {
+          return newName;
+        } else {
+          return x;
+        }
+      });
+    }
+    myConn.indexMap[newName] = index;
+    delete myConn.indexMap[oldName];
+    index.modifiedName = newName;
+  }
+
+  deleteIndex(btx: DatabaseTransaction, indexName: string): void {
+    const myConn = this.connections[btx.transactionCookie];
+    if (!myConn) {
+      throw Error("unknown connection");
+    }
+    const db = this.databases[myConn.dbName];
+    if (!db) {
+      throw Error("db not found");
+    }
+    if (db.txLevel < TransactionLevel.VersionChange) {
+      throw Error("only allowed in versionchange transaction");
+    }
+    let schema = myConn.modifiedSchema;
+    if (!schema) {
+      throw Error();
+    }
+    if (!schema.indexes[indexName]) {
+      throw new Error("index does not exist");
+    }
+    const index: Index = myConn.indexMap[indexName];
+    if (!index) {
+      throw Error("old index missing in connection's index map");
+    }
+    index.deleted = true;
+    delete schema.indexes[indexName];
+    delete myConn.indexMap[indexName];
+    for (const storeName in schema.objectStores) {
+      const store = schema.objectStores[storeName];
+      store.indexes = store.indexes.filter(x => {
+        return x !== indexName;
+      });
+    }
+  }
+
+  deleteObjectStore(btx: DatabaseTransaction, name: string): void {
+    const myConn = this.connections[btx.transactionCookie];
+    if (!myConn) {
+      throw Error("unknown connection");
+    }
+    const db = this.databases[myConn.dbName];
+    if (!db) {
+      throw Error("db not found");
+    }
+    if (db.txLevel < TransactionLevel.VersionChange) {
+      throw Error("only allowed in versionchange transaction");
+    }
+    const schema = myConn.modifiedSchema;
+    if (!schema) {
+      throw Error();
+    }
+    const objectStoreProperties = schema.objectStores[name];
+    if (!objectStoreProperties) {
+      throw Error("object store not found");
+    }
+    const objectStore = myConn.objectStoreMap[name];
+    if (!objectStore) {
+      throw Error("object store not found in map");
+    }
+    const indexNames = objectStoreProperties.indexes;
+    for (const indexName of indexNames) {
+      this.deleteIndex(btx, indexName);
+    }
+
+    objectStore.deleted = true;
+    delete myConn.objectStoreMap[name];
+    delete schema.objectStores[name];
+  }
+
+  renameObjectStore(
+    btx: DatabaseTransaction,
+    oldName: string,
+    newName: string,
+  ): void {
+    const myConn = this.connections[btx.transactionCookie];
+    if (!myConn) {
+      throw Error("unknown connection");
+    }
+    const db = this.databases[myConn.dbName];
+    if (!db) {
+      throw Error("db not found");
+    }
+    if (db.txLevel < TransactionLevel.VersionChange) {
+      throw Error("only allowed in versionchange transaction");
+    }
+    const schema = myConn.modifiedSchema;
+    if (!schema) {
+      throw Error();
+    }
+    if (!schema.objectStores[oldName]) {
+      throw Error("object store not found");
+    }
+    if (schema.objectStores[newName]) {
+      throw Error("new object store already exists");
+    }
+    const objectStore = myConn.objectStoreMap[oldName];
+    if (!objectStore) {
+      throw Error("object store not found in map");
+    }
+    objectStore.modifiedName = newName;
+    schema.objectStores[newName] = schema.objectStores[oldName];
+    delete schema.objectStores[oldName];
+    delete myConn.objectStoreMap[oldName];
+    myConn.objectStoreMap[newName] = objectStore;
+  }
+
+  createObjectStore(
+    btx: DatabaseTransaction,
+    name: string,
+    keyPath: string | string[] | null,
+    autoIncrement: boolean,
+  ): void {
+    const myConn = this.connections[btx.transactionCookie];
+    if (!myConn) {
+      throw Error("unknown connection");
+    }
+    const db = this.databases[myConn.dbName];
+    if (!db) {
+      throw Error("db not found");
+    }
+    if (db.txLevel < TransactionLevel.VersionChange) {
+      throw Error("only allowed in versionchange transaction");
+    }
+    const newObjectStore: ObjectStore = {
+      deleted: false,
+      modifiedName: undefined,
+      originalName: name,
+      modifiedData: undefined,
+      originalData: new BTree([], compareKeys),
+      modifiedKeyGenerator: undefined,
+      originalKeyGenerator: 1,
+    };
+    const schema = myConn.modifiedSchema;
+    if (!schema) {
+      throw Error("no schema for versionchange tx");
+    }
+    schema.objectStores[name] = {
+      autoIncrement,
+      keyPath,
+      indexes: [],
+    };
+    myConn.objectStoreMap[name] = newObjectStore;
+    db.modifiedObjectStores[name] = newObjectStore;
+  }
+
+  createIndex(
+    btx: DatabaseTransaction,
+    indexName: string,
+    objectStoreName: string,
+    keyPath: import("./util/types").KeyPath,
+    multiEntry: boolean,
+    unique: boolean,
+  ): void {
+    const myConn = this.connections[btx.transactionCookie];
+    if (!myConn) {
+      throw Error("unknown connection");
+    }
+    const db = this.databases[myConn.dbName];
+    if (!db) {
+      throw Error("db not found");
+    }
+    if (db.txLevel < TransactionLevel.VersionChange) {
+      throw Error("only allowed in versionchange transaction");
+    }
+    const indexProperties: IndexProperties = {
+      keyPath,
+      multiEntry,
+      unique,
+    };
+    const newIndex: Index = {
+      deleted: false,
+      modifiedData: undefined,
+      modifiedName: undefined,
+      originalData: new BTree([], compareKeys),
+      originalName: indexName,
+    };
+    myConn.indexMap[indexName] = newIndex;
+    db.modifiedIndexes[indexName] = newIndex;
+    const schema = myConn.modifiedSchema;
+    if (!schema) {
+      throw Error("no schema in versionchange tx");
+    }
+    const objectStoreProperties = schema.objectStores[objectStoreName];
+    if (!objectStoreProperties) {
+      throw Error("object store not found");
+    }
+    objectStoreProperties.indexes.push(indexName);
+    schema.indexes[indexName] = indexProperties;
+
+    // FIXME: build index from existing object store!
+  }
+
+  async deleteRecord(
+    btx: DatabaseTransaction,
+    objectStoreName: string,
+    range: import("./BridgeIDBKeyRange").default,
+  ): Promise<void> {
+    const myConn = this.connections[btx.transactionCookie];
+    if (!myConn) {
+      throw Error("unknown connection");
+    }
+    const db = this.databases[myConn.dbName];
+    if (!db) {
+      throw Error("db not found");
+    }
+    if (db.txLevel < TransactionLevel.Write) {
+      throw Error("only allowed in write transaction");
+    }
+  }
+
+  async getRecords(
+    btx: DatabaseTransaction,
+    req: import("./backend-interface").RecordGetRequest,
+  ): Promise<import("./backend-interface").RecordGetResponse> {
+    const myConn = this.connections[btx.transactionCookie];
+    if (!myConn) {
+      throw Error("unknown connection");
+    }
+    const db = this.databases[myConn.dbName];
+    if (!db) {
+      throw Error("db not found");
+    }
+    if (db.txLevel < TransactionLevel.Write) {
+      throw Error("only allowed while running a transaction");
+    }
+    throw Error("not implemented");
+  }
+
+  async storeRecord(
+    btx: DatabaseTransaction,
+    storeReq: RecordStoreRequest,
+  ): Promise<void> {
+    const myConn = this.connections[btx.transactionCookie];
+    if (!myConn) {
+      throw Error("unknown connection");
+    }
+    const db = this.databases[myConn.dbName];
+    if (!db) {
+      throw Error("db not found");
+    }
+    if (db.txLevel < TransactionLevel.Write) {
+      throw Error("only allowed while running a transaction");
+    }
+    const schema = myConn.modifiedSchema
+      ? myConn.modifiedSchema
+      : db.committedSchema;
+
+    const objectStore = myConn.objectStoreMap[storeReq.objectStoreName];
+
+    const storeKeyResult: StoreKeyResult = getStoreKey(
+      storeReq.value,
+      storeReq.key,
+      objectStore.modifiedKeyGenerator || objectStore.originalKeyGenerator,
+      schema.objectStores[storeReq.objectStoreName].autoIncrement,
+      schema.objectStores[storeReq.objectStoreName].keyPath,
+    );
+    let key = storeKeyResult.key;
+    let value = storeKeyResult.value;
+    objectStore.modifiedKeyGenerator = storeKeyResult.updatedKeyGenerator;
+
+    if (!objectStore.modifiedData) {
+      objectStore.modifiedData = objectStore.originalData;
+    }
+    const modifiedData = objectStore.modifiedData;
+    const hasKey = modifiedData.has(key);
+    if (hasKey && !storeReq.overwrite) {
+      throw Error("refusing to overwrite");
+    }
+
+    objectStore.modifiedData = modifiedData.with(key, value, true);
+
+    for (const indexName of schema.objectStores[storeReq.objectStoreName]
+      .indexes) {
+      const index = myConn.indexMap[indexName];
+      if (!index) {
+        throw Error("index referenced by object store does not exist");
+      }
+      const indexProperties = schema.indexes[indexName];
+      insertIntoIndex(index, value, indexProperties);
+    }
+  }
+
+  async rollback(btx: DatabaseTransaction): Promise<void> {
+    const myConn = this.connections[btx.transactionCookie];
+    if (!myConn) {
+      throw Error("unknown connection");
+    }
+    const db = this.databases[myConn.dbName];
+    if (!db) {
+      throw Error("db not found");
+    }
+    if (db.txLevel < TransactionLevel.Read) {
+      throw Error("only allowed while running a transaction");
+    }
+    db.modifiedIndexes = {};
+    db.modifiedObjectStores = {};
+    db.txLevel = TransactionLevel.Connected;
+    myConn.modifiedSchema = structuredClone(db.committedSchema);
+    myConn.indexMap = Object.assign({}, db.committedIndexes);
+    myConn.objectStoreMap = Object.assign({}, db.committedObjectStores);
+    for (const indexName in db.committedIndexes) {
+      const index = db.committedIndexes[indexName];
+      index.deleted = false;
+      index.modifiedData = undefined;
+      index.modifiedName = undefined;
+    }
+    for (const objectStoreName in db.committedObjectStores) {
+      const objectStore = db.committedObjectStores[objectStoreName];
+      objectStore.deleted = false;
+      objectStore.modifiedData = undefined;
+      objectStore.modifiedName = undefined;
+      objectStore.modifiedKeyGenerator = undefined;
+    }
+  }
+
+  async commit(btx: DatabaseTransaction): Promise<void> {
+    const myConn = this.connections[btx.transactionCookie];
+    if (!myConn) {
+      throw Error("unknown connection");
+    }
+    const db = this.databases[myConn.dbName];
+    if (!db) {
+      throw Error("db not found");
+    }
+    if (db.txLevel < TransactionLevel.Read) {
+      throw Error("only allowed while running a transaction");
+    }
+  }
+}
+
+export default MemoryBackend;
diff --git a/packages/idb-bridge/src/backend-interface.ts b/packages/idb-bridge/src/backend-interface.ts
new file mode 100644
index 000000000..c0f498a10
--- /dev/null
+++ b/packages/idb-bridge/src/backend-interface.ts
@@ -0,0 +1,145 @@
+import {
+  TransactionMode,
+  Value,
+  BridgeIDBCursorDirection,
+  Key,
+  KeyPath,
+  BridgeIDBDatabaseInfo,
+} from "./util/types";
+import BridgeIDBKeyRange from "./BridgeIDBKeyRange";
+
+export interface ObjectStoreProperties {
+  keyPath: KeyPath | null;
+  autoIncrement: boolean;
+  indexes: string[];
+}
+
+export interface IndexProperties {
+  keyPath: KeyPath;
+  multiEntry: boolean;
+  unique: boolean;
+}
+
+export interface Schema {
+  databaseName: string;
+  databaseVersion: number;
+  objectStores: { [name: string]: ObjectStoreProperties };
+  indexes: { [name: string]: IndexProperties };
+}
+
+export interface DatabaseConnection {
+  connectionCookie: string;
+}
+
+export interface DatabaseTransaction {
+  transactionCookie: string;
+}
+
+export enum ResultLevel {
+  Full,
+  OnlyKeys,
+  OnlyCount,
+}
+
+export interface RecordGetRequest {
+  direction: BridgeIDBCursorDirection;
+  objectStoreName: string;
+  indexName: string | undefined;
+  range: BridgeIDBKeyRange | undefined;
+  lastIndexPosition?: Key;
+  lastObjectStorePosition?: Key;
+  advanceIndexKey?: Key;
+  advancePrimaryKey?: Key;
+  limit: number;
+  resultLevel: ResultLevel;
+}
+
+export interface RecordGetResponse {
+  values: Value[] | undefined;
+  keys: Key[] | undefined;
+  primaryKeys: Key[] | undefined;
+  count: number;
+}
+
+export interface RecordStoreRequest {
+  objectStoreName: string;
+  value: Value;
+  key: Key | undefined;
+  overwrite: boolean;
+}
+
+export interface Backend {
+  getDatabases(): Promise<BridgeIDBDatabaseInfo[]>;
+
+  connectDatabase(name: string): Promise<DatabaseConnection>;
+
+  beginTransaction(
+    conn: DatabaseConnection,
+    objectStores: string[],
+    mode: TransactionMode,
+  ): Promise<DatabaseTransaction>;
+
+  enterVersionChange(
+    conn: DatabaseConnection,
+    newVersion: number,
+  ): Promise<DatabaseTransaction>;
+
+  /**
+   * Even though the standard interface for indexedDB doesn't require
+   * the client to run deleteDatabase in a version transaction, there is
+   * implicitly one running. 
+   */
+  deleteDatabase(btx: DatabaseTransaction, name: string): Promise<void>;
+
+  close(db: DatabaseConnection): Promise<void>;
+
+  getSchema(db: DatabaseConnection): Schema;
+
+  renameIndex(btx: DatabaseTransaction, oldName: string, newName: string): void;
+
+  deleteIndex(btx: DatabaseTransaction, indexName: string): void;
+
+  rollback(btx: DatabaseTransaction): Promise<void>;
+
+  commit(btx: DatabaseTransaction): Promise<void>;
+
+  deleteObjectStore(btx: DatabaseTransaction, name: string): void;
+
+  createObjectStore(
+    btx: DatabaseTransaction,
+    name: string,
+    keyPath: string | string[] | null,
+    autoIncrement: boolean,
+  ): void;
+
+  renameObjectStore(
+    btx: DatabaseTransaction,
+    oldName: string,
+    newName: string,
+  ): void;
+
+  createIndex(
+    btx: DatabaseTransaction,
+    indexName: string,
+    objectStoreName: string,
+    keyPath: KeyPath,
+    multiEntry: boolean,
+    unique: boolean,
+  ): void;
+
+  deleteRecord(
+    btx: DatabaseTransaction,
+    objectStoreName: string,
+    range: BridgeIDBKeyRange,
+  ): Promise<void>;
+
+  getRecords(
+    btx: DatabaseTransaction,
+    req: RecordGetRequest,
+  ): Promise<RecordGetResponse>;
+
+  storeRecord(
+    btx: DatabaseTransaction,
+    storeReq: RecordStoreRequest,
+  ): Promise<void>;
+}
diff --git a/packages/idb-bridge/src/tree/b+tree.ts b/packages/idb-bridge/src/tree/b+tree.ts
new file mode 100644
index 000000000..01187cdc2
--- /dev/null
+++ b/packages/idb-bridge/src/tree/b+tree.ts
@@ -0,0 +1,1351 @@
+/*
+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
+
+
+import { ISortedMap, ISortedMapF } from './interfaces';
+export {
+  ISetSource, ISetSink, ISet, ISetF, ISortedSetSource, ISortedSet, ISortedSetF,
+  IMapSource, IMapSink, IMap, IMapF, ISortedMapSource, ISortedMap, ISortedMapF
+} from './interfaces';
+
+export type EditRangeResult<V,R=number> = {value?:V, break?:R, delete?:boolean};
+
+type index = number;
+
+// Informative microbenchmarks & stuff:
+// http://www.jayconrod.com/posts/52/a-tour-of-v8-object-representation (very educational)
+// https://blog.mozilla.org/luke/2012/10/02/optimizing-javascript-variable-access/ (local vars are faster than properties)
+// http://benediktmeurer.de/2017/12/13/an-introduction-to-speculative-optimization-in-v8/ (other stuff)
+// https://jsperf.com/js-in-operator-vs-alternatives (avoid 'in' operator; `.p!==undefined` faster than `hasOwnProperty('p')` in all browsers)
+// https://jsperf.com/instanceof-vs-typeof-vs-constructor-vs-member (speed of type tests varies wildly across browsers)
+// https://jsperf.com/detecting-arrays-new (a.constructor===Array is best across browsers, assuming a is an object)
+// https://jsperf.com/shallow-cloning-methods (a constructor is faster than Object.create; hand-written clone faster than Object.assign)
+// https://jsperf.com/ways-to-fill-an-array (slice-and-replace is fastest)
+// https://jsperf.com/math-min-max-vs-ternary-vs-if (Math.min/max is slow on Edge)
+// https://jsperf.com/array-vs-property-access-speed (v.x/v.y is faster than a[0]/a[1] in major browsers IF hidden class is constant)
+// https://jsperf.com/detect-not-null-or-undefined (`x==null` slightly slower than `x===null||x===undefined` on all browsers)
+// Overall, microbenchmarks suggest Firefox is the fastest browser for JavaScript and Edge is the slowest.
+// Lessons from https://v8project.blogspot.com/2017/09/elements-kinds-in-v8.html:
+//   - Avoid holes in arrays. Avoid `new Array(N)`, it will be "holey" permanently.
+//   - Don't read outside bounds of an array (it scans prototype chain).
+//   - Small integer arrays are stored differently from doubles
+//   - Adding non-numbers to an array deoptimizes it permanently into a general array
+//   - 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.
+ */
+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;   
+};
+
+/**
+ * A reasonably fast collection of key-value pairs with a powerful API. 
+ * Largely compatible with the standard Map. BTree is a B+ tree data structure,
+ * so the collection is sorted by key.
+ * 
+ * B+ trees tend to use memory more efficiently than hashtables such as the
+ * standard Map, especially when the collection contains a large number of 
+ * items. However, maintaining the sort order makes them modestly slower: 
+ * O(log size) rather than O(1). This B+ tree implementation supports O(1)
+ * fast cloning. It also supports freeze(), which can be used to ensure that
+ * a BTree is not changed accidentally.
+ * 
+ * Confusingly, the ES6 Map.forEach(c) method calls c(value,key) instead of
+ * c(key,value), in contrast to other methods such as set() and entries()
+ * which put the key first. I can only assume that the order was reversed on 
+ * the theory that users would usually want to examine values and ignore keys.
+ * BTree's forEach() therefore works the same way, but a second method 
+ * `.forEachPair((key,value)=>{...})` is provided which sends you the key
+ * first and the value second; this method is slightly faster because it is 
+ * the "native" for-each method for this class.
+ * 
+ * Out of the box, BTree supports keys that are numbers, strings, arrays of 
+ * numbers/strings, Date, and objects that have a valueOf() method returning a 
+ * number or string. Other data types, such as arrays of Date or custom
+ * objects, require a custom comparator, which you must pass as the second 
+ * argument to the constructor (the first argument is an optional list of 
+ * initial items). Symbols cannot be used as keys because they are unordered
+ * (one Symbol is never "greater" or "less" than another).
+ * 
+ * @example
+ * Given a {name: string, age: number} object, you can create a tree sorted by
+ * name and then by age like this:
+ *   
+ *     var tree = new BTree(undefined, (a, b) => {
+ *       if (a.name > b.name)
+ *         return 1; // Return a number >0 when a > b
+ *       else if (a.name < b.name)
+ *         return -1; // Return a number <0 when a < b
+ *       else // names are equal (or incomparable)
+ *         return a.age - b.age; // Return >0 when a.age > b.age
+ *     });
+ * 
+ *     tree.set({name:"Bill", age:17}, "happy");
+ *     tree.set({name:"Fran", age:40}, "busy & stressed");
+ *     tree.set({name:"Bill", age:55}, "recently laid off");
+ *     tree.forEachPair((k, v) => {
+ *       console.log(`Name: ${k.name} Age: ${k.age} Status: ${v}`);
+ *     });
+ * 
+ * @description
+ * The "range" methods (`forEach, forRange, editRange`) will return the number
+ * of elements that were scanned. In addition, the callback can return {break:R}
+ * to stop early and return R from the outer function.
+ * 
+ * - TODO: Test performance of preallocating values array at max size
+ * - TODO: Add fast initialization when a sorted array is provided to constructor
+ * 
+ * For more documentation see https://github.com/qwertie/btree-typescript
+ *
+ * Are you a C# developer? You might like the similar data structures I made for C#: 
+ * BDictionary, BList, etc. See http://core.loyc.net/collections/
+ * 
+ * @author David Piepgrass
+ */
+export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap<K,V>
+{
+  private _root: BNode<K, V> = EmptyLeaf as BNode<K,V>;
+  _size: number = 0;
+  _maxNodeSize: number;
+  _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.
+   * @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.
+   */
+  public constructor(entries?: [K,V][], compare?: (a: K, b: K) => number, maxNodeSize?: number) {
+    this._maxNodeSize = maxNodeSize! >= 4 ? Math.min(maxNodeSize!, 256) : 32;
+    this._compare = compare || defaultComparator;
+    if (entries)
+      this.setPairs(entries);
+  }
+  
+  // ES6 Map<K,V> methods ///////////////////////////////////////////////////
+
+  /** Gets the number of key-value pairs in the tree. */
+  get size() { return this._size; }
+  /** Gets the number of key-value pairs in the tree. */
+  get length() { return this._size; }
+  /** Returns true iff the tree contains no key-value pairs. */
+  get isEmpty() { return this._size === 0; }
+
+  /** Releases the tree so that its size is 0. */
+  clear() {
+    this._root = EmptyLeaf as BNode<K,V>;
+    this._size = 0;
+  }
+
+  forEach(callback: (v:V, k:K, tree:BTree<K,V>) => void, thisArg?: any): number;
+
+  /** Runs a function for each key-value pair, in order from smallest to 
+   *  largest key. For compatibility with ES6 Map, the argument order to
+   *  the callback is backwards: value first, then key. Call forEachPair 
+   *  instead to receive the key as the first argument.
+   * @param thisArg If provided, this parameter is assigned as the `this`
+   *        value for each callback.
+   * @returns the number of values that were sent to the callback,
+   *        or the R value if the callback returned {break:R}. */
+  forEach<R=number>(callback: (v:V, k:K, tree:BTree<K,V>) => {break?:R}|void, thisArg?: any): R|number {
+    if (thisArg !== undefined)
+      callback = callback.bind(thisArg);
+    return this.forEachPair((k, v) => callback(v, k, this));
+  }
+
+  /** Runs a function for each key-value pair, in order from smallest to 
+   *  largest key. The callback can return {break:R} (where R is any value
+   *  except undefined) to stop immediately and return R from forEachPair.
+   * @param onFound A function that is called for each key-value pair. This 
+   *        function can return {break:R} to stop early with result R.
+   *        The reason that you must return {break:R} instead of simply R 
+   *        itself is for consistency with editRange(), which allows 
+   *        multiple actions, not just breaking.
+   * @param initialCounter This is the value of the third argument of 
+   *        `onFound` the first time it is called. The counter increases 
+   *        by one each time `onFound` is called. Default value: 0
+   * @returns the number of pairs sent to the callback (plus initialCounter,
+   *        if you provided one). If the callback returned {break:R} then
+   *        the R value is returned instead. */
+  forEachPair<R=number>(callback: (k:K, v:V, counter:number) => {break?:R}|void, initialCounter?: number): R|number {
+    var low = this.minKey(), high = this.maxKey();
+    return this.forRange(low!, high!, true, callback, initialCounter);
+  }
+
+  /**
+   * Finds a pair in the tree and returns the associated value.
+   * @param defaultValue a value to return if the key was not found.
+   * @returns the value, or defaultValue if the key was not found.
+   * @description Computational complexity: O(log size)
+   */
+  get(key: K, defaultValue?: V): V | undefined {
+    return this._root.get(key, defaultValue, this);
+  }
+  
+  /**
+   * Adds or overwrites a key-value pair in the B+ tree.
+   * @param key the key is used to determine the sort order of
+   *        data in the tree.
+   * @param value data to associate with the key (optional)
+   * @param overwrite Whether to overwrite an existing key-value pair 
+   *        (default: true). If this is false and there is an existing
+   *        key-value pair then this method has no effect.
+   * @returns true if a new key-value pair was added.
+   * @description Computational complexity: O(log size)
+   * Note: when overwriting a previous entry, the key is updated
+   * as well as the value. This has no effect unless the new key
+   * has data that does not affect its sort order.
+   */
+  set(key: K, value: V, overwrite?: boolean): boolean { 
+    if (this._root.isShared)
+      this._root = this._root.clone();
+    var result = this._root.set(key, value, overwrite, this);
+    if (result === true || result === false)
+      return result;
+    // Root node has split, so create a new root node.
+    this._root = new BNodeInternal<K,V>([this._root, result]);
+    return true;
+  }
+
+  /**
+   * Returns true if the key exists in the B+ tree, false if not.
+   * Use get() for best performance; use has() if you need to
+   * distinguish between "undefined value" and "key not present".
+   * @param key Key to detect
+   * @description Computational complexity: O(log size)
+   */
+  has(key: K): boolean { 
+    return this.forRange(key, key, true, undefined) !== 0;
+  }
+
+  /**
+   * Removes a single key-value pair from the B+ tree.
+   * @param key Key to find
+   * @returns true if a pair was found and removed, false otherwise.
+   * @description Computational complexity: O(log size)
+   */
+  delete(key: K): boolean {
+    return this.editRange(key, key, true, DeleteRange) !== 0;
+  }
+
+  // Clone-mutators /////////////////////////////////////////////////////////
+
+  /** Returns a copy of the tree with the specified key set (the value is undefined). */
+  with(key: K): BTree<K,V|undefined>;
+  /** Returns a copy of the tree with the specified key-value pair set. */
+  with<V2>(key: K, value: V2, overwrite?: boolean): BTree<K,V|V2>;
+  with<V2>(key: K, value?: V2, overwrite?: boolean): BTree<K,V|V2|undefined> {
+    let nu = this.clone() as BTree<K,V|V2|undefined>;
+    return nu.set(key, value, overwrite) || overwrite ? nu : this;
+  }
+
+  /** Returns a copy of the tree with the specified key-value pairs set. */
+  withPairs<V2>(pairs: [K,V|V2][], overwrite: boolean): BTree<K,V|V2> {
+    let nu = this.clone() as BTree<K,V|V2>;
+    return nu.setPairs(pairs, overwrite) !== 0 || overwrite ? nu : this;
+  }
+
+  /** Returns a copy of the tree with the specified keys present. 
+   *  @param keys The keys to add. If a key is already present in the tree,
+   *         neither the existing key nor the existing value is modified.
+   *  @param returnThisIfUnchanged if true, returns this if all keys already 
+   *  existed. Performance note: due to the architecture of this class, all
+   *  node(s) leading to existing keys are cloned even if the collection is
+   *  ultimately unchanged.
+  */
+  withKeys(keys: K[], returnThisIfUnchanged?: boolean): BTree<K,V|undefined> {
+    let nu = this.clone() as BTree<K,V|undefined>, changed = false;
+    for (var i = 0; i < keys.length; i++)
+      changed = nu.set(keys[i], undefined, false) || changed;
+    return returnThisIfUnchanged && !changed ? this : nu;
+  }
+
+  /** Returns a copy of the tree with the specified key removed. 
+   * @param returnThisIfUnchanged if true, returns this if the key didn't exist.
+   *  Performance note: due to the architecture of this class, node(s) leading
+   *  to where the key would have been stored are cloned even when the key
+   *  turns out not to exist and the collection is unchanged.
+   */
+  without(key: K, returnThisIfUnchanged?: boolean): BTree<K,V> {
+    return this.withoutRange(key, key, true, returnThisIfUnchanged);
+  }
+
+  /** Returns a copy of the tree with the specified keys removed.
+   * @param returnThisIfUnchanged if true, returns this if none of the keys
+   *  existed. Performance note: due to the architecture of this class,
+   *  node(s) leading to where the key would have been stored are cloned
+   *  even when the key turns out not to exist.
+   */
+  withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): BTree<K,V> {
+    let nu = this.clone();
+    return nu.deleteKeys(keys) || !returnThisIfUnchanged ? nu : this;
+  }
+
+  /** Returns a copy of the tree with the specified range of keys removed. */
+  withoutRange(low: K, high: K, includeHigh: boolean, returnThisIfUnchanged?: boolean): BTree<K,V> {
+    let nu = this.clone();
+    if (nu.deleteRange(low, high, includeHigh) === 0 && returnThisIfUnchanged)
+      return this;
+    return nu;
+  }
+
+  /** Returns a copy of the tree with pairs removed whenever the callback 
+   *  function returns false. `where()` is a synonym for this method. */
+  filter(callback: (k:K,v:V,counter:number) => boolean, returnThisIfUnchanged?: boolean): BTree<K,V> {
+    var nu = this.greedyClone();
+    var del: any;
+    nu.editAll((k,v,i) => {
+      if (!callback(k, v, i)) return del = Delete;
+    });
+    if (!del && returnThisIfUnchanged)
+      return this;
+    return nu;
+  }
+
+  /** Returns a copy of the tree with all values altered by a callback function. */
+  mapValues<R>(callback: (v:V,k:K,counter:number) => R): BTree<K,R> {
+    var tmp = {} as {value:R};
+    var nu = this.greedyClone();
+    nu.editAll((k,v,i) => {
+      return tmp.value = callback(v, k, i), tmp as any;
+    });
+    return nu as any as BTree<K,R>;
+  }
+
+  /** Performs a reduce operation like the `reduce` method of `Array`. 
+   *  It is used to combine all pairs into a single value, or perform 
+   *  conversions. `reduce` is best understood by example. For example,
+   *  `tree.reduce((P, pair) => P * pair[0], 1)` multiplies all keys 
+   *  together. It means "start with P=1, and for each pair multiply 
+   *  it by the key in pair[0]". Another example would be converting 
+   *  the tree to a Map (in this example, note that M.set returns M):
+   *  
+   *  var M = tree.reduce((M, pair) => M.set(pair[0],pair[1]), new Map())
+   *  
+   *  **Note**: the same array is sent to the callback on every iteration.
+   */
+  reduce<R>(callback: (previous:R,currentPair:[K,V],counter:number,tree:BTree<K,V>) => R, initialValue: R): R;
+  reduce<R>(callback: (previous:R|undefined,currentPair:[K,V],counter:number,tree:BTree<K,V>) => R): R|undefined;
+  reduce<R>(callback: (previous:R|undefined,currentPair:[K,V],counter:number,tree:BTree<K,V>) => R, initialValue?: R): R|undefined {
+    let i = 0, p = initialValue;
+    var it = this.entries(this.minKey(), ReusedArray), next;
+    while (!(next = it.next()).done)
+      p = callback(p, next.value, i++, this);
+    return p;
+  }
+
+  // Iterator methods ///////////////////////////////////////////////////////
+
+  /** Returns an iterator that provides items in order (ascending order if
+   *  the collection's comparator uses ascending order, as is the default.)
+   *  @param lowestKey First key to be iterated, or undefined to start at
+   *         minKey(). If the specified key doesn't exist then iteration
+   *         starts at the next higher 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.
+   */
+  entries(lowestKey?: K, reusedArray?: (K|V)[]): IterableIterator<[K,V]> {
+    var info = this.findPath(lowestKey);
+    if (info === undefined) return iterator<[K,V]>();
+    var {nodequeue, nodeindex, leaf} = info;
+    var state = reusedArray !== undefined ? 1 : 0;
+    var i = (lowestKey === undefined ? -1 : leaf.indexOf(lowestKey, 0, this._compare) - 1);
+
+    return iterator<[K,V]>(() => {
+      jump: for (;;) {
+        switch(state) {
+          case 0:
+            if (++i < leaf.keys.length)
+              return {done: false, value: [leaf.keys[i], leaf.values[i]]};
+            state = 2;
+            continue;
+          case 1:
+            if (++i < leaf.keys.length) {
+              reusedArray![0] = leaf.keys[i], reusedArray![1] = leaf.values[i];
+              return {done: false, value: reusedArray as [K,V]};
+            }
+            state = 2;
+          case 2:
+            // Advance to the next leaf node
+            for (var level = -1;;) {
+              if (++level >= nodequeue.length) {
+                state = 3; continue jump;
+              }
+              if (++nodeindex[level] < nodequeue[level].length)
+                break;
+            }
+            for (; level > 0; level--) {
+              nodequeue[level-1] = (nodequeue[level][nodeindex[level]] as BNodeInternal<K,V>).children;
+              nodeindex[level-1] = 0;
+            }
+            leaf = nodequeue[0][nodeindex[0]];
+            i = -1;
+            state = reusedArray !== undefined ? 1 : 0;
+            continue;
+          case 3:
+            return {done: true, value: undefined};
+        }
+      }
+    });
+  }
+
+  /** 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
+   *         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.
+   *  @param skipHighest Iff this flag is true and the highestKey exists in the
+   *         collection, the pair matching highestKey is skipped, not iterated.
+   */
+  entriesReversed(highestKey?: K, reusedArray?: (K|V)[], skipHighest?: boolean): IterableIterator<[K,V]> {
+    if ((highestKey = highestKey || this.maxKey()) === 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++;
+    var state = reusedArray !== undefined ? 1 : 0;
+
+    return iterator<[K,V]>(() => {
+      jump: for (;;) {
+        switch(state) {
+          case 0:
+            if (--i >= 0)
+              return {done: false, value: [leaf.keys[i], leaf.values[i]]};
+            state = 2;
+            continue;
+          case 1:
+            if (--i >= 0) {
+              reusedArray![0] = leaf.keys[i], reusedArray![1] = leaf.values[i];
+              return {done: false, value: reusedArray as [K,V]};
+            }
+            state = 2;
+          case 2:
+            // Advance to the next leaf node
+            for (var level = -1;;) {
+              if (++level >= nodequeue.length) {
+                state = 3; continue jump;
+              }
+              if (--nodeindex[level] >= 0)
+                break;
+            }
+            for (; level > 0; level--) {
+              nodequeue[level-1] = (nodequeue[level][nodeindex[level]] as BNodeInternal<K,V>).children;
+              nodeindex[level-1] = nodequeue[level-1].length-1;
+            }
+            leaf = nodequeue[0][nodeindex[0]];
+            i = leaf.keys.length;
+            state = reusedArray !== undefined ? 1 : 0;
+            continue;
+          case 3:
+            return {done: true, value: undefined};
+        }
+      }
+    });
+  }
+
+  /* Used by entries() and entriesReversed() to prepare to start iterating.
+   * It develops a "node queue" for each non-leaf level of the tree.
+   * Levels are numbered "bottom-up" so that level 0 is a list of leaf 
+   * nodes from a low-level non-leaf node. The queue at a given level L
+   * consists of nodequeue[L] which is the children of a BNodeInternal, 
+   * and nodeindex[L], the current index within that child list, such
+   * such that nodequeue[L-1] === nodequeue[L][nodeindex[L]].children.
+   * (However inside this function the order is reversed.)
+   */
+  private findPath(key?: K): { nodequeue: BNode<K,V>[][], nodeindex: number[], leaf: BNode<K,V> } | undefined
+  {
+    var nextnode = this._root;
+    var nodequeue: BNode<K,V>[][], nodeindex: number[];
+
+    if (nextnode.isLeaf) {
+      nodequeue = EmptyArray, nodeindex = EmptyArray; // avoid allocations
+    } else {
+      nodequeue = [], nodeindex = [];
+      for (var d = 0; !nextnode.isLeaf; d++) {
+        nodequeue[d] = (nextnode as BNodeInternal<K,V>).children;
+        nodeindex[d] = key === undefined ? 0 : nextnode.indexOf(key, 0, this._compare);
+        if (nodeindex[d] >= nodequeue[d].length)
+          return; // first key > maxKey()
+        nextnode = nodequeue[d][nodeindex[d]];
+      }
+      nodequeue.reverse();
+      nodeindex.reverse();
+    }
+    return {nodequeue, nodeindex, leaf:nextnode};
+  }
+
+  /** 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> {
+    var it = this.entries(firstKey, ReusedArray);
+    return iterator<K>(() => {
+      var n: IteratorResult<any> = it.next();
+      if (n.value) n.value = n.value[0];
+      return n;
+    });
+  }
+  
+  /** Returns a new iterator for iterating the values of each pair in order by key. 
+   *  @param firstKey: Minimum key whose associated value is included in the output. */
+  values(firstKey?: K): IterableIterator<V> {
+    var it = this.entries(firstKey, ReusedArray);
+    return iterator<V>(() => {
+      var n: IteratorResult<any> = it.next();
+      if (n.value) n.value = n.value[1];
+      return n;
+    });
+  }
+
+  // Additional methods /////////////////////////////////////////////////////
+
+  /** Returns the maximum number of children/values before nodes will split. */
+  get maxNodeSize() {
+    return this._maxNodeSize;
+  }
+
+  /** Gets the lowest key in the tree. Complexity: O(log size) */
+  minKey(): K | undefined { return this._root.minKey(); }
+  
+  /** Gets the highest key in the tree. Complexity: O(1) */
+  maxKey(): K | undefined { return this._root.maxKey(); }
+
+  /** Quickly clones the tree by marking the root node as shared. 
+   *  Both copies remain editable. When you modify either copy, any
+   *  nodes that are shared (or potentially shared) between the two
+   *  copies are cloned so that the changes do not affect other copies.
+   *  This is known as copy-on-write behavior, or "lazy copying". */
+  clone(): BTree<K,V> {
+    this._root.isShared = true;
+    var result = new BTree<K,V>(undefined, this._compare, this._maxNodeSize);
+    result._root = this._root;
+    result._size = this._size;
+    return result;
+  }
+
+  /** Performs a greedy clone, immediately duplicating any nodes that are 
+   *  not currently marked as shared, in order to avoid marking any nodes
+   *  as shared.
+   *  @param force Clone all nodes, even shared ones.
+   */
+  greedyClone(force?: boolean): BTree<K,V> {
+    var result = new BTree<K,V>(undefined, this._compare, this._maxNodeSize);
+    result._root = this._root.greedyClone(force);
+    result._size = this._size;
+    return result;
+  }
+
+  /** Gets an array filled with the contents of the tree, sorted by key */
+  toArray(maxLength: number = 0x7FFFFFFF): [K,V][] {
+    let min = this.minKey(), max = this.maxKey();
+    if (min !== undefined)
+      return this.getRange(min, max!, true, maxLength)
+    return [];
+  }
+
+  /** Gets an array of all keys, sorted */
+  keysArray() {
+    var results: K[] = [];
+    this._root.forRange(this.minKey()!, this.maxKey()!, true, false, this, 0, 
+      (k,v) => { results.push(k); });
+    return results;
+  }
+  
+  /** Gets an array of all values, sorted by key */
+  valuesArray() {
+    var results: V[] = [];
+    this._root.forRange(this.minKey()!, this.maxKey()!, true, false, this, 0,
+      (k,v) => { results.push(v); });
+    return results;
+  }
+
+  /** Gets a string representing the tree's data based on toArray(). */
+  toString() {
+    return this.toArray().toString();
+  }
+
+  /** Stores a key-value pair only if the key doesn't already exist in the tree. 
+   * @returns true if a new key was added
+  */
+  setIfNotPresent(key: K, value: V): boolean {
+    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 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 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 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;
+  }
+
+  /** Edits the value associated with a key in the tree, if it already exists. 
+   * @returns true if the key existed, false if not.
+  */
+  changeIfPresent(key: K, value: V): boolean { 
+    return this.editRange(key, key, true, (k,v) => ({value})) !== 0;
+  }
+
+  /**
+   * Builds an array of pairs from the specified range of keys, sorted by key.
+   * Each returned pair is also an array: pair[0] is the key, pair[1] is the value.
+   * @param low The first key in the array will be greater than or equal to `low`.
+   * @param high This method returns when a key larger than this is reached.
+   * @param includeHigh If the `high` key is present, its pair will be included
+   *        in the output if and only if this parameter is true. Note: if the
+   *        `low` key is present, it is always included in the output.
+   * @param maxLength Length limit. getRange will stop scanning the tree when 
+   *                  the array reaches this size.
+   * @description Computational complexity: O(result.length + log size)
+   */
+  getRange(low: K, high: K, includeHigh?: boolean, maxLength: number = 0x3FFFFFF): [K,V][] {
+    var results: [K,V][] = [];
+    this._root.forRange(low, high, includeHigh, false, this, 0, (k,v) => {
+      results.push([k,v])
+      return results.length > maxLength ? Break : undefined;
+    });
+    return results;
+  }
+
+  /** Adds all pairs from a list of key-value pairs.
+   * @param pairs Pairs to add to this tree. If there are duplicate keys, 
+   *        later pairs currently overwrite earlier ones (e.g. [[0,1],[0,7]] 
+   *        associates 0 with 7.)
+   * @param overwrite Whether to overwrite pairs that already exist (if false,
+   *        pairs[i] is ignored when the key pairs[i][0] already exists.)
+   * @returns The number of pairs added to the collection.
+   * @description Computational complexity: O(pairs.length * log(size + pairs.length))
+   */
+  setPairs(pairs: [K,V][], overwrite?: boolean): number {
+    var added = 0;
+    for (var i = 0; i < pairs.length; i++)
+      if (this.set(pairs[i][0], pairs[i][1], overwrite))
+        added++;
+    return added;
+  }
+
+  forRange(low: K, high: K, includeHigh: boolean, onFound?: (k:K,v:V,counter:number) => void, initialCounter?: number): number;
+
+  /**
+   * Scans the specified range of keys, in ascending order by key.
+   * Note: the callback `onFound` must not insert or remove items in the
+   * collection. Doing so may cause incorrect data to be sent to the 
+   * callback afterward.
+   * @param low The first key scanned will be greater than or equal to `low`.
+   * @param high Scanning stops when a key larger than this is reached.
+   * @param includeHigh If the `high` key is present, `onFound` is called for
+   *        that final pair if and only if this parameter is true.
+   * @param onFound A function that is called for each key-value pair. This 
+   *        function can return {break:R} to stop early with result R.
+   * @param initialCounter Initial third argument of onFound. This value 
+   *        increases by one each time `onFound` is called. Default: 0
+   * @returns The number of values found, or R if the callback returned 
+   *        `{break:R}` to stop early.
+   * @description Computational complexity: O(number of items scanned + log size)
+   */
+  forRange<R=number>(low: K, high: K, includeHigh: boolean, onFound?: (k:K,v:V,counter:number) => {break?:R}|void, initialCounter?: number): R|number {
+    var r = this._root.forRange(low, high, includeHigh, false, this, initialCounter || 0, onFound);
+    return typeof r === "number" ? r : r.break!;
+  }
+
+  /**
+   * Scans and potentially modifies values for a subsequence of keys.
+   * Note: the callback `onFound` should ideally be a pure function. 
+   *   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 
+   *   clone() of the collection, otherwise the clone could be modified
+   *   by changes requested by the callback.
+   * @param low The first key scanned will be greater than or equal to `low`.
+   * @param high Scanning stops when a key larger than this is reached.
+   * @param includeHigh If the `high` key is present, `onFound` is called for
+   *        that final pair if and only if this parameter is true.
+   * @param onFound A function that is called for each key-value pair. This 
+   *        function can return `{value:v}` to change the value associated 
+   *        with the current key, `{delete:true}` to delete the current pair,
+   *        `{break:R}` to stop early with result R, or it can return nothing
+   *        (undefined or {}) to cause no effect and continue iterating.
+   *        `{break:R}` can be combined with one of the other two commands.
+   *        The third argument `counter` is the number of items iterated 
+   *        previously; it equals 0 when `onFound` is called the first time.
+   * @returns The number of values scanned, or R if the callback returned 
+   *        `{break:R}` to stop early.
+   * @description 
+   *   Computational complexity: O(number of items scanned + log size)
+   *   Note: if the tree has been cloned with clone(), any shared
+   *   nodes are copied before `onFound` is called. This takes O(n) time 
+   *   where n is proportional to the amount of shared data scanned.
+   */
+  editRange<R=V>(low: K, high: K, includeHigh: boolean, onFound: (k:K,v:V,counter:number) => EditRangeResult<V,R>|void, initialCounter?: number): R|number {
+    var root = this._root;
+    if (root.isShared)
+      this._root = root = root.clone();
+    try {
+      var r = root.forRange(low, high, includeHigh, true, this, initialCounter || 0, onFound);
+      return typeof r === "number" ? r : r.break!;
+    } finally {
+      while (root.keys.length <= 1 && !root.isLeaf)
+        this._root = root = root.keys.length === 0 ? EmptyLeaf :
+                    (root as any as BNodeInternal<K,V>).children[0];
+    }
+  }
+
+  /** Same as `editRange` except that the callback is called for all pairs. */
+  editAll<R=V>(onFound: (k:K,v:V,counter:number) => EditRangeResult<V,R>|void, initialCounter?: number): R|number {
+    return this.editRange(this.minKey()!, this.maxKey()!, true, onFound, initialCounter);
+  }
+
+  /**
+   * Removes a range of key-value pairs from the B+ tree.
+   * @param low The first key scanned will be greater than or equal to `low`.
+   * @param high Scanning stops when a key larger than this is reached.
+   * @param includeHigh Specifies whether the `high` key, if present, is deleted.
+   * @returns The number of key-value pairs that were deleted.
+   * @description Computational complexity: O(log size + number of items deleted)
+   */
+  deleteRange(low: K, high: K, includeHigh: boolean): number {
+    return this.editRange(low, high, includeHigh, DeleteRange);
+  }
+
+  /** Deletes a series of keys from the collection. */
+  deleteKeys(keys: K[]): number {
+    for (var i = 0, r = 0; i < keys.length; i++)
+      if (this.delete(keys[i]))
+        r++;
+    return r;
+  }
+
+  /** 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;
+  }
+
+  /** Makes the object read-only to ensure it is not accidentally modified.
+   *  Freezing does not have to be permanent; unfreeze() reverses the effect.
+   *  This is accomplished by replacing mutator functions with a function 
+   *  that throws an Error. Compared to using a property (e.g. this.isFrozen) 
+   *  this implementation gives better performance in non-frozen BTrees.
+   */
+  freeze() {
+    var t = this as any;
+    // Note: all other mutators ultimately call set() or editRange() 
+    //       so we don't need to override those others.
+    t.clear = t.set = t.editRange = function() {
+      throw new Error("Attempted to modify a frozen BTree");
+    };
+  }
+
+  /** Ensures mutations are allowed, reversing the effect of freeze(). */
+  unfreeze() {
+    delete this.clear;
+    delete this.set;
+    delete this.editRange;
+  }
+
+  /** Returns true if the tree appears to be frozen. */
+  get isFrozen() {
+    return this.hasOwnProperty('editRange');
+  }
+
+  /** Scans the tree for signs of serious bugs (e.g. this.size doesn't match
+   *  number of elements, internal nodes not caching max element properly...)
+   *  Computational complexity: O(number of nodes), i.e. O(size). This method
+   *  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);
+    check(size === this.size, "size mismatch: counted ", size, "but stored", this.size);
+  }
+}
+
+declare const Symbol: any;
+if (Symbol && Symbol.iterator) // iterator is equivalent to entries()
+  (BTree as any).prototype[Symbol.iterator] = BTree.prototype.entries;
+(BTree as any).prototype.where = BTree.prototype.filter;
+(BTree as any).prototype.setRange = BTree.prototype.setPairs;
+(BTree as any).prototype.add = BTree.prototype.set;
+
+function iterator<T>(next: () => {done:boolean,value?:T} = (() => ({ done:true, value:undefined }))): IterableIterator<T> {
+  var result: any = { next };
+  if (Symbol && Symbol.iterator)
+    result[Symbol.iterator] = function() { return this; };
+  return result;
+}
+  
+
+/** Leaf node / base class. **************************************************/
+class BNode<K,V> {
+  // If this is an internal node, _keys[i] is the highest key in children[i].
+  keys: K[];
+  values: V[];
+  isShared: true | undefined;
+  get isLeaf() { return (this as any).children === undefined; }
+  
+  constructor(keys: K[] = [], values?: V[]) {
+    this.keys = keys;
+    this.values = values || undefVals as any[];
+    this.isShared = undefined;
+  }
+
+  // Shared methods /////////////////////////////////////////////////////////
+
+  maxKey() {
+    return this.keys[this.keys.length-1];
+  }
+
+  // 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, mid = hi >> 1;
+    while(lo < hi) {
+      var c = cmp(keys[mid], key);
+      if (c < 0)
+        lo = mid + 1;
+      else if (c > 0) // key < keys[mid]
+        hi = mid;
+      else if (c === 0)
+        return mid;
+      else {
+        // c is NaN or otherwise invalid
+        if (key === key) // at least the search key is not NaN
+          return keys.length;
+        else
+          throw new Error("BTree: NaN was used as a key");
+      }
+      mid = (lo + hi) >> 1;
+    }
+    return mid ^ failXor;
+
+    // Unrolled version: benchmarks show same speed, not worth using
+    /*var i = 1, c: number = 0, sum = 0;
+    if (keys.length >= 4) {
+      i = 3;
+      if (keys.length >= 8) {
+        i = 7;
+        if (keys.length >= 16) {
+          i = 15;
+          if (keys.length >= 32) {
+            i = 31;
+            if (keys.length >= 64) {
+              i = 127;
+              i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 64 : -64;
+              sum += c;
+              i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 32 : -32;
+              sum += c;
+            }
+            i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 16 : -16;
+            sum += c;
+          }
+          i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 8 : -8;
+          sum += c;
+        }
+        i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 4 : -4;
+        sum += c;
+      }
+      i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 2 : -2;
+      sum += c;
+    }
+    i += (c = i < keys.length ? cmp(keys[i], key) : 1) < 0 ? 1 : -1;
+    c = i < keys.length ? cmp(keys[i], key) : 1;
+    sum += c;
+    if (c < 0) {
+      ++i;
+      c = i < keys.length ? cmp(keys[i], key) : 1;
+      sum += c;
+    }
+    if (sum !== sum) {
+      if (key === key) // at least the search key is not NaN
+        return keys.length ^ failXor;
+      else
+        throw new Error("BTree: NaN was used as a key");
+    }
+    return c === 0 ? i : i ^ failXor;*/
+  }
+
+  // Leaf Node: misc //////////////////////////////////////////////////////////
+
+  minKey() {
+    return this.keys[0];
+  }
+
+  clone(): BNode<K,V> {
+    var v = this.values;
+    return new BNode<K,V>(this.keys.slice(0), v === undefVals ? v : v.slice(0));
+  }
+
+  greedyClone(force?: boolean): BNode<K,V> {
+    return this.isShared && !force ? this : this.clone();
+  }
+
+  get(key: K, defaultValue: V|undefined, tree: BTree<K,V>): V|undefined {
+    var i = this.indexOf(key, -1, tree._compare);
+    return i < 0 ? defaultValue : this.values[i];
+  }
+
+  checkValid(depth: number, tree: BTree<K,V>): number {
+    var kL = this.keys.length, vL = this.values.length;
+    check(this.values === undefVals ? kL <= vL : kL === vL,
+      "keys/values length mismatch: depth", depth, "with lengths", kL, vL);
+    // 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);
+    return kL;
+  }
+
+  // Leaf Node: set & node splitting //////////////////////////////////////////
+
+  set(key: K, value: V, overwrite: boolean|undefined, tree: BTree<K,V>): boolean|BNode<K,V> { 
+    var i = this.indexOf(key, -1, tree._compare);
+    if (i < 0) {
+      // key does not exist yet
+      i = ~i;
+      tree._size++;
+      
+      if (this.keys.length < tree._maxNodeSize) {
+        return this.insertInLeaf(i, key, value, tree);
+      } else {
+        // This leaf node is full and must split
+        var newRightSibling = this.splitOffRightSide(), target: BNode<K,V> = this;
+        if (i > this.keys.length) {
+          i -= this.keys.length;
+          target = newRightSibling;
+        }
+        target.insertInLeaf(i, key, value, tree);
+        return newRightSibling;
+      }
+    } else {
+      // Key already exists
+      if (overwrite !== false) {
+        if (value !== undefined)
+          this.reifyValues();
+        // usually this is a no-op, but some users may wish to edit the key
+        this.keys[i] = key;
+        this.values[i] = value;
+      }
+      return false;
+    }
+  }
+
+  reifyValues() {
+    if (this.values === undefVals)
+      return this.values = this.values.slice(0, this.keys.length);
+    return this.values;
+  }
+
+  insertInLeaf(i: index, key: K, value: V, tree: BTree<K,V>) {
+    this.keys.splice(i, 0, key);
+    if (this.values === undefVals) {
+      while (undefVals.length < tree._maxNodeSize)
+        undefVals.push(undefined);
+      if (value === undefined) {
+        return true;
+      } else {
+        this.values = undefVals.slice(0, this.keys.length - 1);
+      }
+    }
+    this.values.splice(i, 0, value);
+    return true;
+  }
+  
+  takeFromRight(rhs: BNode<K,V>) {
+    // Reminder: parent node must update its copy of key for this node
+    // assert: neither node is shared
+    // assert rhs.keys.length > (maxNodeSize/2 && this.keys.length<maxNodeSize)
+    var v = this.values;
+    if (rhs.values === undefVals) {
+      if (v !== undefVals)
+        v.push(undefined as any);
+    } else {
+      v = this.reifyValues();
+      v.push(rhs.values.shift()!);
+    }
+    this.keys.push(rhs.keys.shift()!);
+  }
+
+  takeFromLeft(lhs: BNode<K,V>) {
+    // Reminder: parent node must update its copy of key for this node
+    // assert: neither node is shared
+    // assert rhs.keys.length > (maxNodeSize/2 && this.keys.length<maxNodeSize)
+    var v = this.values;
+    if (lhs.values === undefVals) {
+      if (v !== undefVals)
+        v.unshift(undefined as any);
+    } else {
+      v = this.reifyValues();
+      v.unshift(lhs.values.pop()!);
+    }
+    this.keys.unshift(lhs.keys.pop()!);
+  }
+
+  splitOffRightSide(): BNode<K,V> {
+    // Reminder: parent node must update its copy of key for this node
+    var half = this.keys.length >> 1, keys = this.keys.splice(half);
+    var values = this.values === undefVals ? undefVals : this.values.splice(half);
+    return new BNode<K,V>(keys, values);
+  }
+
+  // Leaf Node: scanning & deletions //////////////////////////////////////////
+
+  forRange<R>(low: K, high: K, includeHigh: boolean|undefined, editMode: boolean, tree: BTree<K,V>, count: number,
+              onFound?: (k:K, v:V, counter:number) => EditRangeResult<V,R>|void): EditRangeResult<V,R>|number {
+    var cmp = tree._compare;
+    var iLow, iHigh;
+    if (high === low) {
+      if (!includeHigh)
+        return count;
+      iHigh = (iLow = this.indexOf(low, -1, cmp)) + 1;
+      if (iLow < 0)
+        return count;
+    } else {
+      iLow = this.indexOf(low, 0, cmp);
+      iHigh = this.indexOf(high, -1, cmp);
+      if (iHigh < 0)
+        iHigh = ~iHigh;
+      else if (includeHigh === true)
+        iHigh++;
+    }
+    var keys = this.keys, values = this.values;
+    if (onFound !== undefined) {
+      for(var i = iLow; i < iHigh; i++) {
+        var key = keys[i];
+        var result = onFound(key, values[i], count++);
+        if (result !== undefined) {
+          if (editMode === true) {
+            if (key !== keys[i] || this.isShared === true)
+              throw new Error("BTree illegally changed or cloned in editRange");
+            if (result.delete) {
+              this.keys.splice(i, 1);
+              if (this.values !== undefVals)
+                this.values.splice(i, 1);
+              tree._size--;
+              i--;
+              iHigh--;
+            } else if (result.hasOwnProperty('value')) {
+              values![i] = result.value!;
+            }
+          }
+          if (result.break !== undefined)
+            return result;
+        }
+      }
+    } else
+      count += iHigh - iLow;
+    return count;
+  }
+
+  /** Adds entire contents of right-hand sibling (rhs is left unchanged) */
+  mergeSibling(rhs: BNode<K,V>, _: number) {
+    this.keys.push.apply(this.keys, rhs.keys);
+    if (this.values === undefVals) {
+      if (rhs.values === undefVals)
+        return;
+      this.values = this.values.slice(0, this.keys.length);
+    }
+    this.values.push.apply(this.values, rhs.reifyValues());
+  }
+}
+
+/** Internal node (non-leaf node) ********************************************/
+class BNodeInternal<K,V> extends BNode<K,V> {
+  // Note: conventionally B+ trees have one fewer key than the number of 
+  // children, but I find it easier to keep the array lengths equal: each
+  // keys[i] caches the value of children[i].maxKey().
+  children: BNode<K,V>[];
+
+  constructor(children: BNode<K,V>[], keys?: K[]) {
+    if (!keys) {
+      keys = [];
+      for (var i = 0; i < children.length; i++)
+        keys[i] = children[i].maxKey();
+    }
+    super(keys);
+    this.children = children;
+  }
+
+  clone(): BNode<K,V> {
+    var children = this.children.slice(0);
+    for (var i = 0; i < children.length; i++)
+      children[i].isShared = true;
+    return new BNodeInternal<K,V>(children, this.keys.slice(0));
+  }
+
+  greedyClone(force?: boolean): BNode<K,V> {
+    if (this.isShared && !force)
+      return this;
+    var nu = new BNodeInternal<K,V>(this.children.slice(0), this.keys.slice(0));
+    for (var i = 0; i < nu.children.length; i++)
+      nu.children[i] = nu.children[i].greedyClone();
+    return nu;
+  }
+
+  minKey() {
+    return this.children[0].minKey();
+  }
+
+  get(key: K, defaultValue: V|undefined, tree: BTree<K,V>): V|undefined {
+    var i = this.indexOf(key, 0, tree._compare), children = this.children;
+    return i < children.length ? children[i].get(key, defaultValue, tree) : undefined;
+  }
+
+  checkValid(depth: number, tree: BTree<K,V>) : number {
+    var kL = this.keys.length, cL = this.children.length;
+    check(kL === cL, "keys/children length mismatch: depth", depth, "lengths", kL, cL);
+    check(kL > 1, "internal node has length", kL, "at depth", depth);
+    var size = 0, c = this.children, k = this.keys, childSize = 0;
+    for (var i = 0; i < cL; i++) {
+      size += c[i].checkValid(depth + 1, tree);
+      childSize += c[i].keys.length;
+      check(size >= childSize, "wtf"); // no way this will ever fail
+      check(i === 0 || c[i-1].constructor === c[i].constructor, "type mismatch");
+      if (c[i].maxKey() != k[i])
+        check(false, "keys[", i, "] =", k[i], "is wrong, should be ", c[i].maxKey(), "at depth", depth);
+      if (!(i === 0 || tree._compare(k[i-1], k[i]) < 0))
+        check(false, "sort violation at depth", depth, "index", i, "keys", k[i-1], k[i]);
+    }
+    var toofew = childSize < (tree.maxNodeSize >> 1)*cL;
+    if (toofew || childSize > tree.maxNodeSize*cL)
+      check(false, toofew ? "too few" : "too many", "children (", childSize, size, ") at depth", depth, ", maxNodeSize:", tree.maxNodeSize, "children.length:", cL);
+    return size;
+  }
+
+  // Internal Node: set & node splitting //////////////////////////////////////
+
+  set(key: K, value: V, overwrite: boolean|undefined, tree: BTree<K,V>): boolean|BNodeInternal<K,V> {
+    var c = this.children, max = tree._maxNodeSize, cmp = tree._compare;
+    var i = Math.min(this.indexOf(key, 0, cmp), c.length - 1), child = c[i];
+    
+    if (child.isShared)
+      c[i] = child = child.clone();
+    if (child.keys.length >= max) {
+      // child is full; inserting anything else will cause a split.
+      // Shifting an item to the left or right sibling may avoid a split.
+      // We can do a shift if the adjacent node is not full and if the
+      // current key can still be placed in the same node after the shift.
+      var other: BNode<K,V>;
+      if (i > 0 && (other = c[i-1]).keys.length < max && cmp(child.keys[0], key) < 0) {
+        if (other.isShared)
+          c[i-1] = other = other.clone();
+        other.takeFromRight(child);
+        this.keys[i-1] = other.maxKey();
+      } else if ((other = c[i+1]) !== undefined && other.keys.length < max && cmp(child.maxKey(), key) < 0) {
+        if (other.isShared)
+          c[i+1] = other = other.clone();
+        other.takeFromLeft(child);
+        this.keys[i] = c[i].maxKey();
+      }
+    }
+
+    var result = child.set(key, value, overwrite, tree);
+    if (result === false)
+      return false;
+    this.keys[i] = child.maxKey();
+    if (result === true)
+      return true;
+
+    // The child has split and `result` is a new right child... does it fit?
+    if (this.keys.length < max) { // yes
+      this.insert(i+1, result);
+      return true;
+    } else { // no, we must split also
+      var newRightSibling = this.splitOffRightSide(), target: BNodeInternal<K,V> = this;
+      if (cmp(result.maxKey(), this.maxKey()) > 0) {
+        target = newRightSibling;
+        i -= this.keys.length;
+      }
+      target.insert(i+1, result);
+      return newRightSibling;
+    }
+  }
+
+  insert(i: index, child: BNode<K,V>) {
+    this.children.splice(i, 0, child);
+    this.keys.splice(i, 0, child.maxKey());
+  }
+
+  splitOffRightSide() {
+    var half = this.children.length >> 1;
+    return new BNodeInternal<K,V>(this.children.splice(half), this.keys.splice(half));
+  }
+
+  takeFromRight(rhs: BNode<K,V>) {
+    // Reminder: parent node must update its copy of key for this node
+    // assert: neither node is shared
+    // assert rhs.keys.length > (maxNodeSize/2 && this.keys.length<maxNodeSize)
+    this.keys.push(rhs.keys.shift()!);
+    this.children.push((rhs as BNodeInternal<K,V>).children.shift()!);
+  }
+
+  takeFromLeft(lhs: BNode<K,V>) {
+    // Reminder: parent node must update its copy of key for this node
+    // assert: neither node is shared
+    // assert rhs.keys.length > (maxNodeSize/2 && this.keys.length<maxNodeSize)
+    this.keys.unshift(lhs.keys.pop()!);
+    this.children.unshift((lhs as BNodeInternal<K,V>).children.pop()!);
+  }
+
+  // Internal Node: scanning & deletions //////////////////////////////////////
+
+  forRange<R>(low: K, high: K, includeHigh: boolean|undefined, editMode: boolean, tree: BTree<K,V>, count: number,
+    onFound?: (k:K, v:V, counter:number) => EditRangeResult<V,R>|void): EditRangeResult<V,R>|number
+  {
+    var cmp = tree._compare;
+    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);
+    var keys = this.keys, children = this.children;
+    if (!editMode) {
+      // Simple case
+      for(; i <= iHigh; i++) {
+        var result = children[i].forRange(low, high, includeHigh, editMode, tree, count, onFound);
+        if (typeof result !== 'number')
+          return result;
+        count = result;
+      }
+    } else if (i <= iHigh) {
+      try {
+        for(; i <= iHigh; i++) {
+          if (children[i].isShared)
+            children[i] = children[i].clone();
+          var result = children[i].forRange(low, high, includeHigh, editMode, tree, count, onFound);
+          keys[i] = children[i].maxKey();
+          if (typeof result !== 'number')
+            return result;
+          count = result;
+        }
+      } finally {
+        // Deletions may have occurred, so look for opportunities to merge nodes.
+        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();
+        }
+      }
+    }
+    return count;
+  }
+
+  /** Merges child i with child i+1 if their combined size is not too large */
+  tryMerge(i: index, maxSize: number): boolean {
+    var children = this.children;
+    if (i >= 0 && i + 1 < children.length) {
+      if (children[i].keys.length + children[i+1].keys.length <= maxSize) {
+        if (children[i].isShared) // cloned already UNLESS i is outside scan range
+          children[i] = children[i].clone();
+        children[i].mergeSibling(children[i+1], maxSize);
+        children.splice(i + 1, 1);
+        this.keys.splice(i + 1, 1);
+        this.keys[i] = children[i].maxKey();
+        return true;
+      }
+    }
+    return false;
+  }
+
+  mergeSibling(rhs: BNode<K,V>, maxNodeSize: number) {
+    // assert !this.isShared;
+    var oldLength = this.keys.length;
+    this.keys.push.apply(this.keys, rhs.keys);
+    this.children.push.apply(this.children, (rhs as any as BNodeInternal<K,V>).children);
+    // If our children are themselves almost empty due to a mass-delete,
+    // they may need to be merged too (but only the oldLength-1 and its
+    // right sibling should need this).
+    this.tryMerge(oldLength-1, maxNodeSize);
+  }
+}
+
+// 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
+// be shared between trees with different maximums, its length can only
+// 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.
+var undefVals: any[] = [];
+
+const Delete = {delete: true}, DeleteRange = () => Delete;
+const Break = {break: true};
+const EmptyLeaf = (function() { 
+  var n = new BNode<any,any>(); n.isShared = true; return n;
+})();
+const EmptyArray: any[] = [];
+const ReusedArray: any[] = []; // assumed thread-local
+
+function check(fact: boolean, ...args: any[]) {
+  if (!fact) {
+    args.unshift('B+ tree '); // at beginning of message
+    throw new Error(args.join(' '));
+  }
+}
+
+/** A BTree frozen in the empty state. */
+export const EmptyBTree = (() => { let t = new BTree(); t.freeze(); return t; })();
\ No newline at end of file
diff --git a/packages/idb-bridge/src/tree/interfaces.ts b/packages/idb-bridge/src/tree/interfaces.ts
new file mode 100644
index 000000000..c708c20b5
--- /dev/null
+++ b/packages/idb-bridge/src/tree/interfaces.ts
@@ -0,0 +1,329 @@
+/*
+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
+
+
+/** Read-only set interface (subinterface of IMapSource<K,any>).
+ *  The word "set" usually means that each item in the collection is unique
+ *  (appears only once, based on a definition of equality used by the 
+ *  collection.) Objects conforming to this interface aren't guaranteed not 
+ *  to contain duplicates, but as an example, BTree<K,V> implements this 
+ *  interface and does not allow duplicates. */
+export interface ISetSource<K=any>
+{
+  /** Returns the number of key/value pairs in the map object. */
+  size: number;
+  /** Returns a boolean asserting whether the key exists in the map object or not. */
+  has(key: K): boolean;
+  /** Returns a new iterator for iterating the items in the set (the order is implementation-dependent). */
+  keys(): IterableIterator<K>;
+}
+
+/** Read-only map interface (i.e. a source of key-value pairs). */
+export interface IMapSource<K=any, V=any> extends ISetSource<K>
+{
+  /** Returns the number of key/value pairs in the map object. */
+  size: number;
+  /** Returns the value associated to the key, or undefined if there is none. */
+  get(key: K): V|undefined;
+  /** Returns a boolean asserting whether the key exists in the map object or not. */
+  has(key: K): boolean;
+  /** Calls callbackFn once for each key-value pair present in the map object.
+   *  The ES6 Map class sends the value to the callback before the key, so
+   *  this interface must do likewise. */
+  forEach(callbackFn: (v:V, k:K, map:IMapSource<K,V>) => void, thisArg: any): void;
+  
+  /** Returns an iterator that provides all key-value pairs from the collection (as arrays of length 2). */
+  entries(): IterableIterator<[K,V]>;
+  /** Returns a new iterator for iterating the keys of each pair. */
+  keys(): IterableIterator<K>;
+  /** Returns a new iterator for iterating the values of each pair. */
+  values(): IterableIterator<V>;
+  // TypeScript compiler decided Symbol.iterator has type 'any'
+  //[Symbol.iterator](): IterableIterator<[K,V]>;
+}
+
+/** Write-only set interface (the set cannot be queried, but items can be added to it.) 
+ *  @description Note: BTree<K,V> does not officially implement this interface,
+ *               but BTree<K> can be used as an instance of ISetSink<K>. */
+export interface ISetSink<K=any>
+{
+  /** Adds the specified item to the set, if it was not in the set already. */
+  add(key: K): any;
+  /** Returns true if an element in the map object existed and has been 
+   *  removed, or false if the element did not exist. */
+  delete(key: K): boolean;
+  /** Removes everything so that the set is empty. */
+  clear(): void;
+}
+
+/** Write-only map interface (i.e. a drain into which key-value pairs can be "sunk") */
+export interface IMapSink<K=any, V=any>
+{
+  /** Returns true if an element in the map object existed and has been 
+   *  removed, or false if the element did not exist. */
+  delete(key: K): boolean;
+  /** Sets the value for the key in the map object (the return value is 
+   *  boolean in BTree but Map returns the Map itself.) */
+  set(key: K, value: V): any;
+  /** Removes all key/value pairs from the IMap object. */
+  clear(): void;
+}
+
+/** Set interface.
+ *  @description Note: BTree<K,V> does not officially implement this interface,
+ *               but BTree<K> can be used as an instance of ISet<K>. */
+export interface ISet<K=any> extends ISetSource<K>, ISetSink<K> { }
+
+/** An interface compatible with ES6 Map and BTree. This interface does not
+ *  describe the complete interface of either class, but merely the common 
+ *  interface shared by both. */
+export interface IMap<K=any, V=any> extends IMapSource<K, V>, IMapSink<K, V> { }
+
+/** An data source that provides read-only access to a set of items called
+ *  "keys" in sorted order. This is a subinterface of ISortedMapSource. */
+export interface ISortedSetSource<K=any> extends ISetSource<K>
+{
+  /** Gets the lowest key in the collection. */
+  minKey(): K | undefined;
+  /** Gets the highest key in the collection. */
+  maxKey(): K | undefined;
+  /** Returns the next key larger than the specified key (or undefined if there is none) */
+  nextHigherKey(key: K): K|undefined;
+  /** Returns the next key smaller than the specified key (or undefined if there is none) */
+  nextLowerKey(key: K): K|undefined;
+  /** Calls `callback` on the specified range of keys, in ascending order by key.
+   * @param low The first key scanned will be greater than or equal to `low`.
+   * @param high Scanning stops when a key larger than this is reached.
+   * @param includeHigh If the `high` key is present in the map, `onFound` is called 
+   *        for that final pair if and only if this parameter is true.
+   * @param onFound A function that is called for each key pair. Because this
+   *        is a subinterface of ISortedMapSource, if there is a value 
+   *        associated with the key, it is passed as the second parameter.
+   * @param initialCounter Initial third argument of `onFound`. This value 
+   *        increases by one each time `onFound` is called. Default: 0
+   * @returns Number of pairs found and the number of times `onFound` was called.
+   */
+  forRange(low: K, high: K, includeHigh: boolean, onFound?: (k:K,v:any,counter:number) => void, initialCounter?: number): number;
+  /** 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>;
+}
+
+/** An data source that provides read-only access to items in sorted order. */
+export interface ISortedMapSource<K=any, V=any> extends IMapSource<K, V>, ISortedSetSource<K>
+{
+  /** Returns the next pair whose key is larger than the specified key (or undefined if there is none) */
+  nextHigherPair(key: K): [K,V]|undefined;
+  /** Returns the next pair whose key is smaller than the specified key (or undefined if there is none) */
+  nextLowerPair(key: K): [K,V]|undefined;
+  /** Builds an array of pairs from the specified range of keys, sorted by key.
+   * Each returned pair is also an array: pair[0] is the key, pair[1] is the value.
+   * @param low The first key in the array will be greater than or equal to `low`.
+   * @param high This method returns when a key larger than this is reached.
+   * @param includeHigh If the `high` key is present in the map, its pair will be
+   *        included in the output if and only if this parameter is true. Note: 
+   *        if the `low` key is present, it is always included in the output.
+   * @param maxLength Maximum length of the returned array (default: unlimited)
+   * @description Computational complexity: O(result.length + log size)
+   */
+  getRange(low: K, high: K, includeHigh?: boolean, maxLength?: number): [K,V][];
+  /** Calls `callback` on the specified range of keys, in ascending order by key.
+   * @param low The first key scanned will be greater than or equal to `low`.
+   * @param high Scanning stops when a key larger than this is reached.
+   * @param includeHigh If the `high` key is present in the map, `onFound` is called 
+   *        for that final pair if and only if this parameter is true.
+   * @param onFound A function that is called for each key-value pair.
+   * @param initialCounter Initial third argument of onFound. This value 
+   *        increases by one each time `onFound` is called. Default: 0
+   * @returns Number of pairs found and the number of times `callback` was called.
+   */
+  forRange(low: K, high: K, includeHigh: boolean, onFound?: (k:K,v:V,counter:number) => void, initialCounter?: number): number;
+  /** Returns an iterator that provides items in order by key.
+   *  @param firstKey: Minimum key to include in the output. */
+  entries(firstKey?: K): IterableIterator<[K,V]>;
+  /** 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>;
+  /** Returns a new iterator for iterating the values of each pair in order by key. 
+   *  @param firstKey: Minimum key whose associated value is included in the output. */
+  values(firstKey?: K): IterableIterator<V>;
+  
+  // This method should logically be in IMapSource but is not supported by ES6 Map
+  /** Performs a reduce operation like the `reduce` method of `Array`. 
+   *  It is used to combine all pairs into a single value, or perform conversions. */
+  reduce<R>(callback: (previous:R,currentPair:[K,V],counter:number,tree:IMapF<K,V>) => R, initialValue: R): R;
+  /** Performs a reduce operation like the `reduce` method of `Array`. 
+   *  It is used to combine all pairs into a single value, or perform conversions. */
+  reduce<R>(callback: (previous:R|undefined,currentPair:[K,V],counter:number,tree:IMapF<K,V>) => R): R|undefined;
+}
+
+/** An interface for a set of keys (the combination of ISortedSetSource<K> and ISetSink<K>) */
+export interface ISortedSet<K=any> extends ISortedSetSource<K>, ISetSink<K> { }
+
+/** An interface for a sorted map (dictionary), 
+ *  not including functional/persistent methods. */
+export interface ISortedMap<K=any, V=any> extends IMap<K,V>, ISortedMapSource<K, V>
+{
+  // All of the following methods should be in IMap but are left out of IMap
+  // so that IMap is compatible with ES6 Map.
+
+  /** Adds or overwrites a key-value pair in the sorted map.
+   * @param key the key is used to determine the sort order of data in the tree.
+   * @param value data to associate with the key
+   * @param overwrite Whether to overwrite an existing key-value pair 
+   *        (default: true). If this is false and there is an existing
+   *        key-value pair then the call to this method has no effect.
+   * @returns true if a new key-value pair was added, false if the key 
+   *        already existed. */
+  set(key: K, value: V, overwrite?: boolean): boolean;
+  /** Adds all pairs from a list of key-value pairs.
+   * @param pairs Pairs to add to this tree. If there are duplicate keys, 
+   *        later pairs currently overwrite earlier ones (e.g. [[0,1],[0,7]] 
+   *        associates 0 with 7.)
+   * @param overwrite Whether to overwrite pairs that already exist (if false,
+   *        pairs[i] is ignored when the key pairs[i][0] already exists.)
+   * @returns The number of pairs added to the collection.
+   */
+  setPairs(pairs: [K,V][], overwrite?: boolean): number;
+  /** Deletes a series of keys from the collection. */
+  deleteKeys(keys: K[]): number;
+  /** Removes a range of key-value pairs from the B+ tree.
+   * @param low The first key deleted will be greater than or equal to `low`.
+   * @param high Deleting stops when a key larger than this is reached.
+   * @param includeHigh Specifies whether the `high` key, if present, is deleted.
+   * @returns The number of key-value pairs that were deleted. */
+  deleteRange(low: K, high: K, includeHigh: boolean): number;
+
+  // TypeScript requires these methods of ISortedMapSource to be repeated
+  entries(firstKey?: K): IterableIterator<[K,V]>;
+  keys(firstKey?: K): IterableIterator<K>;
+  values(firstKey?: K): IterableIterator<V>;
+}
+
+/** An interface for a functional set, in which the set object could be read-only 
+ *  but new versions of the set can be created by calling "with" or "without" 
+ *  methods to add or remove keys. This is a subinterface of IMapF<K,V>,
+ *  so the items in the set may be referred to as "keys". */
+export interface ISetF<K=any> extends ISetSource<K> {
+  /** Returns a copy of the set with the specified key included. 
+   *  @description You might wonder why this method accepts only one key 
+   *  instead of `...keys: K[]`. The reason is that the derived interface
+   *  IMapF expects the second parameter to be a value. Therefore
+   *  withKeys() is provided to set multiple keys at once. */
+  with(key: K): ISetF<K>;
+  /** Returns a copy of the set with the specified key removed. */
+  without(key: K): ISetF<K>;
+  /** Returns a copy of the tree with all the keys in the specified array present.
+   *  @param keys The keys to add.
+   *  @param returnThisIfUnchanged If true, the method returns `this` when
+   *         all of the keys are already present in the collection. The 
+   *         default value may be true or false depending on the concrete
+   *         implementation of the interface (in BTree, the default is false.) */
+  withKeys(keys: K[], returnThisIfUnchanged?: boolean): ISetF<K>;
+  /** Returns a copy of the tree with all the keys in the specified array removed. */
+  withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): ISetF<K>;
+  /** Returns a copy of the tree with items removed whenever the callback 
+   *  function returns false.
+   *  @param callback A function to call for each item in the set.
+   *         The second parameter to `callback` exists because ISetF
+   *         is a subinterface of IMapF. If the object is a map, v
+   *         is the value associated with the key, otherwise v could be
+   *         undefined or another copy of the third parameter (counter). */
+  filter(callback: (k:K,v:any,counter:number) => boolean, returnThisIfUnchanged?: boolean): ISetF<K>;
+}
+
+/** An interface for a functional map, in which the map object could be read-only
+ *  but new versions of the map can be created by calling "with" or "without" 
+ *  methods to add or remove keys or key-value pairs. 
+ */
+export interface IMapF<K=any, V=any> extends IMapSource<K, V>, ISetF<K> {
+  /** Returns a copy of the tree with the specified key set (the value is undefined). */
+  with(key: K): IMapF<K,V|undefined>;
+  /** Returns a copy of the tree with the specified key-value pair set. */
+  with<V2>(key: K, value: V2, overwrite?: boolean): IMapF<K,V|V2>;
+  /** Returns a copy of the tree with the specified key-value pairs set. */
+  withPairs<V2>(pairs: [K,V|V2][], overwrite: boolean): IMapF<K,V|V2>;
+  /** Returns a copy of the tree with all the keys in the specified array present.
+   *  @param keys The keys to add. If a key is already present in the tree,
+   *         neither the existing key nor the existing value is modified. 
+   *  @param returnThisIfUnchanged If true, the method returns `this` when
+   *         all of the keys are already present in the collection. The 
+   *         default value may be true or false depending on the concrete
+   *         implementation of the interface (in BTree, the default is false.) */
+  withKeys(keys: K[], returnThisIfUnchanged?: boolean): IMapF<K,V|undefined>;
+  /** Returns a copy of the tree with all values altered by a callback function. */
+  mapValues<R>(callback: (v:V,k:K,counter:number) => R): IMapF<K,R>;
+  /** Performs a reduce operation like the `reduce` method of `Array`. 
+   *  It is used to combine all pairs into a single value, or perform conversions. */
+  reduce<R>(callback: (previous:R,currentPair:[K,V],counter:number,tree:IMapF<K,V>) => R, initialValue: R): R;
+  /** Performs a reduce operation like the `reduce` method of `Array`. 
+   *  It is used to combine all pairs into a single value, or perform conversions. */
+  reduce<R>(callback: (previous:R|undefined,currentPair:[K,V],counter:number,tree:IMapF<K,V>) => R): R|undefined;
+
+  // Update return types in ISetF
+  without(key: K): IMapF<K,V>;
+  withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): IMapF<K,V>;
+  /** Returns a copy of the tree with pairs removed whenever the callback 
+   *  function returns false. */
+  filter(callback: (k:K,v:V,counter:number) => boolean, returnThisIfUnchanged?: boolean): IMapF<K,V>;
+}
+
+/** An interface for a functional sorted set: a functional set in which the 
+ *  keys (items) are sorted. This is a subinterface of ISortedMapF. */
+export interface ISortedSetF<K=any> extends ISetF<K>, ISortedSetSource<K>
+{
+  // TypeScript requires this method of ISortedSetSource to be repeated
+  keys(firstKey?: K): IterableIterator<K>;
+}
+
+export interface ISortedMapF<K=any,V=any> extends ISortedSetF<K>, IMapF<K,V>, ISortedMapSource<K,V>
+{
+  /** Returns a copy of the tree with the specified range of keys removed. */
+  withoutRange(low: K, high: K, includeHigh: boolean, returnThisIfUnchanged?: boolean): ISortedMapF<K,V>;
+
+  // TypeScript requires these methods of ISortedSetF and ISortedMapSource to be repeated
+  entries(firstKey?: K): IterableIterator<[K,V]>;
+  keys(firstKey?: K): IterableIterator<K>;
+  values(firstKey?: K): IterableIterator<V>;
+  forRange(low: K, high: K, includeHigh: boolean, onFound?: (k:K,v:V,counter:number) => void, initialCounter?: number): number;
+
+  // Update the return value of methods from base interfaces
+  with(key: K): ISortedMapF<K,V|undefined>;
+  with<V2>(key: K, value: V2, overwrite?: boolean): ISortedMapF<K,V|V2>;
+  withKeys(keys: K[], returnThisIfUnchanged?: boolean): ISortedMapF<K,V|undefined>;
+  withPairs<V2>(pairs: [K,V|V2][], overwrite: boolean): ISortedMapF<K,V|V2>;
+  mapValues<R>(callback: (v:V,k:K,counter:number) => R): ISortedMapF<K,R>;
+  without(key: K): ISortedMapF<K,V>;
+  withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): ISortedMapF<K,V>;
+  filter(callback: (k:K,v:any,counter:number) => boolean, returnThisIfUnchanged?: boolean): ISortedMapF<K,V>;
+}
+
+export interface ISortedMapConstructor<K,V> {
+    new (entries?: [K,V][], compare?: (a: K, b: K) => number): ISortedMap<K,V>;
+}
+export interface ISortedMapFConstructor<K,V> {
+    new (entries?: [K,V][], compare?: (a: K, b: K) => number): ISortedMapF<K,V>;
+}
\ No newline at end of file
diff --git a/packages/idb-bridge/src/util/FakeEvent.ts b/packages/idb-bridge/src/util/FakeEvent.ts
new file mode 100644
index 000000000..bf17f7e72
--- /dev/null
+++ b/packages/idb-bridge/src/util/FakeEvent.ts
@@ -0,0 +1,80 @@
+/*
+ Copyright 2017 Jeremy Scheff
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ or implied. See the License for the specific language governing
+ permissions and limitations under the License.
+*/
+
+
+import FakeEventTarget from "./FakeEventTarget";
+import { EventType } from "./types";
+
+class Event {
+    public eventPath: FakeEventTarget[] = [];
+    public type: EventType;
+
+    public readonly NONE = 0;
+    public readonly CAPTURING_PHASE = 1;
+    public readonly AT_TARGET = 2;
+    public readonly BUBBLING_PHASE = 3;
+
+    // Flags
+    public propagationStopped = false;
+    public immediatePropagationStopped = false;
+    public canceled = false;
+    public initialized = true;
+    public dispatched = false;
+
+    public target: FakeEventTarget | null = null;
+    public currentTarget: FakeEventTarget | null = null;
+
+    public eventPhase: 0 | 1 | 2 | 3 = 0;
+
+    public defaultPrevented = false;
+
+    public isTrusted = false;
+    public timeStamp = Date.now();
+
+    public bubbles: boolean;
+    public cancelable: boolean;
+
+    constructor(
+        type: EventType,
+        eventInitDict: { bubbles?: boolean; cancelable?: boolean } = {},
+    ) {
+        this.type = type;
+
+        this.bubbles =
+            eventInitDict.bubbles !== undefined ? eventInitDict.bubbles : false;
+        this.cancelable =
+            eventInitDict.cancelable !== undefined
+                ? eventInitDict.cancelable
+                : false;
+    }
+
+    public preventDefault() {
+        if (this.cancelable) {
+            this.canceled = true;
+        }
+    }
+
+    public stopPropagation() {
+        this.propagationStopped = true;
+    }
+
+    public stopImmediatePropagation() {
+        this.propagationStopped = true;
+        this.immediatePropagationStopped = true;
+    }
+}
+
+export default Event;
diff --git a/packages/idb-bridge/src/util/FakeEventTarget.ts b/packages/idb-bridge/src/util/FakeEventTarget.ts
new file mode 100644
index 000000000..3c7eaf468
--- /dev/null
+++ b/packages/idb-bridge/src/util/FakeEventTarget.ts
@@ -0,0 +1,177 @@
+/*
+ Copyright 2017 Jeremy Scheff
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ or implied. See the License for the specific language governing
+ permissions and limitations under the License.
+ */
+
+
+import { InvalidStateError } from "./errors";
+import FakeEvent from "./FakeEvent";
+import { EventCallback, EventType } from "./types";
+
+type EventTypeProp =
+    | "onabort"
+    | "onblocked"
+    | "oncomplete"
+    | "onerror"
+    | "onsuccess"
+    | "onupgradeneeded"
+    | "onversionchange";
+
+interface Listener {
+    callback: EventCallback;
+    capture: boolean;
+    type: EventType;
+}
+
+const stopped = (event: FakeEvent, listener: Listener) => {
+    return (
+        event.immediatePropagationStopped ||
+        (event.eventPhase === event.CAPTURING_PHASE &&
+            listener.capture === false) ||
+        (event.eventPhase === event.BUBBLING_PHASE && listener.capture === true)
+    );
+};
+
+// http://www.w3.org/TR/dom/#concept-event-listener-invoke
+const invokeEventListeners = (event: FakeEvent, obj: FakeEventTarget) => {
+    event.currentTarget = obj;
+
+    // The callback might cause obj.listeners to mutate as we traverse it.
+    // Take a copy of the array so that nothing sneaks in and we don't lose
+    // our place.
+    for (const listener of obj.listeners.slice()) {
+        if (event.type !== listener.type || stopped(event, listener)) {
+            continue;
+        }
+
+        // @ts-ignore
+        listener.callback.call(event.currentTarget, event);
+    }
+
+    const typeToProp: { [key in EventType]: EventTypeProp } = {
+        abort: "onabort",
+        blocked: "onblocked",
+        complete: "oncomplete",
+        error: "onerror",
+        success: "onsuccess",
+        upgradeneeded: "onupgradeneeded",
+        versionchange: "onversionchange",
+    };
+    const prop = typeToProp[event.type];
+    if (prop === undefined) {
+        throw new Error(`Unknown event type: "${event.type}"`);
+    }
+
+    const callback = event.currentTarget[prop];
+    if (callback) {
+        const listener = {
+            callback,
+            capture: false,
+            type: event.type,
+        };
+        if (!stopped(event, listener)) {
+            // @ts-ignore
+            listener.callback.call(event.currentTarget, event);
+        }
+    }
+};
+
+abstract class FakeEventTarget {
+    public readonly listeners: Listener[] = [];
+
+    // These will be overridden in individual subclasses and made not readonly
+    public readonly onabort: EventCallback | null | undefined;
+    public readonly onblocked: EventCallback | null | undefined;
+    public readonly oncomplete: EventCallback | null | undefined;
+    public readonly onerror: EventCallback | null | undefined;
+    public readonly onsuccess: EventCallback | null | undefined;
+    public readonly onupgradeneeded: EventCallback | null | undefined;
+    public readonly onversionchange: EventCallback | null | undefined;
+
+    public addEventListener(
+        type: EventType,
+        callback: EventCallback,
+        capture = false,
+    ) {
+        this.listeners.push({
+            callback,
+            capture,
+            type,
+        });
+    }
+
+    public removeEventListener(
+        type: EventType,
+        callback: EventCallback,
+        capture = false,
+    ) {
+        const i = this.listeners.findIndex(listener => {
+            return (
+                listener.type === type &&
+                listener.callback === callback &&
+                listener.capture === capture
+            );
+        });
+
+        this.listeners.splice(i, 1);
+    }
+
+    // http://www.w3.org/TR/dom/#dispatching-events
+    public dispatchEvent(event: FakeEvent) {
+        if (event.dispatched || !event.initialized) {
+            throw new InvalidStateError("The object is in an invalid state.");
+        }
+        event.isTrusted = false;
+
+        event.dispatched = true;
+        event.target = this;
+        // NOT SURE WHEN THIS SHOULD BE SET        event.eventPath = [];
+
+        event.eventPhase = event.CAPTURING_PHASE;
+        for (const obj of event.eventPath) {
+            if (!event.propagationStopped) {
+                invokeEventListeners(event, obj);
+            }
+        }
+
+        event.eventPhase = event.AT_TARGET;
+        if (!event.propagationStopped) {
+            invokeEventListeners(event, event.target);
+        }
+
+        if (event.bubbles) {
+            event.eventPath.reverse();
+            event.eventPhase = event.BUBBLING_PHASE;
+            if (event.eventPath.length === 0 && event.type === "error") {
+                console.error("Unhandled error event: ", event.target);
+            }
+            for (const obj of event.eventPath) {
+                if (!event.propagationStopped) {
+                    invokeEventListeners(event, obj);
+                }
+            }
+        }
+
+        event.dispatched = false;
+        event.eventPhase = event.NONE;
+        event.currentTarget = null;
+
+        if (event.canceled) {
+            return false;
+        }
+        return true;
+    }
+}
+
+export default FakeEventTarget;
diff --git a/packages/idb-bridge/src/util/canInjectKey.ts b/packages/idb-bridge/src/util/canInjectKey.ts
new file mode 100644
index 000000000..c6c9c24ab
--- /dev/null
+++ b/packages/idb-bridge/src/util/canInjectKey.ts
@@ -0,0 +1,34 @@
+import { KeyPath, Value } from "./types";
+
+// http://w3c.github.io/IndexedDB/#check-that-a-key-could-be-injected-into-a-value
+const canInjectKey = (keyPath: KeyPath, value: Value) => {
+  if (Array.isArray(keyPath)) {
+    // tslint:disable-next-line max-line-length
+    throw new Error(
+      "The key paths used in this section are always strings and never sequences, since it is not possible to create a object store which has a key generator and also has a key path that is a sequence.",
+    );
+  }
+
+  const identifiers = keyPath.split(".");
+  if (identifiers.length === 0) {
+    throw new Error("Assert: identifiers is not empty");
+  }
+  identifiers.pop();
+
+  for (const identifier of identifiers) {
+    if (typeof value !== "object" && !Array.isArray(value)) {
+      return false;
+    }
+
+    const hop = value.hasOwnProperty(identifier);
+    if (!hop) {
+      return true;
+    }
+
+    value = value[identifier];
+  }
+
+  return typeof value === "object" || Array.isArray(value);
+};
+
+export default canInjectKey;
diff --git a/packages/idb-bridge/src/util/cmp.ts b/packages/idb-bridge/src/util/cmp.ts
new file mode 100644
index 000000000..9d0dc99a2
--- /dev/null
+++ b/packages/idb-bridge/src/util/cmp.ts
@@ -0,0 +1,108 @@
+/*
+ Copyright 2017 Jeremy Scheff
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ or implied. See the License for the specific language governing
+ permissions and limitations under the License.
+ */
+
+import { DataError } from "./errors";
+import valueToKey from "./valueToKey";
+
+const getType = (x: any) => {
+    if (typeof x === "number") {
+        return "Number";
+    }
+    if (x instanceof Date) {
+        return "Date";
+    }
+    if (Array.isArray(x)) {
+        return "Array";
+    }
+    if (typeof x === "string") {
+        return "String";
+    }
+    if (x instanceof ArrayBuffer) {
+        return "Binary";
+    }
+
+    throw new DataError();
+};
+
+// https://w3c.github.io/IndexedDB/#compare-two-keys
+const compareKeys = (first: any, second: any): -1 | 0 | 1 => {
+    if (second === undefined) {
+        throw new TypeError();
+    }
+
+    first = valueToKey(first);
+    second = valueToKey(second);
+
+    const t1 = getType(first);
+    const t2 = getType(second);
+
+    if (t1 !== t2) {
+        if (t1 === "Array") {
+            return 1;
+        }
+        if (
+            t1 === "Binary" &&
+            (t2 === "String" || t2 === "Date" || t2 === "Number")
+        ) {
+            return 1;
+        }
+        if (t1 === "String" && (t2 === "Date" || t2 === "Number")) {
+            return 1;
+        }
+        if (t1 === "Date" && t2 === "Number") {
+            return 1;
+        }
+        return -1;
+    }
+
+    if (t1 === "Binary") {
+        first = new Uint8Array(first);
+        second = new Uint8Array(second);
+    }
+
+    if (t1 === "Array" || t1 === "Binary") {
+        const length = Math.min(first.length, second.length);
+        for (let i = 0; i < length; i++) {
+            const result = compareKeys(first[i], second[i]);
+
+            if (result !== 0) {
+                return result;
+            }
+        }
+
+        if (first.length > second.length) {
+            return 1;
+        }
+        if (first.length < second.length) {
+            return -1;
+        }
+        return 0;
+    }
+
+    if (t1 === "Date") {
+        if (first.getTime() === second.getTime()) {
+            return 0;
+        }
+    } else {
+        if (first === second) {
+            return 0;
+        }
+    }
+
+    return first > second ? 1 : -1;
+};
+
+export default compareKeys;
diff --git a/packages/idb-bridge/src/util/deepEquals.ts b/packages/idb-bridge/src/util/deepEquals.ts
new file mode 100644
index 000000000..8d05ad21e
--- /dev/null
+++ b/packages/idb-bridge/src/util/deepEquals.ts
@@ -0,0 +1,75 @@
+/*
+Copyright (c) 2017 Evgeny Poberezkin
+
+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.
+*/
+
+
+
+
+const isArray = Array.isArray;
+const keyList = Object.keys;
+const hasProp = Object.prototype.hasOwnProperty;
+
+function deepEquals(a: any, b: any): boolean {
+  if (a === b) return true;
+
+  if (a && b && typeof a == "object" && typeof b == "object") {
+    const arrA = isArray(a);
+    const arrB = isArray(b);
+    let i;
+    let length;
+    let key;
+
+    if (arrA && arrB) {
+      length = a.length;
+      if (length != b.length) return false;
+      for (i = length; i-- !== 0; ) if (!deepEquals(a[i], b[i])) return false;
+      return true;
+    }
+
+    if (arrA != arrB) return false;
+
+    const dateA = a instanceof Date;
+    const dateB = b instanceof Date;
+    if (dateA != dateB) return false;
+    if (dateA && dateB) return a.getTime() == b.getTime();
+
+    const regexpA = a instanceof RegExp;
+    const regexpB = b instanceof RegExp;
+    if (regexpA != regexpB) return false;
+    if (regexpA && regexpB) return a.toString() == b.toString();
+
+    const keys = keyList(a);
+    length = keys.length;
+
+    if (length !== keyList(b).length) return false;
+
+    for (i = length; i-- !== 0; ) if (!hasProp.call(b, keys[i])) return false;
+
+    for (i = length; i-- !== 0; ) {
+      key = keys[i];
+      if (!deepEquals(a[key], b[key])) return false;
+    }
+
+    return true;
+  }
+
+  return a !== a && b !== b;
+}
diff --git a/packages/idb-bridge/src/util/enforceRange.ts b/packages/idb-bridge/src/util/enforceRange.ts
new file mode 100644
index 000000000..0cf3b6c85
--- /dev/null
+++ b/packages/idb-bridge/src/util/enforceRange.ts
@@ -0,0 +1,18 @@
+// https://heycam.github.io/webidl/#EnforceRange
+
+const enforceRange = (
+    num: number,
+    type: "MAX_SAFE_INTEGER" | "unsigned long",
+) => {
+    const min = 0;
+    const max = type === "unsigned long" ? 4294967295 : 9007199254740991;
+
+    if (isNaN(num) || num < min || num > max) {
+        throw new TypeError();
+    }
+    if (num >= 0) {
+        return Math.floor(num);
+    }
+};
+
+export default enforceRange;
diff --git a/packages/idb-bridge/src/util/errors.ts b/packages/idb-bridge/src/util/errors.ts
new file mode 100644
index 000000000..bbf9498c1
--- /dev/null
+++ b/packages/idb-bridge/src/util/errors.ts
@@ -0,0 +1,120 @@
+/*
+ Copyright 2017 Jeremy Scheff
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ or implied. See the License for the specific language governing
+ permissions and limitations under the License.
+ */
+
+
+/* tslint:disable: max-classes-per-file max-line-length */
+
+const messages = {
+    AbortError:
+        "A request was aborted, for example through a call to IDBTransaction.abort.",
+    ConstraintError:
+        "A mutation operation in the transaction failed because a constraint was not satisfied. For example, an object such as an object store or index already exists and a request attempted to create a new one.",
+    DataCloneError:
+        "The data being stored could not be cloned by the internal structured cloning algorithm.",
+    DataError: "Data provided to an operation does not meet requirements.",
+    InvalidAccessError:
+        "An invalid operation was performed on an object. For example transaction creation attempt was made, but an empty scope was provided.",
+    InvalidStateError:
+        "An operation was called on an object on which it is not allowed or at a time when it is not allowed. Also occurs if a request is made on a source object that has been deleted or removed. Use TransactionInactiveError or ReadOnlyError when possible, as they are more specific variations of InvalidStateError.",
+    NotFoundError:
+        "The operation failed because the requested database object could not be found. For example, an object store did not exist but was being opened.",
+    ReadOnlyError:
+        'The mutating operation was attempted in a "readonly" transaction.',
+    TransactionInactiveError:
+        "A request was placed against a transaction which is currently not active, or which is finished.",
+    VersionError:
+        "An attempt was made to open a database using a lower version than the existing version.",
+};
+
+export class AbortError extends Error {
+    constructor(message = messages.AbortError) {
+        super();
+        this.name = "AbortError";
+        this.message = message;
+    }
+}
+
+export class ConstraintError extends Error {
+    constructor(message = messages.ConstraintError) {
+        super();
+        this.name = "ConstraintError";
+        this.message = message;
+    }
+}
+
+export class DataCloneError extends Error {
+    constructor(message = messages.DataCloneError) {
+        super();
+        this.name = "DataCloneError";
+        this.message = message;
+    }
+}
+
+export class DataError extends Error {
+    constructor(message = messages.DataError) {
+        super();
+        this.name = "DataError";
+        this.message = message;
+    }
+}
+
+export class InvalidAccessError extends Error {
+    constructor(message = messages.InvalidAccessError) {
+        super();
+        this.name = "InvalidAccessError";
+        this.message = message;
+    }
+}
+
+export class InvalidStateError extends Error {
+    constructor(message = messages.InvalidStateError) {
+        super();
+        this.name = "InvalidStateError";
+        this.message = message;
+    }
+}
+
+export class NotFoundError extends Error {
+    constructor(message = messages.NotFoundError) {
+        super();
+        this.name = "NotFoundError";
+        this.message = message;
+    }
+}
+
+export class ReadOnlyError extends Error {
+    constructor(message = messages.ReadOnlyError) {
+        super();
+        this.name = "ReadOnlyError";
+        this.message = message;
+    }
+}
+
+export class TransactionInactiveError extends Error {
+    constructor(message = messages.TransactionInactiveError) {
+        super();
+        this.name = "TransactionInactiveError";
+        this.message = message;
+    }
+}
+
+export class VersionError extends Error {
+    constructor(message = messages.VersionError) {
+        super();
+        this.name = "VersionError";
+        this.message = message;
+    }
+}
diff --git a/packages/idb-bridge/src/util/extractKey.ts b/packages/idb-bridge/src/util/extractKey.ts
new file mode 100644
index 000000000..fd14c5a64
--- /dev/null
+++ b/packages/idb-bridge/src/util/extractKey.ts
@@ -0,0 +1,55 @@
+import { Key, KeyPath, Value } from "./types";
+import valueToKey from "./valueToKey";
+
+// http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#dfn-steps-for-extracting-a-key-from-a-value-using-a-key-path
+const extractKey = (keyPath: KeyPath, value: Value) => {
+  if (Array.isArray(keyPath)) {
+    const result: Key[] = [];
+
+    for (let item of keyPath) {
+      // This doesn't make sense to me based on the spec, but it is needed to pass the W3C KeyPath tests (see same
+      // comment in validateKeyPath)
+      if (
+        item !== undefined &&
+        item !== null &&
+        typeof item !== "string" &&
+        (item as any).toString
+      ) {
+        item = (item as any).toString();
+      }
+      result.push(valueToKey(extractKey(item, value)));
+    }
+
+    return result;
+  }
+
+  if (keyPath === "") {
+    return value;
+  }
+
+  let remainingKeyPath: string | null = keyPath;
+  let object = value;
+
+  while (remainingKeyPath !== null) {
+    let identifier;
+
+    const i = remainingKeyPath.indexOf(".");
+    if (i >= 0) {
+      identifier = remainingKeyPath.slice(0, i);
+      remainingKeyPath = remainingKeyPath.slice(i + 1);
+    } else {
+      identifier = remainingKeyPath;
+      remainingKeyPath = null;
+    }
+
+    if (!object.hasOwnProperty(identifier)) {
+      return;
+    }
+
+    object = object[identifier];
+  }
+
+  return object;
+};
+
+export default extractKey;
diff --git a/packages/idb-bridge/src/util/fakeDOMStringList.ts b/packages/idb-bridge/src/util/fakeDOMStringList.ts
new file mode 100644
index 000000000..5add17588
--- /dev/null
+++ b/packages/idb-bridge/src/util/fakeDOMStringList.ts
@@ -0,0 +1,37 @@
+/*
+ * Copyright 2017 Jeremy Scheff
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ * or implied. See the License for the specific language governing
+ * permissions and limitations under the License.
+ */
+
+import { FakeDOMStringList } from "./types";
+
+// Would be nicer to sublcass Array, but I'd have to sacrifice Node 4 support to do that.
+
+const fakeDOMStringList = (arr: string[]): FakeDOMStringList => {
+  const arr2 = arr.slice();
+
+  Object.defineProperty(arr2, "contains", {
+    // tslint:disable-next-line object-literal-shorthand
+    value: (value: string) => arr2.indexOf(value) >= 0,
+  });
+
+  Object.defineProperty(arr2, "item", {
+    // tslint:disable-next-line object-literal-shorthand
+    value: (i: number) => arr2[i],
+  });
+
+  return arr2 as FakeDOMStringList;
+};
+
+export default fakeDOMStringList;
diff --git a/packages/idb-bridge/src/util/injectKey.ts b/packages/idb-bridge/src/util/injectKey.ts
new file mode 100644
index 000000000..89d3a01d8
--- /dev/null
+++ b/packages/idb-bridge/src/util/injectKey.ts
@@ -0,0 +1,48 @@
+import { KeyPath, Value, Key } from "./types";
+import canInjectKey from "./canInjectKey";
+import { DataError } from "./errors";
+import structuredClone from "./structuredClone";
+
+export function injectKey(keyPath: KeyPath, value: Value, key: Key): Value {
+  if (Array.isArray(keyPath)) {
+    // tslint:disable-next-line max-line-length
+    throw new Error(
+      "The key paths used in this section are always strings and never sequences, since it is not possible to create a object store which has a key generator and also has a key path that is a sequence.",
+    );
+  }
+
+  const identifiers = keyPath.split(".");
+  if (identifiers.length === 0) {
+    throw new Error("Assert: identifiers is not empty");
+  }
+
+  const lastIdentifier = identifiers.pop();
+
+  if (lastIdentifier === null || lastIdentifier === undefined) {
+    throw Error();
+  }
+
+  for (const identifier of identifiers) {
+    if (typeof value !== "object" && !Array.isArray(value)) {
+      return false;
+    }
+
+    const hop = value.hasOwnProperty(identifier);
+    if (!hop) {
+      return true;
+    }
+
+    value = value[identifier];
+  }
+
+  if (!(typeof value === "object" || Array.isArray(value))) {
+    throw new Error("can't inject key");
+  }
+
+  const newValue = structuredClone(value);
+  newValue[lastIdentifier] = structuredClone(key);
+
+  return newValue;
+}
+
+export default injectKey;
\ No newline at end of file
diff --git a/packages/idb-bridge/src/util/makeStoreKeyValue.ts b/packages/idb-bridge/src/util/makeStoreKeyValue.ts
new file mode 100644
index 000000000..4850cec26
--- /dev/null
+++ b/packages/idb-bridge/src/util/makeStoreKeyValue.ts
@@ -0,0 +1,92 @@
+import { Value, Key, KeyPath } from "./types";
+import extractKey from "./extractKey";
+import { DataError } from "./errors";
+import valueToKey from "./valueToKey";
+import structuredClone from "./structuredClone";
+import injectKey from "./injectKey";
+
+export interface StoreKeyResult {
+  updatedKeyGenerator: number;
+  key: Key;
+  value: Value;
+}
+
+export function makeStoreKeyValue(
+  value: Value,
+  key: Key | undefined,
+  currentKeyGenerator: number,
+  autoIncrement: boolean,
+  keyPath: KeyPath | null,
+): StoreKeyResult {
+  const haveKey = key !== undefined && key !== null;
+  const haveKeyPath = keyPath !== null && keyPath !== undefined;
+
+  // This models a decision table on (haveKey, haveKeyPath, autoIncrement)
+
+  value = structuredClone(value);
+
+  if (haveKey) {
+    if (haveKeyPath) {
+      // (yes, yes, no)
+      // (yes, yes, yes)
+      throw new DataError();
+    } else {
+      if (autoIncrement) {
+        // (yes, no, yes)
+        key = valueToKey(key)!;
+        let updatedKeyGenerator: number;
+        if (typeof key !== "number") {
+          updatedKeyGenerator = currentKeyGenerator;
+        } else {
+          updatedKeyGenerator = key;
+        }
+        return {
+          key: key!,
+          value: value,
+          updatedKeyGenerator,
+        };
+      } else {
+        // (yes, no, no)
+        throw new DataError();
+      }
+    }
+  } else {
+    if (haveKeyPath) {
+      if (autoIncrement) {
+        // (no, yes, yes)
+
+        let updatedKeyGenerator: number;
+        const maybeInlineKey = extractKey(keyPath!, value);
+        if (maybeInlineKey === undefined) {
+          value = injectKey(keyPath!, value, currentKeyGenerator);
+          key = currentKeyGenerator;
+          updatedKeyGenerator = currentKeyGenerator + 1;
+        } else if (typeof maybeInlineKey === "number") {
+          key = maybeInlineKey;
+          updatedKeyGenerator = maybeInlineKey;
+        } else {
+          key = maybeInlineKey;
+          updatedKeyGenerator = currentKeyGenerator + 1;
+        }
+        return {
+          key: key,
+          value: value,
+          updatedKeyGenerator,
+        }
+      } else {
+        // (no, yes, no)
+        key = extractKey(keyPath!, value);
+        key = valueToKey(key);
+        return {
+          key: key!,
+          value: value,
+          updatedKeyGenerator: currentKeyGenerator,
+        };
+      }
+    } else {
+      // (no, no, yes)
+      // (no, no, no)
+      throw new DataError();
+    }
+  }
+}
\ No newline at end of file
diff --git a/packages/idb-bridge/src/util/openPromise.ts b/packages/idb-bridge/src/util/openPromise.ts
new file mode 100644
index 000000000..3f6da81bd
--- /dev/null
+++ b/packages/idb-bridge/src/util/openPromise.ts
@@ -0,0 +1,22 @@
+function openPromise<T>(): {
+  promise: Promise<T>;
+  resolve: (v?: T | PromiseLike<T>) => void;
+  reject: (err?: any) => void;
+} {
+  let resolve;
+  let reject;
+  const promise = new Promise<T>((resolve2, reject2) => {
+    resolve = resolve2;
+    reject = reject2;
+  });
+  if (!resolve) {
+    throw Error("broken invariant");
+  }
+  if (!reject) {
+    throw Error("broken invariant");
+  }
+
+  return { promise, resolve, reject };
+}
+
+export default openPromise;
diff --git a/packages/idb-bridge/src/util/queueTask.ts b/packages/idb-bridge/src/util/queueTask.ts
new file mode 100644
index 000000000..7d59c2263
--- /dev/null
+++ b/packages/idb-bridge/src/util/queueTask.ts
@@ -0,0 +1,21 @@
+/*
+  Copyright 2019 Florian Dold
+
+  Licensed under the Apache License, Version 2.0 (the "License");
+  you may not use this file except in compliance with the License.
+  You may obtain a copy of the License at
+
+  http://www.apache.org/licenses/LICENSE-2.0
+
+  Unless required by applicable law or agreed to in writing, software
+  distributed under the License is distributed on an "AS IS" BASIS,
+  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+  or implied. See the License for the specific language governing
+  permissions and limitations under the License.
+ */
+
+ export function queueTask(fn: () => void) {
+   setImmediate(fn);
+ }
+
+ export default queueTask;
\ No newline at end of file
diff --git a/packages/idb-bridge/src/util/structuredClone.ts b/packages/idb-bridge/src/util/structuredClone.ts
new file mode 100644
index 000000000..8b6b61315
--- /dev/null
+++ b/packages/idb-bridge/src/util/structuredClone.ts
@@ -0,0 +1,15 @@
+
+function structuredCloneImpl(val: any, visited: WeakMap<any, boolean>): any {
+  // FIXME: replace with real implementation!
+  return JSON.parse(JSON.stringify(val));
+}
+
+/**
+ * Structured clone for IndexedDB.
+ */
+export function structuredClone(val: any): any {
+  const visited: WeakMap<any, boolean> = new WeakMap<any, boolean>();
+  return structuredCloneImpl(val, visited);
+}
+
+export default structuredClone;
\ No newline at end of file
diff --git a/packages/idb-bridge/src/util/types.ts b/packages/idb-bridge/src/util/types.ts
new file mode 100644
index 000000000..7aea22ab1
--- /dev/null
+++ b/packages/idb-bridge/src/util/types.ts
@@ -0,0 +1,73 @@
+/*
+ Copyright 2017 Jeremy Scheff
+ Copyright 2019 Florian Dold
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ or implied. See the License for the specific language governing
+ permissions and limitations under the License.
+*/
+
+import BridgeIDBRequest from "../BridgeIDBRequest";
+import BridgeIDBKeyRange from "../BridgeIDBKeyRange";
+import BridgeIDBIndex from "../BridgeIDBIndex";
+import BridgeIBObjectStore from "../BridgeIDBObjectStore";
+
+interface EventInCallback extends Event {
+  target: any;
+  error: Error | null;
+}
+
+export type EventCallback = (event: EventInCallback) => void;
+
+export type EventType =
+  | "abort"
+  | "blocked"
+  | "complete"
+  | "error"
+  | "success"
+  | "upgradeneeded"
+  | "versionchange";
+
+export type CursorSource = BridgeIDBIndex | BridgeIBObjectStore;
+
+
+export interface FakeDOMStringList extends Array<string> {
+  contains: (value: string) => boolean;
+  item: (i: number) => string | undefined;
+}
+
+export type BridgeIDBCursorDirection = "next" | "nextunique" | "prev" | "prevunique";
+
+export type KeyPath = string | string[];
+
+export type Key = any;
+
+export type CursorRange = Key | BridgeIDBKeyRange | undefined;
+
+export type Value = any;
+
+export interface Record {
+  key: Key;
+  value: Key | Value; // For indexes, will be Key. For object stores, will be Value.
+}
+
+export type TransactionMode = "readonly" | "readwrite" | "versionchange";
+
+export interface BridgeIDBDatabaseInfo {
+  name: string;
+  version: number
+};
+
+export interface RequestObj {
+  operation: () => Promise<any>;
+  request?: BridgeIDBRequest | undefined;
+  source?: any;
+}
diff --git a/packages/idb-bridge/src/util/validateKeyPath.ts b/packages/idb-bridge/src/util/validateKeyPath.ts
new file mode 100644
index 000000000..18552a5d4
--- /dev/null
+++ b/packages/idb-bridge/src/util/validateKeyPath.ts
@@ -0,0 +1,77 @@
+/*
+ Copyright 2017 Jeremy Scheff
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ or implied. See the License for the specific language governing
+ permissions and limitations under the License.
+*/
+
+import { KeyPath } from "./types";
+
+// http://www.w3.org/TR/2015/REC-IndexedDB-20150108/#dfn-valid-key-path
+const validateKeyPath = (keyPath: KeyPath, parent?: "array" | "string") => {
+    // This doesn't make sense to me based on the spec, but it is needed to pass the W3C KeyPath tests (see same
+    // comment in extractKey)
+    if (
+        keyPath !== undefined &&
+        keyPath !== null &&
+        typeof keyPath !== "string" &&
+        keyPath.toString &&
+        (parent === "array" || !Array.isArray(keyPath))
+    ) {
+        keyPath = keyPath.toString();
+    }
+
+    if (typeof keyPath === "string") {
+        if (keyPath === "" && parent !== "string") {
+            return;
+        }
+        try {
+            // https://mathiasbynens.be/demo/javascript-identifier-regex for ECMAScript 5.1 / Unicode v7.0.0, with
+            // reserved words at beginning removed
+            // tslint:disable-next-line max-line-length
+            const validIdentifierRegex = /^(?:[\$A-Z_a-z\xAA\xB5\xBA\xC0-\xD6\xD8-\xF6\xF8-\u02C1\u02C6-\u02D1\u02E0-\u02E4\u02EC\u02EE\u0370-\u0374\u0376\u0377\u037A-\u037D\u037F\u0386\u0388-\u038A\u038C\u038E-\u03A1\u03A3-\u03F5\u03F7-\u0481\u048A-\u052F\u0531-\u0556\u0559\u0561-\u0587\u05D0-\u05EA\u05F0-\u05F2\u0620-\u064A\u066E\u066F\u0671-\u06D3\u06D5\u06E5\u06E6\u06EE\u06EF\u06FA-\u06FC\u06FF\u0710\u0712-\u072F\u074D-\u07A5\u07B1\u07CA-\u07EA\u07F4\u07F5\u07FA\u0800-\u0815\u081A\u0824\u0828\u0840-\u0858\u08A0-\u08B2\u0904-\u0939\u093D\u0950\u0958-\u0961\u0971-\u0980\u0985-\u098C\u098F\u0990\u0993-\u09A8\u09AA-\u09B0\u09B2\u09B6-\u09B9\u09BD\u09CE\u09DC\u09DD\u09DF-\u09E1\u09F0\u09F1\u0A05-\u0A0A\u0A0F\u0A10\u0A13-\u0A28\u0A2A-\u0A30\u0A32\u0A33\u0A35\u0A36\u0A38\u0A39\u0A59-\u0A5C\u0A5E\u0A72-\u0A74\u0A85-\u0A8D\u0A8F-\u0A91\u0A93-\u0AA8\u0AAA-\u0AB0\u0AB2\u0AB3\u0AB5-\u0AB9\u0ABD\u0AD0\u0AE0\u0AE1\u0B05-\u0B0C\u0B0F\u0B10\u0B13-\u0B28\u0B2A-\u0B30\u0B32\u0B33\u0B35-\u0B39\u0B3D\u0B5C\u0B5D\u0B5F-\u0B61\u0B71\u0B83\u0B85-\u0B8A\u0B8E-\u0B90\u0B92-\u0B95\u0B99\u0B9A\u0B9C\u0B9E\u0B9F\u0BA3\u0BA4\u0BA8-\u0BAA\u0BAE-\u0BB9\u0BD0\u0C05-\u0C0C\u0C0E-\u0C10\u0C12-\u0C28\u0C2A-\u0C39\u0C3D\u0C58\u0C59\u0C60\u0C61\u0C85-\u0C8C\u0C8E-\u0C90\u0C92-\u0CA8\u0CAA-\u0CB3\u0CB5-\u0CB9\u0CBD\u0CDE\u0CE0\u0CE1\u0CF1\u0CF2\u0D05-\u0D0C\u0D0E-\u0D10\u0D12-\u0D3A\u0D3D\u0D4E\u0D60\u0D61\u0D7A-\u0D7F\u0D85-\u0D96\u0D9A-\u0DB1\u0DB3-\u0DBB\u0DBD\u0DC0-\u0DC6\u0E01-\u0E30\u0E32\u0E33\u0E40-\u0E46\u0E81\u0E82\u0E84\u0E87\u0E88\u0E8A\u0E8D\u0E94-\u0E97\u0E99-\u0E9F\u0EA1-\u0EA3\u0EA5\u0EA7\u0EAA\u0EAB\u0EAD-\u0EB0\u0EB2\u0EB3\u0EBD\u0EC0-\u0EC4\u0EC6\u0EDC-\u0EDF\u0F00\u0F40-\u0F47\u0F49-\u0F6C\u0F88-\u0F8C\u1000-\u102A\u103F\u1050-\u1055\u105A-\u105D\u1061\u1065\u1066\u106E-\u1070\u1075-\u1081\u108E\u10A0-\u10C5\u10C7\u10CD\u10D0-\u10FA\u10FC-\u1248\u124A-\u124D\u1250-\u1256\u1258\u125A-\u125D\u1260-\u1288\u128A-\u128D\u1290-\u12B0\u12B2-\u12B5\u12B8-\u12BE\u12C0\u12C2-\u12C5\u12C8-\u12D6\u12D8-\u1310\u1312-\u1315\u1318-\u135A\u1380-\u138F\u13A0-\u13F4\u1401-\u166C\u166F-\u167F\u1681-\u169A\u16A0-\u16EA\u16EE-\u16F8\u1700-\u170C\u170E-\u1711\u1720-\u1731\u1740-\u1751\u1760-\u176C\u176E-\u1770\u1780-\u17B3\u17D7\u17DC\u1820-\u1877\u1880-\u18A8\u18AA\u18B0-\u18F5\u1900-\u191E\u1950-\u196D\u1970-\u1974\u1980-\u19AB\u19C1-\u19C7\u1A00-\u1A16\u1A20-\u1A54\u1AA7\u1B05-\u1B33\u1B45-\u1B4B\u1B83-\u1BA0\u1BAE\u1BAF\u1BBA-\u1BE5\u1C00-\u1C23\u1C4D-\u1C4F\u1C5A-\u1C7D\u1CE9-\u1CEC\u1CEE-\u1CF1\u1CF5\u1CF6\u1D00-\u1DBF\u1E00-\u1F15\u1F18-\u1F1D\u1F20-\u1F45\u1F48-\u1F4D\u1F50-\u1F57\u1F59\u1F5B\u1F5D\u1F5F-\u1F7D\u1F80-\u1FB4\u1FB6-\u1FBC\u1FBE\u1FC2-\u1FC4\u1FC6-\u1FCC\u1FD0-\u1FD3\u1FD6-\u1FDB\u1FE0-\u1FEC\u1FF2-\u1FF4\u1FF6-\u1FFC\u2071\u207F\u2090-\u209C\u2102\u2107\u210A-\u2113\u2115\u2119-\u211D\u2124\u2126\u2128\u212A-\u212D\u212F-\u2139\u213C-\u213F\u2145-\u2149\u214E\u2160-\u2188\u2C00-\u2C2E\u2C30-\u2C5E\u2C60-\u2CE4\u2CEB-\u2CEE\u2CF2\u2CF3\u2D00-\u2D25\u2D27\u2D2D\u2D30-\u2D67\u2D6F\u2D80-\u2D96\u2DA0-\u2DA6\u2DA8-\u2DAE\u2DB0-\u2DB6\u2DB8-\u2DBE\u2DC0-\u2DC6\u2DC8-\u2DCE\u2DD0-\u2DD6\u2DD8-\u2DDE\u2E2F\u3005-\u3007\u3021-\u3029\u3031-\u3035\u3038-\u303C\u3041-\u3096\u309D-\u309F\u30A1-\u30FA\u30FC-\u30FF\u3105-\u312D\u3131-\u318E\u31A0-\u31BA\u31F0-\u31FF\u3400-\u4DB5\u4E00-\u9FCC\uA000-\uA48C\uA4D0-\uA4FD\uA500-\uA60C\uA610-\uA61F\uA62A\uA62B\uA640-\uA66E\uA67F-\uA69D\uA6A0-\uA6EF\uA717-\uA71F\uA722-\uA788\uA78B-\uA78E\uA790-\uA7AD\uA7B0\uA7B1\uA7F7-\uA801\uA803-\uA805\uA807-\uA80A\uA80C-\uA822\uA840-\uA873\uA882-\uA8B3\uA8F2-\uA8F7\uA8FB\uA90A-\uA925\uA930-\uA946\uA960-\uA97C\uA984-\uA9B2\uA9CF\uA9E0-\uA9E4\uA9E6-\uA9EF\uA9FA-\uA9FE\uAA00-\uAA28\uAA40-\uAA42\uAA44-\uAA4B\uAA60-\uAA76\uAA7A\uAA7E-\uAAAF\uAAB1\uAAB5\uAAB6\uAAB9-\uAABD\uAAC0\uAAC2\uAADB-\uAADD\uAAE0-\uAAEA\uAAF2-\uAAF4\uAB01-\uAB06\uAB09-\uAB0E\uAB11-\uAB16\uAB20-\uAB26\uAB28-\uAB2E\uAB30-\uAB5A\uAB5C-\uAB5F\uAB64\uAB65\uABC0-\uABE2\uAC00-\uD7A3\uD7B0-\uD7C6\uD7CB-\uD7FB\uF900-\uFA6D\uFA70-\uFAD9\uFB00-\uFB06\uFB13-\uFB17\uFB1D\uFB1F-\uFB28\uFB2A-\uFB36\uFB38-\uFB3C\uFB3E\uFB40\uFB41\uFB43\uFB44\uFB46-\uFBB1\uFBD3-\uFD3D\uFD50-\uFD8F\uFD92-\uFDC7\uFDF0-\uFDFB\uFE70-\uFE74\uFE76-\uFEFC\uFF21-\uFF3A\uFF41-\uFF5A\uFF66-\uFFBE\uFFC2-\uFFC7\uFFCA-\uFFCF\uFFD2-\uFFD7\uFFDA-\uFFDC])(?:[\$0-9A-Z_a-z\xAA\xB5\xBA\xC0-\xD6\xD8-\xF6\xF8-\u02C1\u02C6-\u02D1\u02E0-\u02E4\u02EC\u02EE\u0300-\u0374\u0376\u0377\u037A-\u037D\u037F\u0386\u0388-\u038A\u038C\u038E-\u03A1\u03A3-\u03F5\u03F7-\u0481\u0483-\u0487\u048A-\u052F\u0531-\u0556\u0559\u0561-\u0587\u0591-\u05BD\u05BF\u05C1\u05C2\u05C4\u05C5\u05C7\u05D0-\u05EA\u05F0-\u05F2\u0610-\u061A\u0620-\u0669\u066E-\u06D3\u06D5-\u06DC\u06DF-\u06E8\u06EA-\u06FC\u06FF\u0710-\u074A\u074D-\u07B1\u07C0-\u07F5\u07FA\u0800-\u082D\u0840-\u085B\u08A0-\u08B2\u08E4-\u0963\u0966-\u096F\u0971-\u0983\u0985-\u098C\u098F\u0990\u0993-\u09A8\u09AA-\u09B0\u09B2\u09B6-\u09B9\u09BC-\u09C4\u09C7\u09C8\u09CB-\u09CE\u09D7\u09DC\u09DD\u09DF-\u09E3\u09E6-\u09F1\u0A01-\u0A03\u0A05-\u0A0A\u0A0F\u0A10\u0A13-\u0A28\u0A2A-\u0A30\u0A32\u0A33\u0A35\u0A36\u0A38\u0A39\u0A3C\u0A3E-\u0A42\u0A47\u0A48\u0A4B-\u0A4D\u0A51\u0A59-\u0A5C\u0A5E\u0A66-\u0A75\u0A81-\u0A83\u0A85-\u0A8D\u0A8F-\u0A91\u0A93-\u0AA8\u0AAA-\u0AB0\u0AB2\u0AB3\u0AB5-\u0AB9\u0ABC-\u0AC5\u0AC7-\u0AC9\u0ACB-\u0ACD\u0AD0\u0AE0-\u0AE3\u0AE6-\u0AEF\u0B01-\u0B03\u0B05-\u0B0C\u0B0F\u0B10\u0B13-\u0B28\u0B2A-\u0B30\u0B32\u0B33\u0B35-\u0B39\u0B3C-\u0B44\u0B47\u0B48\u0B4B-\u0B4D\u0B56\u0B57\u0B5C\u0B5D\u0B5F-\u0B63\u0B66-\u0B6F\u0B71\u0B82\u0B83\u0B85-\u0B8A\u0B8E-\u0B90\u0B92-\u0B95\u0B99\u0B9A\u0B9C\u0B9E\u0B9F\u0BA3\u0BA4\u0BA8-\u0BAA\u0BAE-\u0BB9\u0BBE-\u0BC2\u0BC6-\u0BC8\u0BCA-\u0BCD\u0BD0\u0BD7\u0BE6-\u0BEF\u0C00-\u0C03\u0C05-\u0C0C\u0C0E-\u0C10\u0C12-\u0C28\u0C2A-\u0C39\u0C3D-\u0C44\u0C46-\u0C48\u0C4A-\u0C4D\u0C55\u0C56\u0C58\u0C59\u0C60-\u0C63\u0C66-\u0C6F\u0C81-\u0C83\u0C85-\u0C8C\u0C8E-\u0C90\u0C92-\u0CA8\u0CAA-\u0CB3\u0CB5-\u0CB9\u0CBC-\u0CC4\u0CC6-\u0CC8\u0CCA-\u0CCD\u0CD5\u0CD6\u0CDE\u0CE0-\u0CE3\u0CE6-\u0CEF\u0CF1\u0CF2\u0D01-\u0D03\u0D05-\u0D0C\u0D0E-\u0D10\u0D12-\u0D3A\u0D3D-\u0D44\u0D46-\u0D48\u0D4A-\u0D4E\u0D57\u0D60-\u0D63\u0D66-\u0D6F\u0D7A-\u0D7F\u0D82\u0D83\u0D85-\u0D96\u0D9A-\u0DB1\u0DB3-\u0DBB\u0DBD\u0DC0-\u0DC6\u0DCA\u0DCF-\u0DD4\u0DD6\u0DD8-\u0DDF\u0DE6-\u0DEF\u0DF2\u0DF3\u0E01-\u0E3A\u0E40-\u0E4E\u0E50-\u0E59\u0E81\u0E82\u0E84\u0E87\u0E88\u0E8A\u0E8D\u0E94-\u0E97\u0E99-\u0E9F\u0EA1-\u0EA3\u0EA5\u0EA7\u0EAA\u0EAB\u0EAD-\u0EB9\u0EBB-\u0EBD\u0EC0-\u0EC4\u0EC6\u0EC8-\u0ECD\u0ED0-\u0ED9\u0EDC-\u0EDF\u0F00\u0F18\u0F19\u0F20-\u0F29\u0F35\u0F37\u0F39\u0F3E-\u0F47\u0F49-\u0F6C\u0F71-\u0F84\u0F86-\u0F97\u0F99-\u0FBC\u0FC6\u1000-\u1049\u1050-\u109D\u10A0-\u10C5\u10C7\u10CD\u10D0-\u10FA\u10FC-\u1248\u124A-\u124D\u1250-\u1256\u1258\u125A-\u125D\u1260-\u1288\u128A-\u128D\u1290-\u12B0\u12B2-\u12B5\u12B8-\u12BE\u12C0\u12C2-\u12C5\u12C8-\u12D6\u12D8-\u1310\u1312-\u1315\u1318-\u135A\u135D-\u135F\u1380-\u138F\u13A0-\u13F4\u1401-\u166C\u166F-\u167F\u1681-\u169A\u16A0-\u16EA\u16EE-\u16F8\u1700-\u170C\u170E-\u1714\u1720-\u1734\u1740-\u1753\u1760-\u176C\u176E-\u1770\u1772\u1773\u1780-\u17D3\u17D7\u17DC\u17DD\u17E0-\u17E9\u180B-\u180D\u1810-\u1819\u1820-\u1877\u1880-\u18AA\u18B0-\u18F5\u1900-\u191E\u1920-\u192B\u1930-\u193B\u1946-\u196D\u1970-\u1974\u1980-\u19AB\u19B0-\u19C9\u19D0-\u19D9\u1A00-\u1A1B\u1A20-\u1A5E\u1A60-\u1A7C\u1A7F-\u1A89\u1A90-\u1A99\u1AA7\u1AB0-\u1ABD\u1B00-\u1B4B\u1B50-\u1B59\u1B6B-\u1B73\u1B80-\u1BF3\u1C00-\u1C37\u1C40-\u1C49\u1C4D-\u1C7D\u1CD0-\u1CD2\u1CD4-\u1CF6\u1CF8\u1CF9\u1D00-\u1DF5\u1DFC-\u1F15\u1F18-\u1F1D\u1F20-\u1F45\u1F48-\u1F4D\u1F50-\u1F57\u1F59\u1F5B\u1F5D\u1F5F-\u1F7D\u1F80-\u1FB4\u1FB6-\u1FBC\u1FBE\u1FC2-\u1FC4\u1FC6-\u1FCC\u1FD0-\u1FD3\u1FD6-\u1FDB\u1FE0-\u1FEC\u1FF2-\u1FF4\u1FF6-\u1FFC\u200C\u200D\u203F\u2040\u2054\u2071\u207F\u2090-\u209C\u20D0-\u20DC\u20E1\u20E5-\u20F0\u2102\u2107\u210A-\u2113\u2115\u2119-\u211D\u2124\u2126\u2128\u212A-\u212D\u212F-\u2139\u213C-\u213F\u2145-\u2149\u214E\u2160-\u2188\u2C00-\u2C2E\u2C30-\u2C5E\u2C60-\u2CE4\u2CEB-\u2CF3\u2D00-\u2D25\u2D27\u2D2D\u2D30-\u2D67\u2D6F\u2D7F-\u2D96\u2DA0-\u2DA6\u2DA8-\u2DAE\u2DB0-\u2DB6\u2DB8-\u2DBE\u2DC0-\u2DC6\u2DC8-\u2DCE\u2DD0-\u2DD6\u2DD8-\u2DDE\u2DE0-\u2DFF\u2E2F\u3005-\u3007\u3021-\u302F\u3031-\u3035\u3038-\u303C\u3041-\u3096\u3099\u309A\u309D-\u309F\u30A1-\u30FA\u30FC-\u30FF\u3105-\u312D\u3131-\u318E\u31A0-\u31BA\u31F0-\u31FF\u3400-\u4DB5\u4E00-\u9FCC\uA000-\uA48C\uA4D0-\uA4FD\uA500-\uA60C\uA610-\uA62B\uA640-\uA66F\uA674-\uA67D\uA67F-\uA69D\uA69F-\uA6F1\uA717-\uA71F\uA722-\uA788\uA78B-\uA78E\uA790-\uA7AD\uA7B0\uA7B1\uA7F7-\uA827\uA840-\uA873\uA880-\uA8C4\uA8D0-\uA8D9\uA8E0-\uA8F7\uA8FB\uA900-\uA92D\uA930-\uA953\uA960-\uA97C\uA980-\uA9C0\uA9CF-\uA9D9\uA9E0-\uA9FE\uAA00-\uAA36\uAA40-\uAA4D\uAA50-\uAA59\uAA60-\uAA76\uAA7A-\uAAC2\uAADB-\uAADD\uAAE0-\uAAEF\uAAF2-\uAAF6\uAB01-\uAB06\uAB09-\uAB0E\uAB11-\uAB16\uAB20-\uAB26\uAB28-\uAB2E\uAB30-\uAB5A\uAB5C-\uAB5F\uAB64\uAB65\uABC0-\uABEA\uABEC\uABED\uABF0-\uABF9\uAC00-\uD7A3\uD7B0-\uD7C6\uD7CB-\uD7FB\uF900-\uFA6D\uFA70-\uFAD9\uFB00-\uFB06\uFB13-\uFB17\uFB1D-\uFB28\uFB2A-\uFB36\uFB38-\uFB3C\uFB3E\uFB40\uFB41\uFB43\uFB44\uFB46-\uFBB1\uFBD3-\uFD3D\uFD50-\uFD8F\uFD92-\uFDC7\uFDF0-\uFDFB\uFE00-\uFE0F\uFE20-\uFE2D\uFE33\uFE34\uFE4D-\uFE4F\uFE70-\uFE74\uFE76-\uFEFC\uFF10-\uFF19\uFF21-\uFF3A\uFF3F\uFF41-\uFF5A\uFF66-\uFFBE\uFFC2-\uFFC7\uFFCA-\uFFCF\uFFD2-\uFFD7\uFFDA-\uFFDC])*$/;
+            if (keyPath.length >= 1 && validIdentifierRegex.test(keyPath)) {
+                return;
+            }
+        } catch (err) {
+            throw new SyntaxError(err.message);
+        }
+        if (keyPath.indexOf(" ") >= 0) {
+            throw new SyntaxError(
+                "The keypath argument contains an invalid key path (no spaces allowed).",
+            );
+        }
+    }
+
+    if (Array.isArray(keyPath) && keyPath.length > 0) {
+        if (parent) {
+            // No nested arrays
+            throw new SyntaxError(
+                "The keypath argument contains an invalid key path (nested arrays).",
+            );
+        }
+        for (const part of keyPath) {
+            validateKeyPath(part, "array");
+        }
+        return;
+    } else if (typeof keyPath === "string" && keyPath.indexOf(".") >= 0) {
+        keyPath = keyPath.split(".");
+        for (const part of keyPath) {
+            validateKeyPath(part, "string");
+        }
+        return;
+    }
+
+    throw new SyntaxError();
+};
+
+export default validateKeyPath;
diff --git a/packages/idb-bridge/src/util/valueToKey.ts b/packages/idb-bridge/src/util/valueToKey.ts
new file mode 100644
index 000000000..3a9e36786
--- /dev/null
+++ b/packages/idb-bridge/src/util/valueToKey.ts
@@ -0,0 +1,70 @@
+/*
+ Copyright 2017 Jeremy Scheff
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
+ or implied. See the License for the specific language governing
+ permissions and limitations under the License.
+ */
+
+
+import { DataError } from "./errors";
+import { Key } from "./types";
+
+// https://w3c.github.io/IndexedDB/#convert-a-value-to-a-input
+function valueToKey(input: any, seen?: Set<object>): Key | Key[] {
+    if (typeof input === "number") {
+        if (isNaN(input)) {
+            throw new DataError();
+        }
+        return input;
+    } else if (input instanceof Date) {
+        const ms = input.valueOf();
+        if (isNaN(ms)) {
+            throw new DataError();
+        }
+        return new Date(ms);
+    } else if (typeof input === "string") {
+        return input;
+    } else if (
+        input instanceof ArrayBuffer ||
+        (typeof ArrayBuffer !== "undefined" &&
+            ArrayBuffer.isView &&
+            ArrayBuffer.isView(input))
+    ) {
+        if (input instanceof ArrayBuffer) {
+            return new Uint8Array(input).buffer;
+        }
+        return new Uint8Array(input.buffer).buffer;
+    } else if (Array.isArray(input)) {
+        if (seen === undefined) {
+            seen = new Set();
+        } else if (seen.has(input)) {
+            throw new DataError();
+        }
+        seen.add(input);
+
+        const keys = [];
+        for (let i = 0; i < input.length; i++) {
+            const hop = input.hasOwnProperty(i);
+            if (!hop) {
+                throw new DataError();
+            }
+            const entry = input[i];
+            const key = valueToKey(entry, seen);
+            keys.push(key);
+        }
+        return keys;
+    } else {
+        throw new DataError();
+    }
+};
+
+export default valueToKey;