Why do databases store data in B+ trees?

System Design for SDE-2 and above: arpitbhayani.me/masterclass
System Design for Beginners: arpitbhayani.me/sys-design
Redis Internals: arpitbhayani.me/redis
Build Your Own Redis / DNS / BitTorrent / SQLite - with CodeCrafters.
Sign up and get 40% off - app.codecrafters.io/join?via=...
In the video, I discussed the evolution of storage from naive implementations to optimized B plus trees in databases. I explained the need for using B plus trees, how table data is stored in them, and how the tree is serialized and stored on disk. I also introduced a system design course I offer. I highlighted the limitations of naive data storage methods like linear scans and explained how B plus trees solve efficiency issues in insertions, updates, finds, deletes, and range queries by organizing data into nodes on disk.
Recommended videos and playlists
If you liked this video, you will find the following videos and playlists helpful
System Design: • PostgreSQL connection ...
Designing Microservices: • Advantages of adopting...
Database Engineering: • How nested loop, hash,...
Concurrency In-depth: • How to write efficient...
Research paper dissections: • The Google File System...
Outage Dissections: • Dissecting GitHub Outa...
Hash Table Internals: • Internal Structure of ...
Bittorrent Internals: • Introduction to BitTor...
Things you will find amusing
Knowledge Base: arpitbhayani.me/knowledge-base
Bookshelf: arpitbhayani.me/bookshelf
Papershelf: arpitbhayani.me/papershelf
Other socials
I keep writing and sharing my practical experience and learnings every day, so if you resonate then follow along. I keep it no fluff.
LinkedIn: / arpitbhayani
Twitter: / arpit_bhayani
Weekly Newsletter: arpit.substack.com
Thank you for watching and supporting! it means a ton.
I am on a mission to bring out the best engineering stories from around the world and make you all fall in
love with engineering. If you resonate with this then follow along, I always keep it no-fluff.

[@jatinrawat1047]

was exploring mongodb internals and needed to understand why we use B+ trees. awesome explanation ,crisp and to the point !

[@user-lg4tw8hu2x]

Absolutely clear your explanation. Very simple approach making all B-tree propose understandable. I was reading a advanced book where I was getting lack of information and motivation about how to range from a leaf like containing 101 to a leaf containing 601. Your example is very realistic providing easier understanding. Congrats, buddy!

[@nishankgoyal8323]

Nice video, reminds me of how documents are stored in shelfs at my home. Containers saying what those documents are for say ITR, followed by files mentioning year blocks say 2010-2020, individual files and then individual documents.

[@arungowda]

Now I am slightly confused with indexing and storing rows as B+ trees 😂

[@RaghvendraKumar-rm7tv]

B+ Tree data structure is used to store both the row & index. Since every table has only one clustered index which determines how data is stored physically on the disk, in clustered index B+ tree will store the row data also. But in a non-clustered index, B+ tree will not have the actual row data but a pointer connecting it to the clustered index which has the actual data.

[@amitrastogi1405]

Beautifully explained...hats off to you!

[@alejandrogarcia3004]

loved your easy to understand explanation, thanks a lot for the new perspective on this!

[@manukolathur4029]

Simple and clear !!!!. Looking for more of these kinds...

[@namangarg3933]

Very well explained Arpit. Looking forward to more such videos. KZbin is full of content and newbie creators. But, knowing the amount of research you put in your content coupled with your rich hands on experience, adds a tremendous confidence in whatever we learn from your channel. Thanks

[@AsliEngineering]

Thanks for resonating 🙌 I ensure the correctness and in-depth understanding before making the video on it. Happy that you saw the efforts I have put in. Thanks again 🙌 will continue putting out videos on things that matter.

[@swati12091993]

These videos are extremely helpful. Makes me curious to explore more on my own. Thanks!

[@AsliEngineering]

Amazing. Thats precisely the attitude I wanted to percolate. Thank you for resonating 👍

[@AbhijeetBhattacharya-uh7dy]

Awesome explanation! Thank you

[@sahazeerks2363]

Awesome explanation, loved it

[@aneksingh4496]

its very very deeply explained just like a good book author explains it .... highly Appreciate your efforts

[@sachinjindal4921]

Great explanation Arpit👏

[@cooldudecs]

beautiful! This is so cool

[@chandrachurmukherjeejucse5816]

Great content as always.

[@pankajvermacr7]

Amazing, I really appreciate your effort, the way you teach us, is great Thanks man.

[@vinitsunita]

Awesome explaination

[@mohdhaseeb9818]

Thank you sir!!

[@rahulsarkar4206]

A video suggestion. Difference between MySQL and Postgres. How they index differently and how that affects read, insert, update and delete query.

[@prashantshubham]

Great detailed video, thanks Arpit. Had one doubt if you can explain: At one point we're saying when we're finding one by Id = 3 it does 3 disk reads from root of the tree to leaf node, but isn't there caching involved and indexes are cached in memory so that the disk reads are avoided also is the caching involved only after 1st call is done pertaining to a row/table or are the indexes cached as soon as DB is ready to take reads/writes?

