B-tree vs B+ tree in Database Systems

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

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

50% 1

In this episode of the backend engineering show I'll discuss the difference between b-tree and b+tree why they were invented, what problems do they solve, and the advantages and disadvantages of both. I'll also discuss the limitation of implementing b-tree over b+tree and how Discord ran into a memory limitation using b-tree Mongo.
Check out my udemy Introduction to Database Engineering course
husseinnasser.com/courses
Learn the fundamentals of database systems to understand and build performant backend apps
Chapters
0:00 Data structure and algorithms
1:30 Working with large datasets
6:00 Binary Tree
8:30 B-tree
19:30 B+ tree
22:00 B-tree vs B+ tree benefits
25:00 MongoDB Btree Indexes Trouble
30:00 Summary
working with a billion-row table (Members only)
• Best Practices Working...
indexing video
• Database Indexing Expl...
Discord moving from MongoDB to Cassandra
• Why Discord Moved from...
/ discord
MongoDB Indexes
docs.mongodb.com/manual/indexes/
Postgres Indexes
www.postgresql.org/docs/13/bt...
b-tree code from @usfcalifornia
www.cs.usfca.edu/~galles/visu...
b+tree
www.cs.usfca.edu/~galles/visu...
Support my work on PayPal
bit.ly/33ENps4
Become a Member on RU-vid
/ @hnasr
🧑‍🏫 Courses I Teach
husseinnasser.com/courses
🏭 Backend Engineering Videos in Order
backend.husseinnasser.com
💾 Database Engineering Videos
• Database Engineering
🎙️Listen to the Backend Engineering Podcast
husseinnasser.com/podcast
Gears and tools used on the Channel (affiliates)
🖼️ Slides and Thumbnail Design
Canva
partner.canva.com/c/2766475/6...
🎙️ Mic Gear
Shure SM7B Cardioid Dynamic Microphone
amzn.to/3o1NiBi
Cloudlifter
amzn.to/2RAeyLo
XLR cables
amzn.to/3tvMJRu
Focusrite Audio Interface
amzn.to/3f2vjGY
📷 Camera Gear
Canon M50 Mark II
amzn.to/3o2ed0c
Micro HDMI to HDMI
amzn.to/3uwCxK3
Video capture card
amzn.to/3f34pyD
AC Wall for constant power
amzn.to/3eueoxP
Stay Awesome,
Hussein

Наука

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

31 май 2024

Ссылка:

Скачать:

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

Добавить в:

Мой плейлист

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

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

@hnasr 2 года назад

Check out my udemy Introduction to Database Engineering course db3 database.husseinnasser.com Learn the fundamentals of database systems to understand and build performant backend apps

@neiliwael5536 2 года назад

hey hussein , can u tell me how to join the channel to get access to all the content ? :D

@jetzemeilink Год назад

Man, hussein the first 40 seconds are so on point. If you really want to learn something new out of curiosity or to solve a problem you're currently facing. You will be driven to understand the concept and way more likely to retain the information and when to apply it.

@zklevsha 2 года назад

A+ explanation of B+ tree topic Thank you Hussein

@gaofan2856 Год назад

Abdul Bari, Tushar Roy, Hussein Nasser, Alex Xu, Andrew Ng - those people are simply legends in explaining convoluted concepts in simple language.

@gelidvoum1207 2 года назад

MongoDB tends to have index bloat problems, even with only 2-3 indexes they take up 10%-20% of the original dataset size.

@Miggleness 2 года назад

Database Internals is an excellent book that goes through various algorithm and implementations for storing data.

@wassimboussebha2561 2 года назад

Please I am beginner , I have only a basic knowledge in data structures like trees etc.., I want to learn more about databases, do you suggest any good book before reading databases internals book?

@Miggleness 2 года назад

@@wassimboussebha2561 you can just right into Database Internals.

@tyrodev5281 2 года назад

I'd love if you could find the time to talk about different data structures, their usage, why they were created in the first place... the in-depth stuff because I haven't seen anyone analyze things as critically as you. Thanks!!

@santoshbhatnagar2155 8 месяцев назад

Really loved how you correlate things. The mongodb example was very eye opening

@jujijiju6929 2 года назад

Is that a sword in the background? Damn... That looks lifesize lmao

@endchoice1073 2 года назад

i agree with exactly with you on data structers and algorithms learning them for interviews is a burden if you understand how data is stored and memory things it is really good

@vaideshshankar9899 2 года назад

A million dollar advice given by him

@miguelgarciadasilva 2 года назад

Great content guy, thanks for sharing. Would be great another video discusing LSM Tree

@germanreynaga7256 2 года назад

I'm looking all your videos, great job man and thanks for all the information again

