This is far and away the best indexing video I have watched. Every other one barely goes into how indexing works under the hood, or use analogies that don't really make sense. Keep up the awesome content!
It’s not that accurate though. He used binary search instead of a B tree (though he did briefly mention it) but I think that misguides the viewer into thinking that’s also what is happening. It also fails to explain the importance of avoiding reading from disk (the whole point of using B trees over AVL or red black trees for example).
More on the performance hit of indices on WRITES. How does it work? Does it: A. Insert the new row in the TABLE (O(1)). Find where the index should be placed (O(logn)), insert it there (O(1)). Or does it: B. Insert the new row in the TABLE (O(1)). Query the whole TABLE again (constant). Sort it again (O(idk)). Save it in the index (O(1)). --- I'm guessing A, but I'm not even sure if that's possible lol. I guess the "finding where the index should be placed" would be the slow part and most likely it would be equivalent as doing the same SELECT query for that column as well? Since you mentioned that SELECT is O(logn): Essentially writes would be O(logn). Would that be, correct?
