Why do databases store data in B+ trees?
Вставка
- Опубліковано 5 жов 2024
- System Design for SDE-2 and above: arpitbhayani.m...
System Design for Beginners: arpitbhayani.m...
Redis Internals: arpitbhayani.m...
Build Your Own Redis / DNS / BitTorrent / SQLite - with CodeCrafters.
Sign up and get 40% off - app.codecrafte...
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.m...
Bookshelf: arpitbhayani.m...
Papershelf: arpitbhayani.m...
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...
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. - Наука та технологія
was exploring mongodb internals and needed to understand why we use B+ trees.
awesome explanation ,crisp and to the point !
Very well explained Arpit. Looking forward to more such videos.
UA-cam 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
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.
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!
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.
Now I am slightly confused with indexing and storing rows as B+ trees 😂
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.
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) ?
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?
Good enough for interview preparations...thanks a lot
its very very deeply explained just like a good book author explains it .... highly Appreciate your efforts
So wonderful, very digestible content
These videos are extremely helpful. Makes me curious to explore more on my own. Thanks!
Amazing. Thats precisely the attitude I wanted to percolate. Thank you for resonating 👍
loved your easy to understand explanation, thanks a lot for the new perspective on this!
Amazing, I really appreciate your effort, the way you teach us, is great Thanks man.
A video suggestion. Difference between MySQL and Postgres. How they index differently and how that affects read, insert, update and delete query.
Simple and clear !!!!. Looking for more of these kinds...
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.
this is a trade off made in order to achieve better performance and efficient range searches
Beautifully explained...hats off to you!
Very insightful video. Could you please make a video explaining the internal functionality of graph databases..??
No need to do linear scan in sequential sorted rows. You can do binary search.
Awesome explanation! Thank you
Somehow, I am naturally very curious about how various kinds of databases/use cases store data at the lowest level i.e. disk level/SSD level.
How various social websites/apps model and store list of followers/followees of a user? because after each friend request, this entire list changes.
Sources of my confusion:
(1) If we store this entire data in one field, that field will keep changing.Do relational databases even provide such variable length field(I know varchar,string etc, but that doesnt seem right data structure for this, to begin with)
(2) instagram I read some time back uses postgres. How does postgres model such variable length field?
(3) is there any social platform which uses nosql just to meet this criteria. That would sound funny though.
(4) I am inclined to split the discussion into 2 parts :
(a) When this field will be updated in-place like regular B+ tree, then a separate block might be needed to be allocated everytime, the new field size causes the block to expand.
(b) if we use a database which uses sstable/memtable, and argue that anyway the field will be appended after every change, still we will cause intentional appending of this entire field(list of complete followers/followees after each new friend request) very frequently.
(5) Some reference from real world use cases of how actual systems implement this in practice, will be very useful. Given your vast readings, I am sure you will be able to add value to it.
(6) graph databases might be an option, but in real practice, are there social apps which use graph database for this use case?
Thanks a lot!,
If you find the doubt generic enough, you might make content for general consumption.
Jagrati
Hi @Arpit just asking out of curiosity can one see the internal implementation of storage of data in a database?
Thank you sir!!
Great content as always.
Awesome explaination
Great explanation Arpit👏
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
exactly tree will store the pointer to the data not the entire data
For this very reason, indexes, such as B+ Trees, perform poorly in write-heavy systems. Indexes are primarily designed to enhance lookup speeds (reads), not writes. This inefficiency arises because each insert, update, or delete operation may require rearranging the tree to maintain its balanced nature. This rearrangement often involves splitting or merging nodes and updating pointers, which can be time-consuming. It is crucial to carefully consider the required access patterns and create only the necessary minimum number of indexes on a table.
Awesome explanation, loved it
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
Can you share the Notes
unable to download them from your website
I wanna learn more about this, any good references?
Hey Arpit - Help me to understand the case, when DB update and insert operation cannot take place in the given block due to limited space in the block then how DB manages insert and updates in such scenarios ?
beautiful! This is so cool
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?
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.
@@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?
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?
It's not ordered, so the search has to be linear. As the nodes can be scattered anywhere.. like.. imagine linked lists
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?
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.
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?
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.
Why AVL trees are not used as for them also time complexity is log(n)?
Thank you
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?
Thanks
awesome.
do the leaf nodes contain data or pointers to actual data ?
I read in other places - its pointers
No. It is data. Read about the clustered index and how tables store data in the clustered index.
What if we want to search a name? How B+ tree will work?
same way, strings are comparable.
So tthey will have different indexing? And we would have another B+ tree@@AsliEngineering
Sir, What will happen we use B trees instead of B+ trees.
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.
Kya quality he bhaiya videos ki
At ua-cam.com/video/09E-tVAUqQw/v-deo.html -> 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?
with all due respect, you should choose better topics for the videos
Suggest a few then.