I went on a small rabbit hole on how these work under the hood and it's pretty cool! So I thought I would share.

The real magic of the index is pre-sorting db pointers into a balanced binary tree.

Why SORTED?

Binary search algorithm is insanely efficient and is only possible on a sorted list. At most it will take 20 steps to return a result from a dataset of 1 million. At 10 million the max steps grows to 24. That's the power of an O(log n) function. Compare that to just iterating over 1 or 10 million records and the performance gain is apparent and significant. The obvious downside, especially in the context of solving algorithmic problems in isolation a la LeetCode, is how inefficient sorting is. That's why the pre-sorting part is so critical. But of course, to maintain the sort you have to update the index on every write...

OK but what about the impact on write performance?

This is where the balanced binary tree comes in. If you have just a sorted list or a btree that is not balanced, it's worst case scenario is that it's totally skewed, essentially a linked list. In this case we'd be adding O(n) to every write operation. Not great. But a balanced binary tree is by definition never skewed, and so it's worst case scenario complexity is the same as it's average - O(log n). Same as search. That's pretty dang efficient. It's still not nothing, especially in the context of tens of millions of records, but it's easy to see why indexes are so commonly used even with the hit to write performance.