#08 - Tree Indexes: B+Trees (CMU Intro to Database Systems)

15-445/645 Intro to Database Systems (Fall 2024)
Carnegie Mellon University

[VenuS-pg]

what a legend! "It's just a linkedlist with scaffolding on top to get to the required node quicker - Andy P" and just like that B+tree seems simple!

[MohammedAl-Jawaheri]

I'm a bit confused. at 34:50 it seems like we split 16 (as opposed to 15) because 16 was the key that was going to cause the split, but when we launched it up, we decided to take the middle node as the one to split up (13). why isn't it a consistent rule? when 16 was inserted why didn't we say

13 14 15 16 17

we'll split up 15

Edit: NVM
so it's the smallest key in the right node in the leaf for partitioning purposes and then later always the middle one (before insertion of the new node) ?

[ivanychevsergey]

Thanks for amazing lectures and such thorough preparation! Question: during delete operation in some cases we are doing gymnastics that reduce the height of the subtree (e.g. when pulling „13” node down). We’re not paying attention to other parts of the tree — their tree remains the same (for example, imagine that „13” node had a parent with other children). This might cause imbalance in the tree, no? Must the B+ tree be perfectly balanced and how do we maintain the invariant here?

[ivanychevsergey]

Another question: since insert or delete might involve the merging of all subtrees including the root (worst case) that we meet during the descending to the leaf node, do we actually keep latches to all of them/root of the B+ tree when doing any insert/delete?

[nsudhir_here]

44:53 I had the same question, thanks for asking.
So question is how to find that two children belong to same parent when we are not maintaining pointer from child to parents.
based on the answer of the instructor I assume it's responsibility of the programming-language or programmer to decide how he cn find it.

[МаксимПадалица-их]

What does Andy drink from the thermos?

[cccc]

What exact data goes in leaf nodes? My understanding says that every leaf node has a key, pointer to siblings, and value where value is rowid(ie file-id + page-id + slot-id). Am I right?

[cccc]

if database is using index tree to store tuples, wont it cause memory issues as number of tuples may be too large?

[rohandvivedi]

Can some one help me with this:

How does borrowing key from the siblings work, when we are dealing with variable length keys?

Because now there is a possibiltiy that borrowing just 1 key may not suffice.

And, also the new parent separator entry may make the parent node overfull or underfull.