ECE356 Lecture Notes - Lecture 15: Innodb, The Algorithm, Binary Tree

• School: University of Waterloo
• Department: Electrical and Computer Engineering
• Course: ECE356
• Professor: Zarnett

Document Summary

If instead of having just a at index le, we decide to have multiple levels, then it means instead of performing a simple binary search on the index, we must traverse a tree. At rst that may appear counterproductive, or at least, not helpful, since we would still have to traverse a bunch of blocks to get to the item we would like to nd. That is true if we pick a binary tree, but, as the title of this section gives away, that"s not what we will do. Thinking back on how linear search works, we check an item to see if it matches and we reduce the remaining space to check by 1. If we do a binary search, we reduce the remaining space to check by half of its current size. Hypothetically we could improve on that if we could reduce the remaining space to search by more than that.