R2. 2-3 Trees and B-Trees

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: ocw.mit.edu/6-046JS15
Instructor: Amartya Shankha Biswas
In this recitation, problems related to 2-3 Trees and B-Trees are discussed.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu

[@MyLowFlow]

that's the cleanest blackboard i've ever seen

[@a4addel]

5 years later and I agree, and I hope you are still alive and in a good health

[@hak4fak]

INSERTION STARTS AT 18:20

[@medievalogic]

your comment sounds dirty

[@Anubis10110]

Thanks

[@user-uk6zh6lr1m]

@@medievalogic hahahahhahahhahahahahahaha

[@himanshumaurya428]

@@medievalogic his name too lol

[@batch25official53]

And goes on and on for all

[@luisgraterolpalumbo3200]

DELETION STARTS AT 21:30

[@marcuskim1989]

THANK WHICHEVER GOD MADE YOU. I MEAN IT. I AM NOT JOKING

[@rohitnikam3780]

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

[@martinez536]

Thanks

[@guillermoalcantaragonzalez6532]

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.

[@mauinisikawa1808]

if we are here watching his lectures, there's no way we can get into mit:(

[@rahuldeshpande3516]

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

[@Rohit-tz6gs]

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

[@ria7941]

Thank you so much! This helped me a lot! Keep going with such wonderful videos!

[@kenniolsen181]

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

[@akshaysalunkhe2534]

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

[@sachinpal2424]

What a passionate teacher !

[@Abhishek-ig9nu]

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 🤔

[@bc9477]

That's some seriously young professor.

[@sob4655]

I don't believe he is a professor; a graduate student, teaching for some credit (Teaching Assistant), perhaps. That's because he is terrible at teaching.

[@skippycavanaugh3148]

He was in his 3rd while teaching.

[@zondaken]

+1

[@idobooks909]

I don't see how "he is terrible at teaching" makes him a not professor ;)

[@hasibulalam3367]

its a recitation. they are always conducted by TA.

[@kabirkanha]

Amazing explanation. Thank you.

[@wesdaaawg]

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

[@jamesreed4735]

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

[@danielkurniadi8805]

Ah yes. I think that's the phrase. Another question though, so do we tune the size of each node (which consists of M # of children) to fit (a) RAM line size or (b) Disk block size?

[@seungchullee4222]

It depends on the location where the B-tree stay. If a B-tree lives in a memory, then cache line size is appropriate. If a B-tree lives in a storage, then disk block size is appropriate.

[@timothymagsino]

Such a passionate guy. Respect!

[@somerandomguy8361]

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)

[@sidog6444]

Thanks for this video, this helps a lot during the pandemic!

[@sunny10528]

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

[@asadullahfarooqi254]

who cares he is a terrible teacher....

[@7xr1e20ln8]

@@asadullahfarooqi254 you are a terrible student. Its perfectly understandable.

[@prathamyadav3105]

@@asadullahfarooqi254 Why so much hate? Are you pakistani?

[@asadullahfarooqi254]

Sorry guys @Int 0x80 @Pratham Yadav, I shouldn’t have said that 😔 I take back my words. my sincere apologies. One more thing @Pratham Yadav That was wrong but not political.

[@hil449]

@@7xr1e20ln8 isnt his definition wrong though? in CLRS 3rd edition page 489 the definition for internal nodes of degree t is: t

[@vatsalgujarati1100]

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.

[@tsupeichen693]

Great lecture!

[@theflubba]

The way this guy explains things is unreal

[@user-kq7cw2vf7j]

Thank you for good lecture about deletion op.

[@user-ev9kf9fy3u]

Great Lecture thanks.

[@Sliekas99]

Great explanation.

[@MendaSpain]

10:18 a wild runner appears

[@somerandomguy8361]

he is really good at juggling chalks

[@karansah9506]

Great lecture, thanks!

[@timothylang356]

Amazing lecture!

[@MrSelcukBak]

Thanks a lot mate!

[@mrkingdom75]

This is an excellent education video, thanks a lot. I would like to clarify is B-Tree B is really stands for Branching? Thanks

[@lucha6262]

I believe it stands for balanced

[@rinkirathore6502]

Deletion very beautifully explained

