How a B-Tree Really Reads, Inserts, Updates and Deletes (and Where It Fails a Blockchain Indexer)

Every indexer I have worked on started the same way. Someone creates the transactions table, adds an index on every column the API might filter by, and ships. For the first hundred million rows, everything is fast.

Then ingestion starts falling behind the chain. The wallet history endpoint is still quick, but the balance updater takes twice as long per block as it did last month. Disk usage grows faster than row count. A cleanup job deletes old spam events and the table gets no smaller.

None of that is necessarily a bug. The database is doing exactly what its indexes require. The workload has simply outgrown the assumptions behind the original schema.

This post walks through what a B-tree physically does on each of the four operations, using PostgreSQL's implementation, and then applies that to the tables of a real blockchain indexer: blocks, transactions, coins, fungible assets, NFTs, digital assets, wallet history and portfolio. For each one, the question is the same: is a B-tree the right tool here, and if not, what is?

The Shape: A Dictionary With a Table of Contents

A B-tree is a sorted dictionary with a table of contents stacked on top of it.

• Leaf pages hold the actual entries: a key (say, a wallet address) and a pointer to the row in the table (Postgres calls this pointer a TID, the physical location of the row). Leaf pages are sorted and linked to their neighbors, left and right, like pages in a book.
• Internal pages hold no rows. They hold signposts: "keys below X are on this page, keys from X onward are on that one."
• The root is the single page at the top. In a small index, the root is itself the only leaf, and internal levels appear as the index grows.

                    [ root: ... | 0x5a.. | 0xb3.. | ... ]
                       /              |              \
        [ internal ]           [ internal ]          [ internal ]
         /    |    \             /    |    \           /    |    \
     [leaf]<->[leaf]<->[leaf]<->[leaf]<->[leaf]<->[leaf]<->[leaf] ...

Each page is 8 KB in Postgres. As an illustrative estimate, a leaf page of bigint keys holds a few hundred entries once you account for per-entry overhead (the row pointer, the line pointer) and the free space left by the fillfactor. Internal pages fan out by a similar order of magnitude. That fanout is the whole trick. Depending on key size, page occupancy and deduplication, an index with tens of millions of entries may be three or four levels deep, and one with billions may need another level. Depth grows logarithmically with row count, not linearly.

Why this matters in production: an index traversal touches only a handful of pages, and the upper levels are touched by every query, so they tend to stay cached. Fetching the matching heap row can still cost extra I/O, but the search itself stays cheap even on enormous tables. This is why "just add an index" works so well for so long.

Read: Walk Down, Then Walk Right

A point lookup like WHERE tx_version = 912345678 works like finding a word in a dictionary:

1. Read the root. Binary search its signposts to pick a child.
2. Repeat on each internal page until you reach a leaf.
3. Binary search the leaf for the key. It gives you a TID.
4. Fetch the row from the table (the heap) at that TID.

Step 4 matters more than people expect. In Postgres, the index does not know whether a row is visible to your transaction. That information lives in the heap. So a normal index scan pays one extra page read per matching row to check visibility. The exception is an index-only scan: if every column the query needs is in the index, and the visibility map says the heap page is all-visible, Postgres skips the heap entirely.

Range queries are where B-trees really shine. WHERE sender = $1 ORDER BY tx_version DESC LIMIT 50 descends once to the right spot, then walks sideways along the linked leaf pages, reading entries that are already in the order you asked for. No sort step. No scanning unrelated rows.

Why this matters in production: "latest 50 transactions for this wallet" is one descent plus one or two leaf pages, whether the table has a million rows or ten billion. That query shape is the B-tree's home ground, and a wallet explorer is mostly made of it.

Insert: Find the Page, Make Room, Sometimes Split

An insert starts as a read. Postgres descends to the leaf where the new key belongs, then:

• If the leaf has free space, the entry goes in, in sorted position. Done.
• If the leaf is full, the page splits. Postgres allocates a new page, moves roughly half the entries into it, links it into the leaf chain, and inserts a new signpost into the parent. If the parent is also full, the parent splits too. If the split climbs all the way up, the root splits and the tree gets one level taller.

For a unique index, there is one extra step: before inserting, Postgres checks the leaf for an existing live entry with the same key. That is how PRIMARY KEY and ON CONFLICT work.

