do you ever start a project get halfway through it and realize the whole thing is just held together by duct tape and questionable life choices and just leave it unfinished instead of fixing it because life is pointless and entropy is unavoidable and the universe is filled with callous and casual destruction
B-Trees are one of the most important data structures in database internals, yet most of us barely explore them
almost every time you create an index in postgres or mysql, there's a good chance a B-Tree or one of its variations is used
but why do databases prefer B-Trees over traditional binary search trees, AVL trees, or red black trees?
it's how computers store and access data , lets see this from first principles
A balanced BST can search among a 1e6 elements in ~20 comparisons which is very efficient, but there's a problem
Databases deal with data that often doesn't fit entirely in RAM. They store data on disk in fixed size blocks called pages, and accessing a page from disk is much more expensive than comparing two integers in memory
In a traditional BST, each node contains one key and at most two child pointers, traversing the tree may require jumping between multiple memory locations or disk pages
what if instead of storing just one key per node, we stored hundreds of sorted keys in a single node?
unlike BST, B-Trees are multiway search trees where each node can hold multiple keys and have multiple children.
for example, a node might look like,
[10 | 20 | 30 | 40]
these keys divide the search space into five different ranges, and if each node can branch into 100 children, a tree with only a few levels can organize millions of records.
this is possible because B-Trees are designed to fit many keys into a single database page, significantly reducing the number of page accesses needed during traversal.
all leaf nodes remain at the same depth, when a node becomes full during insertion, it can split and propagate a separator key upward, deletions may involve redistribution or merging
this keeps the tree balanced without rebuilding the entire structure, this is called self balancing
some examples of usages of B-Trees in systems -
Database indexing - postgres and mysql use B-Tree style indexes to locate records without scanning the entire table
Range queries - queries like "WHERE age BETWEEN 20 AND 30" benefit from the sorted arrangement of keys.
Sorting - an index can help databases efficiently process ORDER BY queries without requiring a separate sorting operation
Storage engines - B-Tree variations help organize large amounts of data while minimizing expensive storage accesses
Filesystems - B-Tree based structures are also used to manage file metadata and other on disk structures.
there's also an important variation called the B+ Tree,
in a B+ Tree, internal nodes primarily guide the search, while actual indexed entries are stored at the leaf level. leaf nodes are typically linked, making sequential and range based traversal efficient.
this is especially useful for databases because queries don't always search for a single key. They frequently retrieve an entire range of sorted records.
every additional index consumes storage and introduces overhead during inserts, updates, and deletes. page splits and index maintenance can make writes more expensive
that's why creating indexes on every column isn't necessarily a good idea.
the interesting part is that B-Trees don't fundamentally improve the asymptotic search complexity over balanced binary search trees
both provide O(log n) operations.
💀
who wants to be a millionaire?
i actually want to know if your account on X is worth $1M
go check this out myaccworth.com
bro is mocking a 28 batch student , he/she still has time to learn and grow but i think you haven't after all this time alas 🥀
recently I was upgrading a legacy java codebase and the amount of slop there was actually insane
it's over bros, AI is much better at coding than humans, stop believing anyone who says otherwise, it's 2026
