Bifalgorithm post

Indexing is one of the most asked interview concepts in database. Picture a table with 10 million rows stored on disk in the order they were inserted. That raw storage is called a heap. Search for one email with no index and the database walks the heap row by row, which is 10 million comparisons in worst case. An index avoids that by keeping a second sorted copy of indexed column and has a pointer to actual location of row. That sorted copy is built as a B-tree. In this structure, each node holds a range of values and pointers to child nodes covering smaller ranges inside it. A lookup starts at the root node, compares your value, and picks a branch. Then it repeats that at the next level and the next. 10 million rows collapse into a tree only 4 or 5 levels deep. So instead of 10 million comparisons, you make 4 or 5. Once the tree lookup lands on a match, it grabs the pointer and jumps straight to that row in the heap. Comment index for detailed walkthrough.

Indexing is one of the most asked interview concepts in database. Picture a table with 10 million rows stored on disk in the order they were inserted. That raw…