Where the new key lands decides everything:

• Increasing keys (block height, transaction version, a sequence) always land on the rightmost leaf. Postgres has a fast path for this: it remembers the rightmost leaf and skips the descent when it can. And when the rightmost page splits, it leaves the old page packed full (to the index's fillfactor, 90% by default) instead of half empty, because nothing will ever be inserted to its left again.
• Random keys (transaction hashes, UUIDv4, wallet addresses) land on a random leaf every time. Insert activity is spread across the whole index instead of one edge, so the working set is much larger, and splits tend to leave pages around half full.

I covered the random-key case with numbers in the UUID post. The short version: the same number of rows can produce a bigger index, and as its working set grows beyond what the cache holds, inserts are more likely to need extra page reads and writes.

Why this matters in production: an indexer inserts millions of rows per day into tables keyed by both kinds of value. The tx_version index stays compact and its hot edge stays cached. The tx_hash index on the same table touches pages all over the index, and at scale it is a likely candidate for the slowest part of the ingest path.

Update: There Is No Such Thing as Updating an Index Entry

This is the part most engineers get wrong, and it is the most important one for an indexer.

In Postgres, UPDATE does not modify a row in place. Because of MVCC, it writes a new version of the row somewhere in the heap and marks the old one as expired. The new version has a new physical location. So every index on the table now has an entry pointing at the old location and nothing pointing at the new one.

The default consequence: an UPDATE that can't use HOT (below) generally needs new index entries for the new row version in every index on the table, including indexes whose values did not change. Updating only amount on a balances table with five indexes can therefore mean index maintenance across all five. That adds CPU, WAL and write overhead on every update. Depending on how full the target pages are and what cleanup is possible, some of those insertions can also trigger page splits.

There is one escape hatch, and it is worth designing around: the HOT update (Heap-Only Tuple). If the update changes no column that any index depends on, and the new row version fits on the same heap page as the old one, Postgres chains the new version off the old one and touches no indexes at all. The existing index entries still lead to the right row by following the chain.

"Depends on" is broader than it sounds. It includes columns used inside expression indexes (lower(name)) and columns in a partial index's WHERE clause, not just columns listed directly in an index. (Since Postgres 16, summarizing indexes like BRIN are the exception: they no longer block HOT.)

Two conditions, both under your control:

1. Don't index columns that change often. One index on amount disables HOT for every balance change.
2. Leave free space on heap pages with a table fillfactor below 100, so the new version has room on the same page.

Postgres 14 added bottom-up index deletion, which removes the obsolete version entries that non-HOT updates leave in indexes whose values didn't change, often before they force a page split. It reduces the bloat. It does not make the insertions free.

An index is not free just because no query uses it during an update. Its mere presence decides whether Postgres can use HOT and skip touching indexes altogether.

Note also that changing an indexed key never edits the entry. The old entry stays until vacuum removes it, and a new one is inserted where the new value sorts.

Why this matters in production: a "current balances" table updated on every transfer is the most write-heavy table in an indexer. Whether those updates are HOT is often the difference between the balance updater keeping up with the chain or not.

Delete: Mark Now, Clean Later, Never Shrink

DELETE in Postgres removes nothing immediately. It marks the heap row as expired. The index entries stay exactly where they are, still pointing at the dead row.

Cleanup happens in layers:

1. Kill bits. When an index scan follows an entry to a row that is dead to everyone, it marks that index entry as dead so future scans skip it.
2. Opportunistic cleanup. When an insert finds a leaf full, Postgres first tries removing dead entries from that page before splitting it.
3. VACUUM. The real cleanup. It scans the indexes, removes entries pointing to dead rows, and only then lets the heap space be reused.

And here is the part that surprises people: Postgres does not merge partially filled B-tree pages just because their occupancy drops. Vacuum removes dead entries and can reclaim pages that become completely empty, but a page that is still 40% full stays a page. Delete a large fraction of rows spread across the key range, and the index will not shrink in proportion. The freed space is reusable for future inserts into those key ranges, but it is not given back.

Why this matters in production: pruning old events with DELETE ... WHERE tx_version < X leaves the table and indexes the same size, generates a burst of WAL, and creates vacuum work. If you plan to drop data by age or range, partition by that range and DROP or DETACH the old partition. That removes the table and all of its indexes as files, with no dead rows to clean up.

Where B-Trees Hurt

The four operations above give you the failure list directly:

A note on the alternatives, because each has its own cost:

• BRIN stores only the min and max value per block of table pages (128 pages by default). When the column's values follow the physical order of the table, it can be thousands of times smaller than a B-tree. When they don't, it is nearly useless. Check the actual correlation (pg_stats.correlation) before relying on it.
• Hash indexes store a 4-byte hash code per row instead of the key, which can make them smaller than a B-tree on a wide key. But in Postgres they are equality-only, single-column, can't serve ordered or range scans, and cannot enforce uniqueness. Whether they are actually faster for your lookups is something to benchmark, not assume.
• GIN handles "does this JSONB contain X." Its write cost is higher than a B-tree's, and it buffers new entries in a pending list that gets merged later.
• LSM-trees make writes cheap by deferring the sort to background compaction, and pay for it on reads and in compaction I/O. The Cassandra post covers that trade in depth. Aptos nodes use RocksDB, an LSM engine, as part of their storage layer. An indexer serves a different job: turning chain data into relational records that support flexible queries. The two have different requirements, so their storage choices aren't interchangeable.

The Indexer, Table by Table

Here is how this plays out for a Move-chain indexer (Supra, Aptos), with the queries an explorer and wallet API actually serve. I'll assume addresses and hashes are stored as 32-byte bytea, not 66-character hex text. That choice alone roughly halves the key size of every index that contains one, as covered in Your Blockchain Indexer Is Fine Until It Isn't.

Blocks

CREATE TABLE blocks (
  height        bigint PRIMARY KEY,      -- B-tree, append-only, rightmost inserts
  block_hash    bytea  NOT NULL,
  first_version bigint NOT NULL,
  last_version  bigint NOT NULL,
  block_time    timestamptz NOT NULL
);
CREATE UNIQUE INDEX blocks_hash_uidx ON blocks (block_hash);
-- or, if uniqueness is enforced outside the database:
-- CREATE INDEX blocks_hash_idx ON blocks USING hash (block_hash);
CREATE INDEX blocks_time_brin ON blocks USING brin (block_time);

• height: B-tree. Perfect case. Monotonic, never updated, "latest blocks" is a backward walk from the right edge.
• block_hash: hash index or unique B-tree, depending on what the database must guarantee. It is only ever looked up by equality. Note that the height primary key does not make block_hash unique. If you want the database to enforce unique block hashes, use CREATE UNIQUE INDEX ... ON blocks (block_hash), which has to be a B-tree. If you have decided to trust the chain and your ingestion code for that invariant, a non-unique hash index is worth benchmarking.
• block_time: BRIN. Blocks are inserted in time order, so the physical correlation should be near perfect (verify it in pg_stats). "Blocks between 10:00 and 11:00" needs nothing more.

Honestly, the blocks table is small enough that the index choices barely matter. They matter on the next one.

Transactions

CREATE TABLE transactions (
  version      bigint PRIMARY KEY,       -- global, increasing
  tx_hash      bytea  NOT NULL,
  sender       bytea,
  block_height bigint NOT NULL,
  success      boolean NOT NULL,
  gas_used     bigint,
  payload      jsonb
);
CREATE UNIQUE INDEX tx_hash_uidx ON transactions (tx_hash);
-- or, if uniqueness is enforced outside the database (benchmark first):
-- CREATE INDEX tx_hash_idx ON transactions USING hash (tx_hash);
CREATE INDEX tx_sender_ver_idx  ON transactions (sender, version DESC);
CREATE INDEX tx_block_brin      ON transactions USING brin (block_height);

• version: B-tree. Same as block height. It is also your idempotency key: re-ingesting a batch uses ON CONFLICT (version) DO NOTHING, so replays don't create duplicate rows. (In the JSONB TOAST post I keyed transactions by tx_hash to keep the example focused on JSONB. For a real indexer, the increasing version is the better primary key, for exactly the insert reasons above.)
• tx_hash: a design decision, not a default. Version uniqueness and hash uniqueness protect different things. The version key stops the same transaction version from being stored twice. It does not stop two rows from carrying the same hash. If "one hash, one row" must be enforced by the database, keep CREATE UNIQUE INDEX ... ON transactions (tx_hash), which has to be a B-tree. If you trust the chain and ingestion for that invariant and the column only serves "look up this transaction," a hash index is a candidate: hashes are uniformly random, so a B-tree on them gets the random-insert treatment described above, on your largest table, while the hash index stores a 4-byte hash value in its entries (plus tuple and page overhead). That does not guarantee it ends up smaller or faster overall, since B-trees have their own advantages such as deduplication. Benchmark both on your own data before switching, and make sure the API handles a lookup returning more than one row instead of assuming it can't.
• (sender, version DESC): composite B-tree. This is wallet transaction history, and it is the textbook B-tree query: one descent to the sender, then walk the leaves in version order. Don't create a separate index on sender alone. The composite one already serves it.
• block_height: BRIN, since version and height rise together and rows are inserted in that order (again, verify the correlation, especially after backfills).
• success: no index. Almost every row is true. If you need failed transactions, CREATE INDEX ... WHERE NOT success indexes only the rare ones.
• payload: no index by default. If you need to filter by entry function, extract it into its own column at ingest and B-tree that, rather than GIN-indexing the whole payload.

Coin and Fungible Asset Activity (transfers)

Every deposit and withdrawal for both legacy 0x1::coin coins and 0x1::fungible_asset FAs, one row per event. Append-only, never updated, and the biggest table in the database.

CREATE TABLE fa_activities (
  version      bigint NOT NULL,
  event_index  int    NOT NULL,
  owner        bytea  NOT NULL,
  asset_type   bytea  NOT NULL,   -- coin type hashed, or FA metadata address
  amount       numeric NOT NULL,
  kind         smallint NOT NULL, -- deposit / withdraw / mint / burn
  PRIMARY KEY (version, event_index)
);
CREATE INDEX fa_owner_ver_idx ON fa_activities (owner, version DESC);
CREATE INDEX fa_asset_ver_idx ON fa_activities (asset_type, version DESC);

• Wallet transfer history: (owner, version DESC). B-tree.
• Coin transaction history ("all USDC transfers, newest first"): (asset_type, version DESC). B-tree.
• Match the index to your pagination cursor. One transaction can emit several events for the same wallet, so a cursor of version alone is ambiguous. If the API paginates on (version, event_index), use (owner, version DESC, event_index DESC) and WHERE owner = $1 AND (version, event_index) < ($2, $3) so the index serves both the filter and the order.
• Coin type strings like 0x1::supra_coin::SupraCoin can be long, and legacy coin types can be very long once generics are involved. Hash them into a fixed 32-byte key with a lookup table, instead of putting a variable-length string into two of your biggest indexes.
• No index on amount. "Largest transfers" is an analytics query. Serve it from a rollup or a columnar store.
• Partition by version range if you will ever prune or archive. This table is where a DELETE-based retention job would hurt the most.

Wallet Portfolio (current balances)

This is the table where B-tree update behavior decides whether you keep up with the chain.

CREATE TABLE current_balances (
  owner       bytea   NOT NULL,
  asset_type  bytea   NOT NULL,
  amount      numeric NOT NULL,
  last_version bigint NOT NULL,
  PRIMARY KEY (owner, asset_type)
) WITH (fillfactor = 80);

• (owner, asset_type) primary key: B-tree. "Show this wallet's portfolio" is one descent and a short leaf walk.
• Nothing else. amount and last_version change on every transfer. As long as neither is indexed (directly, in an expression, or in a partial index predicate), and the fillfactor leaves room on each heap page, most balance updates can be HOT and touch zero indexes. Treat 80 as a starting point to measure, not a magic number: watch n_tup_hot_upd against n_tup_upd in pg_stat_user_tables.
• The trap: someone adds (asset_type, amount DESC) to serve a "top holders" page. From that moment, every balance change is a non-HOT update that inserts into both indexes. On a busy token, this is the table that starts lagging first.
• Top holders belongs in a separate table refreshed every few minutes, or computed in your analytics store. It is a ranking, and rankings don't need to be correct to the transaction.

Historical Balances (balance at a point in time)

If you support "what did this wallet hold at version X," keep an append-only table:

CREATE TABLE balance_history (
  owner      bytea   NOT NULL,
  asset_type bytea   NOT NULL,
  version    bigint  NOT NULL,
  amount     numeric NOT NULL,
  PRIMARY KEY (owner, asset_type, version)
);
 
SELECT amount FROM balance_history
WHERE owner = $1 AND asset_type = $2 AND version <= $3
ORDER BY version DESC
LIMIT 1;

This is a B-tree at its best. With owner and asset_type fixed by equality, Postgres can use the composite index to find the latest version not greater than X and return that row without scanning the wallet's history. No other structure answers "the last value before this point" as cheaply.

NFTs and Digital Assets

Move chains have two NFT standards, and they want different key designs (the Coins, FAs and NFTs guide covers the data model itself):

• Legacy 0x3 tokens are identified by creator, collection name, token name and property version. That is a wide, variable-length text key. Hash it into a 32-byte token_id at ingest and index that.
• 0x4 Digital Assets are objects, so the token already has a 32-byte address. Use it directly.

-- current owner of each token: churns on every transfer
CREATE TABLE current_token_ownership (
  token_id      bytea  PRIMARY KEY,
  owner         bytea  NOT NULL,
  amount        numeric NOT NULL,
  last_version  bigint NOT NULL
) WITH (fillfactor = 80);
CREATE INDEX cto_owner_idx ON current_token_ownership (owner);
 
-- every movement, append-only
CREATE TABLE token_activities (
  version     bigint NOT NULL,
  event_index int    NOT NULL,
  token_id    bytea  NOT NULL,
  from_addr   bytea,
  to_addr     bytea,
  PRIMARY KEY (version, event_index)
);
CREATE INDEX ta_token_ver_idx ON token_activities (token_id, version DESC);
 
-- metadata
CREATE TABLE token_data (
  token_id      bytea PRIMARY KEY,
  collection_id bytea NOT NULL,
  name          text  NOT NULL,
  attributes    jsonb
);
CREATE INDEX td_collection_name_idx ON token_data (collection_id, name);
CREATE INDEX td_attributes_gin ON token_data USING gin (attributes jsonb_path_ops);

• "NFTs in this wallet": B-tree on current_token_ownership (owner). Here we do index a changing column, deliberately, because it is the query the wallet page depends on. Accept that ownership changes are non-HOT, and keep this the only secondary index on the table.
• NFT movement history: (token_id, version DESC) on the append-only activity table. B-tree.
• Collection listing sorted by name: (collection_id, name). B-tree.
• "Tokens in this collection with Background = Gold": that is a containment query, attributes @> '{"Background": "Gold"}'. GIN with jsonb_path_ops is usually smaller than the default jsonb_ops and supports @> (plus the jsonpath operators @? and @@), but not the key-existence operators ?, ?| and ?&. If your API asks "has this attribute at all," you need jsonb_ops. A B-tree cannot help with either.

Analytics: Daily Volume, Unique Wallets, Holder Counts

Don't add B-trees to the OLTP tables for these. Questions that read most of the history are not what a B-tree is for, and every index you add to serve a dashboard is paid for on every ingest. Push activity into a columnar store, or maintain rollup tables updated per block. For distinct counts specifically, a HyperLogLog sketch estimates the number of unique wallets in a few kilobytes, with a tunable accuracy-versus-space trade-off. That is fine for dashboards, and very different from the exact balances an explorer must serve. The technique is discussed in my wallet uniqueness system case study.

The Cheat Sheet

The Takeaway

A B-tree is a sorted dictionary that is cheap to search and expensive to keep sorted. Every read is a descent and a walk. Every insert might split a page. Every update in Postgres is an insert into every index, unless you keep it HOT. Every delete leaves a hole that never closes on its own.

An indexer is a machine that turns blockchain events into those four operations at high volume. Design each table by asking which of the four it does most, and the index choices mostly make themselves: B-trees for ordered history and enforced uniqueness, hash indexes as a benchmarked option for random equality lookups, BRIN for time, GIN for containment, partitions for retention, and somewhere else entirely for analytics.

If you want the full page-level detail on nbtree, HOT updates, and the other index types, Module A-5: Index Internals in the PostgreSQL In-Depth course goes deeper, and Storage Engines: B-Trees vs LSM-Trees in the System Design course covers the other side of the trade.