B-trees and database indexes (2024)

Thanks for writing this! The visualisations really drive a better understanding than pure text does, and it's quite clear that you have a better understanding of what database do under the hood than I do.

As such, I have a question for you: contrary to your article, I've always been taught that random primary keys are better than sequential ones. The reason for this, I was told, was to avoid "hotspots". I guess it only really applies once sharding comes into play, and perhaps also only if your primary key is your sharding key, but I think that's a pretty common setup.

I'm not really sure how to formulate a concrete question here, I guess I would like to hear your thoughts on any tradeoffs on sequential Vs random keys in sharded setups? Is there a case there random keys are valid, or have I been taught nonsense?

I remember this article for when I was researching for https://spacetimedb.com/. The interactivity is very cool, BTW!

One neat realization is that a database is in fact more about indexes than the actual raw tables (all things interesting work under this assumption), to the point that implementing the engine you get the impression that everything start with "CREATE INDEX" than "CREATE TABLE". This includes sequential scans, where as visualized in your article show that lay the data sequentially is in fact a form of index.

Now, I have the dream of make a engine more into this vision...

> incorrectly advising people to use uuid4 or v7 PKs with Postgres

random UUIDs vs time-based UUIDs vs sequential integers has too many trade-offs and subtleties to call one of the options "incorrect" like you're doing here.

just as one example, any "just use serial everywhere" recommendation should mention the German tank problem [0] and its possible modern-day implications.

for example, if you're running a online shopping website, sequential order IDs means that anyone who places two orders is able to infer how many orders your website is processing over time. business people usually don't like leaking that information to competitors. telling them the technical justification of "it saves 8 bytes per order" is unlikely to sway them.

0: https://en.wikipedia.org/wiki/German_tank_problem

DB perf considerations aside, a lot of software pattern around idempotency/safe retries/horiz-scaling/distributed systems are super awkward with a serial pk because you don’t have any kind of unambiguous unique record identifier until after the DB write succeeds.

DB itself is “distributed” in that it’s running outside the services own memory in 99% of cases, in complex systems the actual DB write may be buried under multiple layers of service indirection across multiple hosts. Trying to design that correctly while also dealing with pre-write/post-write split on record id is a nightmare.

Simple sequential IDs are great. If you want UUID, v7 is the way to go since it maintains sequential ordering.

> just use serial

Ideally you use IDENTITY with Postgres, but the end result is the same, yes.

If your application is write intensive LSM is better than Btree.

But you'd rarely need it. We mostly have write intensive counters. We just write to redis first then aggregate and write to postgres.

This reduces number of writes we need in postgres a lot

It's really just a matter of tradeoffs. B-trees are great, but are better suited for high read % and medium/low write volume. In the opposite case, things like LSMs are typically better suited.

If you want a comprehensive resource, I'd recommend reading either Designing Data Intensive Applications (Kleppman) or Database Internals (Petrov). Both have chapters on B-trees and LSMs.

See my comment in the main thread for an example. In a worst case scenario, some data is simply too "frizzy" to index/search efficiently and with good performance in a B-tree.

For pure write throughput, LSM trees tend to beat btrees.

I've read this paper and it's a neat idea. It hasn't been introduced into popular oss databases like postgres and mysql, and my understanding is it has some drawbacks for real prod use vs ths simplistic benchmarks presented in the paper.

Would love to know if anyones built something using it outside of academic testing.

It may not have the popularity it once did, but MySQL still powers a huge % of the internet.

Is there a problem with that?