[@santoshbhatnagar2155]

Hi @Arpit just asking out of curiosity can one see the internal implementation of storage of data in a database?

[@itsthesecondchannel]

Thank you

[@butterhalves4262]

awesome.

[@smritimittal4128]

For the first approach (discussed before B+ tree) - - All rows stored in a file - Can we not have 4KB (=disk block) sections each in that file too - If there were 1000 rows, then, each block is 100 rows now - so, to go through all of 1000 rows, I do 10 disk reads - hence, findOne is not O(n) but, O(no. of total disk blocks) ? - Also, when inserting - - Again, can we not put these 10 disk reads in RAM - re-arrange and flush all back to the file, the disk (similar to what we did for B+ tree) ?

[@AsliEngineering]

1. that is exactly how disk io happens but how will you do random reads 2. Today you are talking about 10, but you will not have just 40kb of data, it will go in GBs if not TBs. Then how will you do it?

[@vishnuaggarwal1132]

Can you share the Notes unable to download them from your website

[@jagannathprasaddas1636]

Does a DBMS behave more intelligent than an os by bypassing the filesystem I/O? If yes what is the system call for reading writing to disk block from user space?

[@rahulyadav8159]

One question here Arpit Leaf nodes of the tree contains the actural rows of table. So leafs nodes are efficiently utilizing the disk block size. But the internal nodes of the tree contains the child and their node information. So it seems internal nodes of the tree is not fully uitlizing the disk block size. So overall if we have more interanl nodes then we are un nessessarly wasting the disk block. Please let me know if I am thinking in right direction.

[@Goku-xm1gq]

this is a trade off made in order to achieve better performance and efficient range searches

[@siddhantchavan1370]

I wanna learn more about this, any good references?

[@samarth319]

Can Clustered and Non-clustered index be related to B+ tree store of the database? Like for instance if we create a primary key then a clustered index is created on that, and inside the index, pointers to the block stored. So is that pointer pointing to the leaf node of the B+ tree?

[@AsliEngineering]

Indexes are implemented as B+ trees. Indexes are implicit tables with 2 columns (indexed value and row id). Storage is very similar to how a table is stored.

[@arungowda]

@@AsliEngineering so the numbers 100,200..500 you talked about in the video, are they row Ids? when we index on a column, does it store a mapping of that column to rowId in B+ trees? In which case it has to do the B+ tree search? Or is the index a mapping of column to physical address on the disk?

[@learnwithme7750]

Hey Arpit Really good content..but one doubt in findById when we reach the leaf node of B+ tree then to search a particular should we need to traverse one by one or we can use binary search as well to reach a particular node?

[@DurgeshYadav-bc5nm]

It's not ordered, so the search has to be linear. As the nodes can be scattered anywhere.. like.. imagine linked lists

[@darshanv1748]

I have a doubt , if i insert another row in row 195 then all the next rows should also move forward (you have to do the same in B Trees also right ?) , i don't get how btrees solve this problem

[@snehagupta1044]

exactly tree will store the pointer to the data not the entire data

[@binitrajshah9354]

In case of update still we can face same issue of overflow which implies time complexity to O(n). How B+ trees handle this situation? I mean new update might have larger value and my leaf node is already fully occupied.

[@gauravsharma3142]

If a table has too many columns such as the data in each row exceeds 4kb of block size Will that block size will be of bigger value Or the databse will partition the row on basis of columns

[@sanketh768]

Sir , I'm not able to imagine things when you say b tree is serialised and stored in the disk. Could someone please help me understand this better and visualize this?

[@AsliEngineering]

each node is B+ tree is stored in one disk block. naive way to image each node in b+ tree as one separate file on the disk.

[@rahulmenon5149]

do the leaf nodes contain data or pointers to actual data ? I read in other places - its pointers

[@AsliEngineering]

No. It is data. Read about the clustered index and how tables store data in the clustered index.

[@BugMug09]

Kya quality he bhaiya videos ki

[@aayush7099]

Sir, What will happen we use B trees instead of B+ trees.

[@AsliEngineering]

intermediate nodes bloat up (given data now resides there as well). This means it will take us to read more data from disk to reach rows present in the leaf. Performance will degrade.

[@saifulhasan2532]

What if we want to search a name? How B+ tree will work?

[@AsliEngineering]

same way, strings are comparable.

[@saifulhasan2532]

So tthey will have different indexing? And we would have another B+ tree@@AsliEngineering

[@ankuragarwal9712]

At kzbin.info/www/bejne/ZmqoXqeMdrqkh9k -> are we assuming always that all B+ tree nodes will be part of one file therefore concluding that B+ tree leaf nodes contain offset of the next leaf node?

[@rjarora]

with all due respect, you should choose better topics for the videos

[@AsliEngineering]

Suggest a few then.