A large tree in IndexedDB with RxDB: indexes, trigram search and lazy loading

Personal OS, my time-management app, keeps a library of blocks: reusable activities that nest inside each other ("Weekend study" contains "Focus session 1", "Break", "Reading", and "Reading" has its own chapters). Everything lives in the browser, in IndexedDB through RxDB, and the library can grow without limit. This post covers what made a tree in IndexedDB slow, and the changes that made reading, searching and drawing it depend on what's on screen rather than on the size of the whole table: an index that RxDB couldn't build, a trigram search that ignores Vietnamese diacritics, lazy loading, virtualization, and tests that count queries instead of milliseconds.

A query that took 19.6 seconds for 61 nodes

Each block stores its parent in parent_id, which is null for top-level blocks. Loading a subtree meant asking for the children of one level at a time:

db.snapshot_nodes.find({ selector: { parent_id: { $in: parentIds } } })

That looks like an index lookup. It wasn't. A day's plan with two levels and 61 nodes, in a table of 2,061 nodes, took 19.6 seconds to load, because every level was a full scan of the table.

The reason is in RxDB's schema rules: indexes are only allowed on fields of type string, integer or number. A nullable field is declared as ["string", "null"], which is neither, so parent_id could never be indexed. Without an index, $in falls back to reading every document.

A non-null shadow column, filled by a hook

The obvious fix, storing a sentinel like "" in parent_id instead of null, would have broken dozens of places that check if (!block.parent_id) to mean "this is a root". So the fix adds a second column instead:

• parent_key is a non-null copy of parent_id, equal to it, or "" for a root. It exists only to be indexed; parent_id keeps its meaning everywhere else.
• A preInsert and preSave hook fills it on every write (repository calls, bulk inserts, upserts, migrations), so no code path can forget it.
• A schema migration backfills it for blocks that already exist on users' devices.

With that, loading a subtree is one indexed lookup per level, and the number of round trips is the depth of the tree (two or three in practice), not the number of nodes.

The same trick was later needed for category_id, for the same reason. A shadow column also has consequences for sync, which are a story of their own in four bugs that silently broke RxDB sync.

Read one branch at a time, not the whole table

Even with the index, the library page originally observed the whole table and derived the tree in JavaScript: build a map, group by parent, count children. Everything on the page cost time proportional to the total number of blocks.

Now the tree loads lazily:

• Roots and the children of each expanded branch are separate reactive queries on parent_key. Collapsing a branch drops its subscription.
• Breadcrumbs and detail panels walk up by findById instead of searching an in-memory copy of the table.
• Deleting or duplicating a subtree walks it breadth-first through the index.

A test checks the property that matters. It reads the 20 children of one branch in a table of 120 blocks, then again in a table of 2,020 blocks (16.8 times larger), and compares the times. When the page watched the whole table, the ratio would be close to 16.8; with the index it came out at about 0.95×, i.e. constant. The test fails if the ratio goes above 6, a generous margin because it runs on fake-indexeddb in CI.

Substring search without a full-text index

Search is harder. Users expect "contains" matching: typing "họp" should find "Cuộc họp nhóm". An index on title can only help with prefixes, and RxDB has no full-text search, so the first version loaded every block and filtered in JavaScript.

The fix is a small inverted index in the style of a search engine, kept in its own local-only collection that is never synced:

1. Normalize the text: strip Vietnamese diacritics, lowercase, collapse spaces. NFD decomposition removes most marks, but đ is its own letter in Unicode, not d plus a mark, so it needs an explicit rule.
2. Split into trigrams, overlapping three-character pieces: "cuoc hop" gives cuo, uoc, oc , c h, ho, hop.
3. Store one row per (block, trigram) with an index on the trigram.
4. To search, split the query the same way, fetch the rows matching any of its trigrams with one indexed $in, then verify each candidate by checking that its normalized title really contains the normalized query. Results are ranked by how many trigrams matched.

export function normalizeForSearch(text: string): string {
  return text
    .normalize('NFD')
    .replace(/[̀-ͯ]/g, '')
    .replace(/đ/g, 'd')
    .replace(/Đ/g, 'd')
    .toLowerCase()
    .replace(/\s+/g, ' ')
    .trim()
}

Because both sides are normalized, typing without diacritics ("hop") finds "họp", which is how many Vietnamese users type on a laptop.

A few practical details:

• The index is updated explicitly by the commands that create, rename, duplicate, delete or undo blocks, not by a generic observer. A rename deletes the block's old trigrams before inserting new ones, since a shorter title loses some.
• Primary keys can't contain leading or trailing spaces in RxDB, and trigrams often do ("oc "), so the row ID encodes the trigram while the indexed field keeps its real value.
• Existing libraries are backfilled in the background on startup, page by page with an ID cursor, so the whole table is never loaded into memory at once.
• Trigrams need at least three characters. Queries shorter than that can't use the index, which is a general limit of the technique worth planning for.

Draw only the rows on screen

The tree used to render recursively: every expanded node was in the DOM. A library with thousands of open blocks meant thousands of rows.

The tree is now flattened into a list in pre-order, descending only into expanded nodes, so every visible row is one array element with its depth. That list goes to TanStack Virtual, which mounts only the rows in the viewport plus a small overscan.

One view deliberately isn't virtualized: the day editor. Its drag and drop between nesting levels needs every sortable item in the DOM, and a day has a few dozen nodes, so the benefit is small and the risk real.

A depth limit, for usability rather than speed

Blocks can nest at most 8 levels deep. The real costs come from fan-out and total size, which the changes above handle; depth is limited because a pathological tree is unusable and recursive code paths deserve a bound. Moving a whole subtree checks the parent's depth plus one plus the height of the moved subtree, since a node being dragged can be fine while its grandchildren would cross the limit.

There is deliberately no limit on how many children a block can have: a day with many blocks is a valid use, and the expensive paths for wide trees (rendering and deletion) are handled directly.

Count queries in tests, not milliseconds

Timing tests on CI machines are noisy. Most of the performance tests in this codebase count instead:

• How many queries an operation makes. Copying a week forward used to call count() once per day for every week ahead, about 364 queries for a year; it now makes one range query. Importing a file did one findOne per row and now does one find plus one bulkUpsert. The tests assert the query counts, so an N+1 pattern coming back fails the build.
• Which plan the database uses. On the server, tests run EXPLAIN on a real PostgreSQL with 50,000 rows and assert that the sync pull uses an index scan, not a sequential scan. If someone drops or changes the index, the test turns red, independently of how fast the CI machine is.

Summary

These changes were made and tested at the scale of thousands of blocks, with the goal that nothing on screen depends on the total size. The common thread is simple: in IndexedDB as in a server database, check that the query you think is indexed actually is.

If you've kept a large tree fast in IndexedDB or RxDB, I'd love to compare notes. My email is on the home page.