[@tinyanarchy836]

the professor is adept at dancing, it seems

[@rajeshdansena]

There is something wrong while explaining Number of Keys. The correction will be : B-1

[@h8pathak]

Yes. There are two mistakes. B

[@patrickdornellesdasilvavie937]

actually the teacher and you are right, there are two concepts, for Bayer e McCreight(the creators), b ai the minimal number of keys, and Knuth use the minimal number of childrens.

[@hil449]

@@patrickdornellesdasilvavie937 i dont think so. From what i've read both bayer and CLRS use b as the minimal number of children and knuth uses b as the maximum number of children

[@hil449]

@@h8pathak yes, in CLRS 3rd edition page 489 the definition for internal nodes of degree t is: t

[@kevinoliveira8576]

Thank you, this was helpful to me when i was implementing a b-tree in C ;

[@cecekoko9080]

I have to watch 2 time to understand it. Thanks sir

[@rancoxu]

can someone explain why in the last bit we chose to rotate 17 on the left over 30 on the right? thxxxxx in advance!

[@juanbecerra5073]

I believe that it's an arbitrary decision and both are viable operations. Like in deletion, we can choose to propagate the left-most element of the right child OR the right-most element of the left child. Take what I say with a grain of salt, I'm also trying to learn B-Trees lol

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

[@tomlynd8836]

Where can I access the notes he said he would provide?

[@jsarvesh]

ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/recitation-notes/MIT6_046JS15_Recitation2.pdf

[@samiere]

ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/recitation-notes/MIT6_046JS15_Recitation2.pdf

[@ashu7pathak]

Man, once I hit play, I couldn't stop till the end, except for just this comment! ❤✌🇮🇳🇮🇳🇮🇳

[@ghazalfaris8796]

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

Every time I check subtitles for sth I don't understand subtitles help me a lot with this answer: "inaudible"

[@yusufl3800]

+1

[@chinmaydas4053]

Sir what is the best programming language for design and analysis of data structures and algorithms??.. please reply me sir 🙏🙏

[@kenkaneki5433]

c++

[@kenkaneki5433]

c

[@hil449]

c++/java

[@hemantjoshi8388]

how is the order of B tree related to the branching factor? Also how do you find the branching factor?

[@samiere]

