PostgreSQL's B-tree indexes are the unsung heroes behind your fast queries. For core understanding of indexed, please read this fantastic article https://planetscale.com/blog/btrees-and-database-indexes. This article is just a follow-up with some details that I find interesting to share. But really, check the article above, it has fancy animations, is super interactive, and well described. This article expects you to understand the core principles of indexing, B+Tree, root | inner | leaf nodes. So, now we’re ready to dig in.

❕Also, in the article, I’ll sometimes call “B+Tree” just “B-Tree” for better readability; most popular SQL databases use “B+Tree” in their index implementations.

In B+Tree, we have a core concept like inner page(node)That is crucial for a better understanding of indices.

Non-leaf(inner + root) nodes store only keys and the associated child pointers.

Fan-out is the number of children an internal node in a tree can point to.

The inner page stores a sorted list of separator keys and, for each slot, a child pointer (downlink) to another index page.

Each downlink implicitly covers a key range determined by the separator keys around it. You can play around here: https://bplustree.app/

1. Big Inner Nodes vs. Small Inner Nodes 🤔

When we talk about the "size" of inner nodes in a B-tree, we're really thinking about how many keys and pointers (references to child nodes) can fit within a single fixed-size page (typically 8KB in PostgreSQL). This design choice profoundly impacts performance.

Advantages of Big Inner Nodes (Fewer Levels of Nesting) 🚀

• Fewer Disk I/O Operations: If an inner node can point to many children, you'll traverse fewer levels to find your data. Each level often means another slow disk read.
• Better Cache Utilization: Bigger fan-out can bring more relevant data into RAM (PostgreSQL's shared buffers) with a single disk read, reducing future cache misses. 🧠✨

Disadvantages of Big Inner Nodes 🐢

• More Memory Per Node (when loaded): While good for I/O, a larger node consumes more RAM when loaded into cache. If not fully utilized, it might seem a bit wasteful.
• Slower Node Updates: When a node needs to split or mergei due to data changes (inserts/deletes), there's more data to shuffle around, which can be marginally slower.
• Higher CPU Cost for In-Node Search: Searching within a larger node for the correct pointer might take a tiny bit more CPU, but this is usually negligible compared to disk I/O.

Advantages of Small Inner Nodes (More Levels of Nesting) 🤏

• Lower Memory Per Node (when loaded): Individually, smaller nodes use less RAM.
• Faster Node Updates (Potentially): Less data to move during splits/merges. Ideal for extremely high-churn scenarios.