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
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.
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!!
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?
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
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.
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.
@@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?
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 :)
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
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
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
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
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
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.
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 ruclips.net/video/jsWwFL_iqVM/видео.html
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
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
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
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?
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
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.
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.
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... ;-)
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.
![Felix "Unfair" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/Oswujxm2Ag0/mqdefault.jpg)
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
hey hussein , can u tell me how to join the channel to get access to all the content ? :D
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.
A+ explanation of B+ tree topic
Thank you Hussein
Abdul Bari, Tushar Roy, Hussein Nasser, Alex Xu, Andrew Ng - those people are simply legends in explaining convoluted concepts in simple language.
Abdul bari? The fat guy? Are we talking about the same person?
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!!
MongoDB tends to have index bloat problems, even with only 2-3 indexes they take up 10%-20% of the original dataset size.
Database Internals is an excellent book that goes through various algorithm and implementations for storing data.
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?
@@wassimboussebha2561 you can just right into Database Internals.
Really loved how you correlate things. The mongodb example was very eye opening
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
A million dollar advice given by him
People like you motivate me to study hard and develop some skills to be proud of.
Is that a sword in the background? Damn... That looks lifesize lmao
Look like a Katana.
16:49, that's what she said. Informative video!
MongoDB uses B+ by WiredTiger default storage engine.
I'm looking all your videos, great job man and thanks for all the information again
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.
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.
If we store indexes in RAM,isn't that volatile?
@@Keerthiprincess2061 You only store a copy of the index file in RAM. The entire index file + content will be on the disk
@@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?
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 :)
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
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
Very clear and interesting, thanks
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
1:45 Impeccable Japanese
thanks hussein
here after completing the DBE course in udemy!
How was it , any suggestions for learning backend with node
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
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
Great content guy, thanks for sharing. Would be great another video discusing LSM Tree
b+ tree is used in Kubernetes(etcd database)
Since MongoDB 3.2 Mongodb uses Wiredtiger as default storage engine which can use LSM Tree.
Thank you! I didn’t know that.
More info here source.wiredtiger.com/mongodb-3.4/lsm.html
thank you so much very valuable information
you're great Hussien
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.
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
ruclips.net/video/jsWwFL_iqVM/видео.html
@@hnasr The link you shared and a few other docs, helped me get a better understanding. Thanks.
You are awesome man.. thank you so much for this incredible channel.
Thanks for this Hussein!
1:46 my friend, did you really say "thank you ソウーマッチョーですか"😁
Thank you.
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
Really Awesome Nasser
Really helpful video
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
Thank you!
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
Why is there a katana on the shelf?
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?
I think memory swapping happens once you are out of memory and OS is responsible for resource management
Quick question. Why cant you load parts of Btree in memory, but load parts of a b+tree in memory?
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
@@hnasr ah right. Thanks!
Hussein, can you recommend some RUclips channels about database engineering?
ruclips.net/video/aZjYr87r1b8/видео.html
what is the difference between b+tree and b*(star)-tree
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.
"My right, don't know if it is your right!" 😁
is that a samurai? behind
Awesome wideo
For a second I got confused on why is CarryMinati talking about B+ trees lol
👌
learn by doing
When you are so early that there's no pinned comment.
If MongoDB using Btree and PgSQL using B+tree. So, this means pgsql reads are faster than mongodb?
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.
why DBs are not using hash tables?
Doesn't scale well when you have millions or billions of rows. Also hard for range queries.
Posted from terminal
Wolverine
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... ;-)
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.
ruclips.net/video/aZjYr87r1b8/видео.html
Watch the video of this guy. Very well explained how b-tree and b+tree work.
Nonsense accent
why do you speak like this?! hahahaha, you're not american my brother
Learn by doing