Ben

You're probably sick of me saying "B-tree" but these impact SO MUCH of database performance. They're used all over the place in Postgres, MySQL, and SQLite. This week I broke down B-tree lookups and how the page cache makes lookups faster.

If databases fascinate you like they do me, this article's for you! Every time you interact with a website, database transactions are keeping your data consistent, safe, and isolated. I wrote an interactive guide to how they work ⬇️

R-trees are a powerful structure for indexing geometric data. They’re used by MySQL, and Postgres uses an R-tree-like structure via GiST in PostGIS. 🧵

Moving up the tree, the bounding rectangles get larger and larger, up to the root node storing a small number of large bounding boxes.

R-trees are a powerful structure for indexing geometric data. They’re used by MySQL, and Postgres uses an R-tree-like structure via GiST in PostGIS. 🧵

They function similarly to B-trees: It’s a tree structure with multiple entries at each page-aligned node. This generally keeps the trees nice and shallow, and allows for efficient lookups for millions of elements stored on-disk. It also generally only stores data values at the leaves, like B+trees.

I'm excited about the database performance io_uring will unlock. Last year I benchmarked Postgres 17 vs 18 to test the initial io_uring upgrades. I was surprised to see they weren't always a clear win for TPC-C. This paper studies the potential, and the future looks good.

Software at scale reveals the cracks. Managing a system for a single use-case (databases or otherwise) can make it seem like a perfect solution. It just might be for that narrow environment! At scale you see all the edge cases because you're operating on so many workloads.

What do Git, Cursor, and Dynamo have in common? Merkle trees! A great data structure for tracking file changes, facilitating incremental sync with remote servers. Say we want to track changes to a codebase at a per-file level. We compute a hash for each source file, and these become leaf nodes.

When syncing local file changes with a remote server (like Git) we can quickly tell if changes were made by comparing the client's root hash to the server's. If they differ, the tree is navigated to find the leaf node(s) with changes, and only those files need to be re-synced.

What do Git, Cursor, and Dynamo have in common? Merkle trees! A great data structure for tracking file changes, facilitating incremental sync with remote servers. Say we want to track changes to a codebase at a per-file level. We compute a hash for each source file, and these become leaf nodes.

If 2026 is the year of AI, it's also the year to read more papers. LLMs make writing code cheaper. This places greater emphasis on architectural choices, understanding design tradeoffs, ensuring security, and building things people actually need. Great example: yesterday I read the Dynamo paper.

Merkle trees, consistent hashing, vector clocks, gossip protocols, and quorum algorithms were all previously known and had been used to build other software. But their unique combination to build Dynamo worked super well for Amazon's use-case, and helped them to scale to millions of DAU.

If 2026 is the year of AI, it's also the year to read more papers. LLMs make writing code cheaper. This places greater emphasis on architectural choices, understanding design tradeoffs, ensuring security, and building things people actually need. Great example: yesterday I read the Dynamo paper.

2026 is the year to end TikTok brain. Instead, learn database internals on YouTube. Speaking of which, another dropped today (link below).

Amazing how one simple idea can revolutionize an industry. Binary search trees were invented in 1960. It seems obvious today, but this was a fresh way of thinking about ordered data on computers.

PSA to my Postgres people: use a connection pooler. Incredible article on when and why to use PgBouncer. Includes a great explanation of how increasing direct connections leads to more contention → degraded performance. (+ benchmarks too!)

Log structures are all over the place in databases, but did you know they are used in file systems too? This week I re-read the iconic LFS paper by Rosenblum / Ousterhout. The differences between I/O demands on a database vs a general-purpose FS are neat to study.