Why do databases store data in B+ trees?
Oct 4, 2026
Why do databases store data in B+ trees?
so recently i was learning about B+ trees and one question that actually made the whole thing much more interesting for me was , why do databases even need B+ trees in the first place ?
like we already have filesystems , we can create a file on disk , write data into it and read that data whenever we need it , so why don't databases just keep the table data in a normal file and somehow read and update that file whenever a query comes in ?
and the answer is actually not about the database wanting some fancy data structure , it is mostly about one thing , Disk I/O
because once our data becomes large enough , the problem is not really how fast our CPU can compare two numbers , the problem becomes how many times we have to go to the disk to get the data we need.
let's start with a simple file
suppose we have a users table
id name
1 John
2 Doe
3 Shahbaz
4 Lucifer
5 Andrej
...
and imagine that we simply store all these rows one after another inside a file on disk
[1, John]
[2, Doe]
[3, Shahbaz]
[4, Lucifer]
[5, Andrej]
...
this looks completely fine
and if i ask you
give me the user whose id is 4
you can simply start reading the file from the beginning , check each row and eventually find id = 4
but now imagine that instead of 5 rows , we have 500 million rows.
now finding one particular row can potentially mean scanning a huge portion of the file.
and the problem becomes even more obvious when we try to insert something in the middle.
suppose our file looks like this
1
2
3
4
5
6
and now i want to insert 3.5
if this is actually a sequentially organized file , we need to make room for the new data
1
2
3
3.5
4
5
6
which means that the data after that position may need to move.
the same kind of problem appears when we delete or update data. and particularly for update we must make sure that new data row bytes must be same to the one we are updating , because otherwise it will just overwrite the next row.
so a simple file is not really a good structure for a database that is constantly doing insert , update , delete , search and range operations
Okay , then let's keep the file sorted
now we might think , why don't we just keep the file sorted by id ?
then finding a user becomes easier because we know where the data should approximately exist.
but now we have another problem. what happens when i insert a new row ?
suppose the file contains
1
2
3
4
5
and i want to insert 2.5
we still need to maintain the sorted order.
and if the file is huge , maintaining this order can become expensive , because first we have to copy the entire data after that row , where we are writing the data , to a seperate file and after writing our new row , just copy back all data after this new row from that file.
so we have a tradeoff
if we don't keep the data organized , searching becomes expensive.
if we keep the entire file sorted , insertion and deletion become expensive.
we need some structure which can give us both reasonably efficient searching and modification.
and this is where B+ trees come into the picture.
so what exactly is a B+ tree doing here ?
instead of thinking of our entire table as one giant file , we divide the data into smaller blocks/pages.
for example , conceptually imagine something like this
[ 50 ]
/ \
< 50 >= 50
/ \
[10 20 30] [50 60 70]
the important thing here is that these nodes are not just random objects floating somewhere in memory.
they are designed around how data is actually read from disk.
a database doesn't usually read one byte from the disk every time it needs something.
it reads a page/block of data , which is approx 4 Kb.
so instead of asking the disk
give me this one row
we try to make one disk read useful enough that it gives us a bunch of relevant rows together.
for example , if a page is 4KB and our rows are around 40 bytes , then one page can contain roughly 100 rows.
so one disk read can bring around 100 rows into memory.
and this is a very important idea behind B+ trees.
the database is basically trying to reduce disk reads
imagine we have 1 million rows.
if our structure forces us to randomly read hundreds or thousands of different places on disk just to find one row , that is going to hurt.
instead , we want something like
root
|
internal
|
leaf
|
actual data
and each level helps us decide where to go next.
so when i search for id = 734
the database doesn't start from row 1 and keep checking every row.
it starts from the root , looks at the keys , decides which child contains 734 , goes there , does the same thing again and eventually reaches the leaf page containing the row.
something like
[500]
/ \
< 500 >= 500
|
[700 900]
|
[734 ...]
the actual structure is obviously more complicated than this , but the idea is simple
each level helps us eliminate a huge amount of data that we don't need to look at.
and because B+ trees have a very high number of children per node , not two like we have in simple binary trees , the tree doesn't become very deep even when we have millions or billions of records.
which means fewer levels
which means fewer disk reads.
but why B+ tree and not just a normal binary search tree ?
this is another interesting part.
in a binary search tree , each node basically has two children.
so if we have a lot of data , the tree can become quite deep.
and remember what we care about here , disk I/O
if going from one node to another potentially means another disk page read , having a very deep tree is not ideal.
B+ trees solve this by having a very high fanout.
a node can contain many keys and many pointers to other nodes.
so instead of
50
/ \
25 75
/ \ / \
...
we can have something conceptually more like
[20 | 40 | 60 | 80]
/ | | | \
... ... ... ... ...
one node can point to a large number of children.
so the tree becomes very wide and very shallow.
and that is exactly what we want when our expensive operation is reading from disk.
and then there are the leaf nodes
one of the things i found interesting about B+ trees is that the internal nodes are mainly there to help us navigate , means they contain mostly the indexes to route to the correct node.
the actual rows are stored at the leaf level and all the leaf nodes are connected as a linked list.
something like
[50 | 100]
/ | \
/ | \
[10 20 30] [50 70 80] [100 120 150]
and the leaf nodes are linked with each other
[10 20 30] -> [50 70 80] -> [100 120 150] -> ...
this becomes really useful for range queries.
suppose i ask
SELECT * FROM users
WHERE id >= 100 AND id <= 600;
we don't need to search the whole database again and again.
we first navigate through the tree to find where 100 exists.
once we reach that leaf node , we can simply move through the linked leaf nodes until we reach 600.
so the B+ tree gives us two useful things , fast point lookup and efficient range traversal , which is exactly what databases need very often.
what happens when we insert ?
let say i want to insert a new user with id = 735
the database first navigates through the tree to find the leaf page where 735 belongs.
then that page is brought into memory.
the row is inserted there.
but what if that page is already full ?
then the B+ tree can split the node.
something like
before
[700 710 720 730 740 750]
becomes
[700 710 720] -> [730 740 750]
and the parent is updated so that it knows about this new separation.
this is why B+ trees are not just a static sorted structure.
they can continuously change as data is inserted and deleted while still keeping the overall organization.
and this is where memory comes in
there is another important thing to understand here.
the B+ tree is a logical data structure , but the database is ultimately storing it on disk.
when we want to modify a page , the database generally brings that page or block into memory , modifies it there and eventually writes the modified page back to disk.
so conceptually
disk
|
| read page
v
memory
|
| modify
v
memory
|
| flush/write
v
disk
this is also why the concept of pages is so important when learning database internals.
the bigger picture
when you connect B+ trees with the actual problem , it starts making much more sense.
the database has potentially billions of rows.
those rows ultimately have to live on persistent storage.
persistent storage is much slower than memory , so we want to minimize expensive disk I/O.
therefore we need a structure that keeps data organized , allows fast lookup , supports insert/update/delete , supports range queries , keeps the number of disk reads low , and can grow without becoming ridiculously deep.
and B+ trees fit this problem really well.