B-trees and database indexes (2024)

Oh hey, I wrote this! Happy to chat more about the article here. Databases are kinda my thing.

This has been post before, but planetscale also has a great sql for developers course:

https://planetscale.com/learn/courses/mysql-for-developers

I've known for a long time that you usually want b-tree in Postgres/MySQL, but never understood too well how those actually work. This is the best explanation so far.

Also, for some reason there have been lots of HN articles incorrectly advising people to use uuid4 or v7 PKs with Postgres. Somehow this is the first time I've seen one say to just use serial.

Also curious to hear what people think of Bf-tree.

  https://vldb.org/pvldb/vol17/p3442-hao.pdf
  https://github.com/microsoft/bf-tree

"The deeper the tree, the slower it is to look up elements. Thus, we want shallow trees for our databases!"

With composite indices in InnoDB it's even more important to keep the tree streamlined and let it fan out according to data cardinality: https://news.ycombinator.com/item?id=34404641

Past comments: https://news.ycombinator.com/item?id=41489832

I keep hearing about the downside of B(+)-Trees for DBs, that they have issues for certain scenarios, but I've never seen a simple, detailed list about them, what they are, and the scenarios they perform badly in.

A B+ tree with deletion was one of the most difficult algorithms I had to do back in college. You'd hit edge cases after billions of insertions...

interactive viz on this kind of topic is just unfair compared to text

Sqlite’s btree is available here:

https://github.com/sqlite/sqlite/blob/master/src/btree.c

I always thought this was too complicated to every really understand how it worked, especially the lock policy, but now with LLMs (assisted with sqlite’s very comprehensive comment policy) even a relative neophyte can start to understand how it all works together. Also the intro to the file is worth reading today:

* 2004 April 6 * * The author disclaims copyright to this source code. In place of * a legal notice, here is a blessing: * * May you do good and not evil. * May you find forgiveness for yourself and forgive others. * May you share freely, never taking more than you give. * ************************************* * This file implements an external (disk-based) database using BTrees. * See the header comment on "btreeInt.h" for additional information. * Including a description of file format and an overview of operation. */

> MySQL, arguably the world's most popular database management system,

[dead]