Throughout this recursion and trees course, we have been working with recursion, binary trees, and special types of binary trees. We are at the point now where we can discuss the logical conclusion of our binary tree structures.
In this lesson, we will be introducing the b-tree, a sorted and balanced tree that contains nodes with multiple keys and children. You will also generalize a BST to a b-tree that has been adapted for any number of children and keys.
We’ll discuss how to implement the insert method by splitting nodes to keep the b-tree sorted and balanced. Finally, we will implement a search method that is similar to previous search methods and analyze the runtime complexities of the methods to give you a clearer idea of when each approach might be most efficient.
As with all of our lessons, as you grapple with these concepts you’ll be challenged to apply them by writing your own code, which is then checked by our automated answer-checker, to ensure that you really understand each concept before moving on.
2. B-Tree Nodes
3. Inserting into a Non-Full Node
4. Inserting into a Full Node
5. Expanding the Tree
6. Insert Performance
7. Searching the B-Tree
8. Next Steps