Why do databases store data in B+ trees?

Подписаться 103 тыс.

Просмотров 27 тыс.

50% 1

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.

Наука

Опубликовано:

18 мар 2023

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 54

@jatinrawat1047 5 месяцев назад

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

@arungowda Год назад

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

@RaghvendraKumar-rm7tv 9 месяцев назад

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.

@user-lg4tw8hu2x 7 месяцев назад

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!

@amitrastogi1405 4 месяца назад

Beautifully explained...hats off to you!

@alejandrogarcia3004 5 месяцев назад

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

@manukolathur4029 11 месяцев назад

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

@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.

@sahazeerks2363 Год назад

Awesome explanation, loved it

@namangarg3933 Год назад

Very well explained Arpit. Looking forward to more such videos. RU-vid 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.

@sachinjindal4921 Год назад

Great explanation Arpit👏

@aneksingh4496 9 месяцев назад

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

@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?

@cooldudecs 10 месяцев назад

beautiful! This is so cool

@vinitsunita 6 месяцев назад

Awesome explaination

@pankajvermacr7 4 месяца назад

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

@chandrachurmukherjeejucse5816 2 месяца назад

Great content as always.

@mohdhaseeb9818 Год назад

Thank you sir!!

@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?

@santoshbhatnagar2155 Год назад

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

@rahulsarkar4206 Год назад

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

@itsthesecondchannel Год назад

Thank you

@butterhalves4262 Год назад

awesome.

@jagannathprasaddas1636 11 месяцев назад

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?

@vishnuaggarwal1132 Год назад

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

@siddhantchavan1370 3 месяца назад

I wanna learn more about this, any good references?

@rahulyadav8159 10 месяцев назад

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 8 месяцев назад

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

@gauravsharma3142 3 месяца назад

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 3 месяца назад

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 3 месяца назад

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.

@binitrajshah9354 5 месяцев назад

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.

@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?

@darshanv1748 9 месяцев назад

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

@learnwithme7750 9 месяцев назад

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 5 месяцев назад

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

@rahulmenon5149 2 месяца назад

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

@AsliEngineering 2 месяца назад

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.

@ankuragarwal9712 Год назад

At ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-09E-tVAUqQw.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?