B-tree vs B+ tree in Database Systems

[@hnasr]

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]

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

[@gaofan2856]

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

[@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]

A+ explanation of B+ tree topic Thank you Hussein

[@Miggleness]

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

[@wassimboussebha2561]

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]

@@wassimboussebha2561 you can just right into Database Internals.

[@tyrodev5281]

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!!

[@endchoice1073]

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]

A million dollar advice given by him

[@gelidvoum1207]

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

[@tusharrao6316]

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

[@santoshbhatnagar2155]

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

[@0xc0ffee_]

MongoDB uses B+ by WiredTiger default storage engine.

[@ravisemwal5363]

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

[@kenvat6344]

here after completing the DBE course in udemy!

[@nitindevatraj]

How was it , any suggestions for learning backend with node

[@jujijiju6929]

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

[@surters]

Look like a Katana.

[@Varun2799]

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]

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

[@Miggleness]

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

[@ibrahimbayramov3510]

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

[@miguelgarciadasilva]

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

[@pjcollazo8318]

1:45 Impeccable Japanese

[@animatedzombie64]

thanks hussein

[@engineeranonymous]

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

[@hnasr]

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

[@lakshminarasimmanv]

b+ tree is used in Kubernetes(etcd database)

[@ayenewyihune]

Very clear and interesting, thanks

[@germanreynaga7256]

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

[@AhmedMohamed-zr9kw]

you're great Hussien

[@saralightbourne]

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

[@amalalsaeh4894]

thank you so much very valuable information

[@moazmohamedhassanbayoumi4722]

Thank you.

[@jhguygih]

Great content. I have one question, where can I find material explaining the pros and cons of each tree? You mentioned range querie on B tree is not as efficient. Why is that? Why we need a find for every node and not collect results once we find the end of the range

[@SunnyGuptaTech]

Really Awesome Nasser

[@chandeeparora.7165]

Thanks for this Hussein!

[@Telenisme]

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

[@rocklife1802]

Really helpful video

[@fadhilimamkurnia4566]

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

[@danielskrypnik5181]

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]

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

[@digvijaysingh6882]

​@@hnasr but isn't the data you're mentioning here is just references to some tuple... Is it of so large size that it could severely affect performance?

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

[@surters]

"My right, don't know if it is your right!" 😁

[@tjalferes]

Thank you!

[@rohitmundada703]

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]

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

[@stormShadow64]

Awesome wideo

[@gunnvant]

learn by doing

[@krozaine]

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

[@utsabbanerjee9672]

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]

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 kzbin.info/www/bejne/oKS6qHmClM6kjK8

[@utsabbanerjee9672]

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

[@nitindevatraj]

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

[@henrmota]

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.

[@pushpak6523]

is that a samurai? behind

[@Music_song_Musurmonov_Mehroj]

Hussein, can you recommend some KZbin channels about database engineering?

[@nurmukhammad_30k]

kzbin.info/www/bejne/l4vNiqVubNdkmJo

[@gunnvant]

Posted from terminal

[@abdulmoizsheikh8031]

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

[@hnasr]

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]

@@hnasr ah right. Thanks!

[@abdulmlikba9452]

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

[@HungryEagle2610]

Why is there a katana on the shelf?

[@bijayjungkarki7369]

👌

[@sumedhasaxena6702]

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

[@lostfrequency89]

Wolverine

[@lionkiddo]

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

[@geghamayvazyan5637]

why DBs are not using hash tables?

[@MrYokyScape]

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

[@numtostr]

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

[@hnasr]

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.

[@IBITZEE]

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]

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]

kzbin.info/www/bejne/l4vNiqVubNdkmJo Watch the video of this guy. Very well explained how b-tree and b+tree work.

[@user-xedwsg]

Nonsense accent

[@user-xedwsg]

why do you speak like this?! hahahaha, you're not american my brother

[@gunnvant]

Learn by doing