
Episode 485: Howard Chu on B+tree Data Structure in Depth
Software Engineering Radio - the podcast for professional software developers
00:00
Using a Binary Tree?
A bee tree will attempt to do the insert first, and then fix up anything that needs t be fixed up afterwards. In an a vl tree, we add a little extra information to each note. We call it a balance factor. The algorithm that maintains the tree will go up and down examine these balance factors. And if the balance factor ever exceeds one or minus one, like if the balast factor gets to two or gets to minus two, then then it knows, oh, this tree is now too heavy on one side,. That's the basic idea behind an avl tree.
Transcript
Play full episode