@0xc0ffee_ Год назад

MongoDB uses B+ by WiredTiger default storage engine.

@SheikhYourbutty 2 года назад

Hussein, thank you very much for your time for creating such educative content for advanced topics. I would like to suggest additional topics to cover regarding b-trees. 1) What regulates b-tree depth? 2) And how b-tree behave in case of composite index?

@hnasr 2 года назад

Great suggestion!

@ravisemwal5363 2 года назад

16:49, that's what she said. Informative video!

@tusharrao6316 Год назад

People like you motivate me to study hard and develop some skills to be proud of.

@chandeeparora.7165 2 года назад

Thanks for this Hussein!

@ayenewyihune 7 месяцев назад

Very clear and interesting, thanks

@SunnyGuptaTech 2 года назад

Really Awesome Nasser

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

B stands for "ubiquitous". Reference: Douglas Comer: " The ubiquitous b-tree", ACM Computing surveys, volume 11, number 2, pages 121-137 June 1979 8:36

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

thank you so much very valuable information

@Telenisme 2 года назад

You are awesome man.. thank you so much for this incredible channel.

@pjcollazo8318 2 года назад

1:45 Impeccable Japanese

@AhmedMohamed-zr9kw 2 года назад

you're great Hussien

@Miggleness 2 года назад

B-trees is a generic term and doesn't imply that content is stored on the middle nodes and not the leaf node. MySQLs InnoDB does use B+tree but refers to it as B-tree. WiredTiger is likely similar

@animatedzombie64 2 года назад

thanks hussein

@nitindevatraj 2 года назад

Found your channel through codedamn , I like the backend focused content, any suggestions, resources for learning backend with node, there is lot of content on front end but not much content with depth on backend

@rocklife1802 2 года назад

Really helpful video

@krozaine 2 года назад

Does a B-Tree with value as the pointer to the actual data tuple (and not the whole value) count as B-Tree? It should be small in size but work well enough. The differentiating factor in B+ Trees (IMO) is the sequential pointer to the next node and storage of data in the leaves

@Varun2799 2 года назад

MongoDB does not infact use B-Trees. They use B+ Trees. I dont know why the docs say it is B tree but if you dig deep enough and read the implementation then you'll find that it is in fact a B+ tree lol. I spent the last 2hours going down this rabbit hole because I am preparing a presentation on database storage systems. But yeah. Hope people reading this in the future will find it helpful :)

@Varun2799 2 года назад

And as to why Discord went with Cassandra, My guess is because Cassandra uses LSM trees as their data structure for storage which is a whole different thing from B trees

@dimitriborgers9800 Месяц назад

At 15:37, you mention that in Postgres, the index node is the actual page that holds thousands of elements. Is this mentioned in their docs? I've only heard people say it holds the record pointer, not the actual pages itself

@kenvat6344 2 года назад

here after completing the DBE course in udemy!

@nitindevatraj 2 года назад

How was it , any suggestions for learning backend with node

@tjalferes 2 года назад

Thank you!

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

Thank you.

@fadhilimamkurnia4566 2 года назад

I think mongodb can't easily use B+ tree since the key is relatively unpredictable, compared to postgresdb who usually has ordered primary index (1,2,3,4,....). The insert operation on postgresdb (or other relational db) usually just need to increase the primary index hence we just need to append it in the memory, but when its come to mongodb we can have 1,2,8,9 as our keys then inserting 5 will require us to move many nodes in the tree, because we are inserting in the middle of our "array". Cmiiw

@lakshminarasimmanv Год назад

b+ tree is used in Kubernetes(etcd database)

@danielskrypnik5181 2 года назад

Hey, Hussein, could you please explain one thing? Why b+ three is more efficient for RAM? I guess we don’t store data in leaf nodes in RAM. We store only intermediary nodes, isn’t? Didn’t get your explanation of problem with Discord’s problem of Mongo db.

@hnasr 2 года назад

B-trees store keys and values in all nodes, which means node take more space. B+trees only store values in leave nodes while it only stores keys in intermediate nodes. This means that nodes with only keys are much more smaller than leave nodes. Which means you can easily fit the intermediate nodes in memory easier while keeping the leave nodes in disk, this makes traversal much more efficient. A luxury that b-tree does have.

@Keerthiprincess2061 Год назад

If we store indexes in RAM,isn't that volatile?

@NotYourAveragePirate Год назад

@@Keerthiprincess2061 You only store a copy of the index file in RAM. The entire index file + content will be on the disk

@engineeranonymous 2 года назад

Since MongoDB 3.2 Mongodb uses Wiredtiger as default storage engine which can use LSM Tree.

