R2. 2-3 Trees and B-Trees

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
Instructor: Amartya Shankha Biswas

In this recitation, problems related to 2-3 Trees and B-Trees are discussed.

License: Creative Commons BY-NC-SA

[JohnaphorFantazio]

that's the cleanest blackboard i've ever seen

[rohitnikam]

INSERTION STARTS AT 18:20
DELETION STARTS AT 21:30

[guillermoalcantaragonzalez]

Somebody should have told Amartya that he does really well here. He is knowledgeable about the subject, has good material, illustrations and it's clear with his explanations.

[Rohit-tzgs]

What a clear xplanation @ this age!!. It gave me goosebumps to have knowledge like this rather than for passing just exams.

[anonrd]

Great lecture - the passion shines through and the motivation rubs off!

[rahuldeshpande]

2-3 Tree: Atmost 2 keys, at most 3 children

[akrambhat]

Inserting a new key in a 2-3 tree is done as follows. First of all, we always
insert a new key K in a leaf, except for the empty tree. The appropriate leaf is
found by performing a search for K. If the leaf in question is a 2-node, we insert
K there as either the first or the second key, depending on whether K is smaller or
larger than the node’s old key. If the leaf is a 3-node, we split the leaf in two: the
smallest of the three keys (two old ones and the new key) is put in the first leaf,
the largest key is put in the second leaf, and the middle key is promoted to the
old leaf’s parent. (If the leaf happens to be the tree’s root, a new root is created
to accept the middle key.)
author always rocks...

[bc]

That's some seriously young professor.

[jamesreed]

"Cache line size" is the phrase you're looking for

[Abhishek-ignu]

In the Cormen textbook, section 18.1, it is written that if a node has 2*B-1 keys then it is called "full node" and once the # keys become 2*B then split occurs. But in this lecture, split occurs at 2*B-1 itself as here max # keys should be strictly less than 2*B-1. So practically which one to prefer is the confusion here 🤔

[sunny]

He is a grad student of MIT (2017 passout), currently working at Twitter

[wesdaaawg]

I really enjoyed this. Instructor is great at explaining everything. Thank you!

[vatsalgujarati]

it is a good lecture for clearing the concept of B tree.
But I have a doubt that value of maximum keys in a node is less than 2*B-1 or less or equal to 2*B-1 @MIT OpenCourseWare.

[akshaysalunkhe]

It was best solution on b tree i had ever seen on YouTube. Thanks

[ghazalfaris]

Structure Preserve invariance (Rep Invariant)
Common Issue:
One of your nodes will (become) overFull, & Overflow
24:04

[somerandomguy]

The literature on B-trees is not uniform in its terminology

Bayer and McCreight (1972) define the order of B-tree
as the 'minimum number of keys' in a non-root node.

terminology is ambiguous because the maximum number of keys is not clear
: An order 3 B-tree might hold a maximum of 6 keys or a maximum of 7 keys
(4 minimum children holds a maximum of 7 or 8 children)

Knuth (1998) avoids the problem by defining the order to be the 'maximum number of children'
order 3 B-tree : 2-3 tree
order 4 B-tree : 2-3-4 tree (2-4 tree)

[theflubba]

The way this guy explains things is unreal

[tinyanarchy]

the professor is adept at dancing, it seems

[shershahdrimighdelih]

When I know something that I have to teach to a junior but am not completely prepared for it, that's how I teach. Good recitation though

[rajeshdansena]

There is something wrong while explaining Number of Keys. The correction will be :
B-1<= #oF Keys < 2B
check here for details :