R2. 2-3 Trees and B-Trees
Vložit
- čas přidán 3. 03. 2016
- 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
that's the cleanest blackboard i've ever seen
5 years later and I agree,
and I hope you are still alive and in a good health
INSERTION STARTS AT 18:20
your comment sounds dirty
Thanks
@@medievalogic hahahahhahahhahahahahahaha
@@medievalogic his name too lol
And goes on and on for all
DELETION STARTS AT 21:30
THANK WHICHEVER GOD MADE YOU. I MEAN IT. I AM NOT JOKING
INSERTION STARTS AT 18:20
DELETION STARTS AT 21:30
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 🤔
What a clear xplanation @ this age!!. It gave me goosebumps to have knowledge like this rather than for passing just exams.
Great lecture - the passion shines through and the motivation rubs off!
2-3 Tree: Atmost 2 keys, at most 3 children
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.
if we are here watching his lectures, there's no way we can get into mit:(
It was best solution on b tree i had ever seen on CZcams. Thanks
What a passionate teacher !
Thank you so much! This helped me a lot! Keep going with such wonderful videos!
That's some seriously young professor.
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.
He was in his 3rd while teaching.
+1
I don't see how "he is terrible at teaching" makes him a not professor ;)
its a recitation. they are always conducted by TA.
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.
I really enjoyed this. Instructor is great at explaining everything. Thank you!
Amazing explanation. Thank you.
Such a passionate guy. Respect!
The way this guy explains things is unreal
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)
"Cache line size" is the phrase you're looking for
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?
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.
Thanks for this video, this helps a lot during the pandemic!
can someone explain why in the last bit we chose to rotate 17 on the left over 30 on the right? thxxxxx in advance!
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
Structure Preserve invariance (Rep Invariant)
Common Issue:
One of your nodes will (become) overFull, & Overflow
24:04
Thank you for good lecture about deletion op.
he is really good at juggling chalks
Great lecture!
10:18 a wild runner appears
Great Lecture thanks.
Insertion explained at 13:50
He is a grad student of MIT (2017 passout) , currently working at Twitter
who cares he is a terrible teacher....
@@asadullahfarooqi254 you are a terrible student. Its perfectly understandable.
@@asadullahfarooqi254 Why so much hate? Are you pakistani?
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.
@@7xr1e20ln8 isnt his definition wrong though? in CLRS 3rd edition page 489 the definition for internal nodes of degree t is: t
the professor is adept at dancing, it seems
This is an excellent education video, thanks a lot. I would like to clarify is B-Tree B is really stands for Branching? Thanks
I believe it stands for balanced
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
Great explanation.
Amazing lecture!
Thank you, this was helpful to me when i was implementing a b-tree in C ;
Deletion very beautifully explained
Thanks a lot mate!
Great lecture, thanks!
Man, once I hit play, I couldn't stop till the end, except for just this comment! ❤✌🇮🇳🇮🇳🇮🇳
I have to watch 2 time to understand it. Thanks sir
Where can I access the notes he said he would provide?
ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/recitation-notes/MIT6_046JS15_Recitation2.pdf
ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/recitation-notes/MIT6_046JS15_Recitation2.pdf
What is the meaning of the R in the playlist? Is R1 available?
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.
Complexity of delete operation?
logn
how is the order of B tree related to the branching factor? Also how do you find the branching factor?
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...)
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
he is just dancing can anyone tell me what beat is that .?? because google just failed to find such a beat..
dud dud dud dud. du du dud dud dud.. dudu dud dud dudd dududd dud dud...
Sir what is the best programming language for design and analysis of data structures and algorithms??.. please reply me sir 🙏🙏
c++
c
c++/java
oh this guy is so energetic. I like that!
in the end, what if you delete 3?
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..
so cute awww
This guy's pretty good (thumbs up)
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?
And b = 4
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
There is something wrong while explaining Number of Keys. The correction will be :
B-1
Yes. There are two mistakes.
B
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.
@@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
@@h8pathak yes, in CLRS 3rd edition page 489 the definition for internal nodes of degree t is: t
Guys, the b-tree in 20:08 is not valid, isn't it? We are having problems with the root node
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.
make an ASMR video just with chalk sounds
Smart explanation
That's a very nice coat.
Every time I check subtitles for sth I don't understand subtitles help me a lot with this answer: "inaudible"
+1
Amazing lesson, you have my gratitude.
He has Nobody's gratitude...
thanks you sir
wow, good vid.....this guy has got a bronze medal in IOI twice.
wow
But bronze is not gold.
Why log n? shouldn't it be log n base 3
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.
I am in love with this teacher
Do You Code B-tree by yourself?Understanding this and implementing it makes a huge difference
youre cute lol pretty eyes
I could not follow quite well when he said why use B Trees over BSTs. Can someone please help me understand it?.
Memory access time cost is much expensive than CPU compare(
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.
Hi MIT! this lecture doesn't seem to be well connected. Can we have another one?
No
excuse me sir , your deletion of 41 is wrong , why should you bring 30 down ?
in order to have same height for every leaf
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
half an hour worth more than Whole semester in my collage
Any one please explain how its no of children B
so how can it adjust 19 children in it there
i think he's wrong, in CLRS 3rd edition page 489 the definition is: t
the way this guys flips his chalk after every sentence pisses me off
I like this handsome Indian TA. No Indian accent at all.
North Indian accent is just like this
....
You bastards have stereotyped Indian accent with South Indian accent
He is from our school in india
weird that an MIT prof has never implemented B tree but my college need me to do it without plagurism
Incredible India 🔥
Buddy I Also strucked on Implementation.. It's implementation is really very tough on coding point of view 🥴
@@achyutambharatam2116 yes, took me hours. And is kinda stupid coz libraries exist for all this stuff already
@@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?
@@achyutambharatam2116 ofc i do, it was last to last semester
Cool guy
2:35 to 5:32 will change your life :D
XD yeah man
4:30
tweakin
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.
probably everybody knew? its MIT
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.
I can bet, this faculty is from India.
KULDEEP SINGH great discovery, you want a cookie?
No thanks
Kharagpur to be precise.
He reminds me Tedd Mozbi from How i met your mom? NO??
Lol
Awesome! Greetings from Mexico.
cool
why is he speaking at 1.25 speed lol. I had to check my settings for a second
Why he is in hurry
Perhaps to rush for his next fix?
guys while your watching the vid write awesome!🤣
MARANATHA KYMRY
too smart.. didn't understand shit.
NOOO YOU ARE TOO DUMB
Or simply the guy is bad at teaching.
tits
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.
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.
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.
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
@@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
this is insane
13:30 I know this fake laughs its widely used in my univirsty
ADHD very chaotic - hard to follow - jumping all over the place and at the end the result is quite confusing.
He is Shahrukh Khan
I think ravindrababu ravula has taught it better than this MIT teacher
When watching this lecture, I can't help but think that this dude is scamming me right now :q
:)
He wants to dance
Searching In BST is O(n) worst case not log(n)
He said B-trees needed to be balanced
maybe he is impersonating SRK
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.
he is too impatient and he has to correct himself way too often. I am so glad I never had such lecturers.