B is defined as the branching factor. By definition, this establishes a bound on the number of children: [B,2B) and hence a bound on the number of keys: [B-1, 2B-1]. You can what B is by taking the floor of lg(# of children in any branch)....(correct me if im wrong here...)

[@bharat_arora]

2B-1 = order of the tree (which means the maximum number of branches a node can have ) and B= minimum number of Branches a node can have. and you don't need to find the branching factor, whatever you wish you can take depending on your max height constraints

[@thinhnguyenvan7003]

oh this guy is so energetic. I like that!

[@Speed4Runs]

so cute awww

[@asadullahfarooqi254]

he is just dancing can anyone tell me what beat is that .?? because google just failed to find such a beat..

[@ishwarraghu2463]

dud dud dud dud. du du dud dud dud.. dudu dud dud dudd dududd dud dud...

[@teaMmMate]

Amazing lesson, you have my gratitude.

[@deveshratnasingh9689]

He has Nobody's gratitude...

This guy's pretty good (thumbs up)

[@anmol9096]

Complexity of delete operation?

[@bipros7]

logn

[@jessicahassibi8516]

Have a question... The nodes are not supposed to have more than b-1 keys.. But in his example (26:16 m) he got 5 keys in one leaf... how is that right?

[@jessicahassibi8516]

And b = 4

[@marshalryan5049]

I believe that you've mistaken the maximum bound of keys in a node to not be more than b-1 when the correct one is suppose to be less than 2b-1

[@andrealaw2291]

Insertion explained at 13:50

[@AsmaaMohamed-kr1dm]

Smart explanation

[@Balouk]

What is the meaning of the R in the playlist? Is R1 available?

[@mitocw]

The R means Recitation. It is a session that allows students to ask questions from materials presented in the lectures and to get help if they are stuck on a specific problem or concept. R1 was not recorded.

[@KarenMartikyan]

Guys, the b-tree in 20:08 is not valid, isn't it? We are having problems with the root node

[@marshalryan5049]

I think that in a programming recursive point of view, a root node can be subjective as in every node is a root node, even the ones on the very end of the branch have also a left and right node equivalent to NULL. Thus why as long as its in the lower minimum degree and upper order bound then it's completely valid to the B-Tree's properties.

[@blueninja42069]

make an ASMR video just with chalk sounds

[@rbrtchng]

in the end, what if you delete 3?

[@deepakkumarprajapati8823]

Good qus! After deleting 3, we marge 2 and 7 make it a single node but this node has empty parent then 10 will come down and take it's parent node now 10 will only left node( containing two key 2 and 7) and it's right node is empty. There is one more problem the root node is also empty. Now we are combine 14 and 17 and make the left node/child of 30 and 16 goes up and take's the root place but still 10 doesn't have the right child now 10 will ask to it's sibling 30 help me but 30 say i am bierley full but sibling left child say hay i am eligible to help him, now sibling (30) of left child of right element goes up and combine with 30(now the parent node contain two key 17 and 30) now there will be rotation as well as shifting now 17 goes up now the root node has two key (16 and 17) and 16 come down to 17's left child 10 and there will be two key (i.e 10 and 16) and finally 16 will come down and became the right child of 10.now everything is kk..

[@NoOneIsHereRightNow]

I am in love with this teacher

[@achyutambharatam2116]

Do You Code B-tree by yourself?Understanding this and implementing it makes a huge difference

[@hil449]

youre cute lol pretty eyes

[@rohandalvi6476]

weird that an MIT prof has never implemented B tree but my college need me to do it without plagurism

[@vinayak186f3]

Incredible India 🔥

[@achyutambharatam2116]

Buddy I Also strucked on Implementation.. It's implementation is really very tough on coding point of view 🥴

[@rohandalvi6476]

@@achyutambharatam2116 yes, took me hours. And is kinda stupid coz libraries exist for all this stuff already

[@achyutambharatam2116]

@@rohandalvi6476 Really? Libraries are there! But this is complex type of Dta structure... Sometimes I strucked for week for making their code understand.. Do u also face this?

[@rohandalvi6476]

@@achyutambharatam2116 ofc i do, it was last to last semester

[@alpacino3989]

wow, good vid.....this guy has got a bronze medal in IOI twice.

[@yoavtamir7707]

wow

[@rj-nj3uk]

But bronze is not gold.

[@davidalexander9633]

thanks you sir

[@bishwendrachoudhary2281]

excuse me sir , your deletion of 41 is wrong , why should you bring 30 down ?

[@DenisG631]

in order to have same height for every leaf

[@bishwendrachoudhary2281]

no , actually it is beacuse of 30 's both children has only one number so, merging and then 41 also has one children in both side so merging again.height does n't matter yr

[@saurabhtiwaririshi]

Why log n? shouldn't it be log n base 3

[@seungchullee4222]

Base doesn't matter. By change of base formula of log function. i.e., log_3(x) = Constant * log_10(x). You can pick any base for asymptotic analysis.

[@pavankumardittakavi5325]

I could not follow quite well when he said why use B Trees over BSTs. Can someone please help me understand it?.

[@seungchullee4222]

Memory access time cost is much expensive than CPU compare(

[@seungchullee4222]

If single node's memory size is bigger than cache line, then single node visiting makes caching at most twice. Therefore it seems good to make node's memory size to fit into cache line size.

[@monukumar-xb5cc]

Any one please explain how its no of children B

[@monukumar-xb5cc]

so how can it adjust 19 children in it there

[@hil449]

i think he's wrong, in CLRS 3rd edition page 489 the definition is: t

[@bashaarshah2974]

That's a very nice coat.

[@peterzeng1243]

I like this handsome Indian TA. No Indian accent at all.

[@hypernova54]

North Indian accent is just like this .... You bastards have stereotyped Indian accent with South Indian accent

[@AAZinvicto]

2:35 to 5:32 will change your life :D

[@patcoder1287]

XD yeah man

[@KULDEEPSINGH-rh3go]

I can bet, this faculty is from India.

[@hotamohit]

KULDEEP SINGH great discovery, you want a cookie?

[@KULDEEPSINGH-rh3go]

No thanks

[@soumyadippayra2034]

Kharagpur to be precise.

[@ummonk]

1:32 Is no one in the class paying attention? It isn't at all clear why the depth is logN. 8:04 Finally mentioned that all the leaves are at the same depth, and only then do you know that the depth is actually logN and the tree is balanced.

[@hamzaktk18]

probably everybody knew? its MIT

[@aviralrastogi]

They supposedly studied Binary Search Trees last time. It should be obvious then. And if it isn't clear to you then you are studying in wrong order. Study BST first.

[@saurabhtiwaririshi]

Hi MIT! this lecture doesn't seem to be well connected. Can we have another one?

[@patcoder1287]

No

[@tyyyuuuhunngra618]

He is from our school in india

[@achrafBadiry]

why is he speaking at 1.25 speed lol. I had to check my settings for a second

[@user-df1sk3ct2o]

Cool guy

[@gutierreznunezdavidisrael2511]

Awesome! Greetings from Mexico.

[@omerashraf_]

half an hour worth more than Whole semester in my collage

[@user-wr4ke3qw4m]

He reminds me Tedd Mozbi from How i met your mom? NO??

[@patcoder1287]

Lol

[@coderopes2983]

Why he is in hurry

[@kofiill2509]

Perhaps to rush for his next fix?

[@hunting4ever389]

cool

[@DehXable]

tweakin

[@AbdulWahab-ms6bn]

guys while your watching the vid write awesome!🤣

[@AtticusFinch65]

the way this guys flips his chalk after every sentence pisses me off

[@6puritans9]

this is insane

[@bubeshp]

4:30

[@TheThunderSpirit]

too smart.. didn't understand shit.

[@BrajeshKumar-ez8zs]

NOOO YOU ARE TOO DUMB

[@pithikoulis]

Or simply the guy is bad at teaching.

[@johnd6246]

tits

[@bradleyfallon6847]

I think the reason to use these trees is balancing! Near the beginning, he asks "Why use B-trees over Binary Search Trees". He then explains something about avoiding reading memory from disk. This is not the reason I was taught in my class. The reason I was taught, is that these trees will stay balanced. With a Binary Search Tree, the algorithm of insert could result in the tree being extremely deep on one branch and very shallow on others. This means you will not actually get log(n) performance, since most of the data is in longer branches.

[@thenightspoofed]

I believe that b-trees are to be used when accessing a disk location takes a larger amount of time and thus it is more efficient to have more keys stored in each location.

[@pharoah327]

Why can't it be both? Both better caching and a balanced tree. Most data structures have not one, but several pros and cons over other data structures.

[@hil449]

You're wrong. AVL trees also stay balanced and are way easier to implement, but they only hold 1 key for a given node and each node has only up to 2 children. The reason for using B trees is the one presented in the video

[@hil449]

@@pharoah327 because there are avl trees and red-black trees which are also balanced and way easier to implement but wouldnt work for disk access

[@omerashraf_]

13:30 I know this fake laughs its widely used in my univirsty

[@tuffgonggbUNCTION]

MARANATHA KYMRY

[@kumararun5318]

I think ravindrababu ravula has taught it better than this MIT teacher

[@andrearomanic1803]

[@abbbb5625]

ADHD very chaotic - hard to follow - jumping all over the place and at the end the result is quite confusing.

[@fastrhythms6051]

:)

[@manishkumarparmar412]

He is Shahrukh Khan

[@pajeetsingh]

He wants to dance

[@bonbonpony]

When watching this lecture, I can't help but think that this dude is scamming me right now :q

[@MuharremGorkem]

Very poor presentation missing tones of critical and essential points. Even the "node" and "keys in a node" distinction is not made that clear (and he gets a question because of this basic confusion). I suggest someone who wants to get basics of the subject should definitely NOT start with this lecture. It seems that someone who did not implement a B-tree should not give lectures on it.

[@dallasphillips91]

He is pretty spazy and needs to slow it down a bit. So far the better videos on BTree's for sure, just needs to clean up his lecture and be a bit more prepared.

[@ankurdhuriya]

maybe he is impersonating SRK

[@badalgupta3518]

Searching In BST is O(n) worst case not log(n)

[@artun97]

He said B-trees needed to be balanced