@hnasr 2 года назад

Thank you! I didn’t know that. More info here source.wiredtiger.com/mongodb-3.4/lsm.html

@utsabbanerjee9672 2 года назад

I have a silly question Hussein. I understood that the InnoDB secondary indexes don't store the tuple ID on the heap but just stores the associated PK index values. The question is, why doesn't it simply store the disk address of the PK index node (i mean the address of the node containing the associated PK values in the btree structure created for the PK index) and from there just fetch the on-disk tuple ID? This way the choice of the PK won't bump up the memory requirement for secondary indexes, since the data type of disk address is fixed length. Please help me clear this doubt.

@hnasr 2 года назад

This is a basic tradeoff that DBMS systems do. Postgres does as you describe, it stores the direct pointer to the tuple in all indexes, while InnoDB stores the primary key as a pointer in all secondary indexes. There are pros and cons in both approaches for different use cases. While true in MySQL based InnoDB, you have to do to index searches to get to the row, (one in the secondary to find the primary key and another b-tree search on the primary to find the row pointer), the write amplification in InnoDB is significant. Compare this to postgres where when you do a secondary index search you immediately jump to the row tuple, but updating any indexed column in the row must update ALL indexes to point to the new row id. I talked about this in detail in my write-amplification private discord (members only) which you have access to as a member, check it out ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-jsWwFL_iqVM.html

@utsabbanerjee9672 2 года назад

@@hnasr The link you shared and a few other docs, helped me get a better understanding. Thanks.

@stormShadow64 2 года назад

Awesome wideo

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

Maybe mongodb uses B-Tree because of the nature of the keys UUID instead of sequential? Rebalancing trees will cost more with UUID? Just asking here, not making any affirmation.

@saralightbourne Год назад

1:46 my friend, did you really say "thank you ソウーマッチョーですか"😁

@abdulmlikba9452 2 года назад

what is the difference between b+tree and b*(star)-tree

@rohitmundada703 2 года назад

Being a noob at databases here, I just had a question: When the index reaches the size of RAM, who decides to put the other part of index into disk? And how do they decide which part of index should go to disk?

@supersu6138 2 года назад

I think memory swapping happens once you are out of memory and OS is responsible for resource management

@Music_song_Musurmonov_Mehroj 2 года назад

Hussein, can you recommend some RU-vid channels about database engineering?

@nurmukhammad_30k Год назад

ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-aZjYr87r1b8.html

@bijayjungkarki7369 2 года назад

👌

@abdulmoizsheikh8031 2 года назад

Quick question. Why cant you load parts of Btree in memory, but load parts of a b+tree in memory?

@hnasr 2 года назад

You can load both data structures in memory. Its just you can load more of the b+tree internal nodes compared to b-tree. Just because of the sheer size

@abdulmoizsheikh8031 2 года назад

@@hnasr ah right. Thanks!

@pushpak6523 2 года назад

is that a samurai? behind

@sumedhasaxena6702 2 года назад

For a second I got confused on why is CarryMinati talking about B+ trees lol

@gunnvant 2 года назад

learn by doing

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

Why is there a katana on the shelf?

@gunnvant 2 года назад

Learn by doing

@gunnvant 2 года назад

Posted from terminal

@numtostr 2 года назад

If MongoDB using Btree and PgSQL using B+tree. So, this means pgsql reads are faster than mongodb?

@hnasr 2 года назад

Depends on the size of the index and the nature of queries. if the index is small enough to fit in memory it’s similar performance and its a single lookup than btree/b+tree are similar in performance. If the index is large that it doesn’t fit in memory and queries are range based (eg where date range ) b+tree (postgres) wins for sure. discord ran into severe performance issues with mongo when their btree index couldn’t fit in memory, and switched to Cassandra instead which uses an LSM tree instead.

@lionkiddo 2 года назад

When you are so early that there's no pinned comment.

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

Wolverine

@geghamayvazyan5637 2 года назад

why DBs are not using hash tables?

@MrYokyScape 2 года назад

Doesn't scale well when you have millions or billions of rows. Also hard for range queries.

@IBITZEE 2 года назад

Huummm... the B+Tree looks o me like a "Linked-List" where you mantain some metadata (the paths to the nodes) nevertheless it seems a good strategy for +1M leafs... ;-)

@privacyvalued4134 2 года назад

This video was rather useless. The main problems are that it skips from B-trees straight into a complete B+ tree (too much edited out) and also doesn't show how the data would be stored on disk. Hand-waving over the two critical parts means anyone wanting details will just waste their time.

@nurmukhammad_30k Год назад

ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-aZjYr87r1b8.html Watch the video of this guy. Very well explained how b-tree and b+tree work.