Doesn't the second solution have to do the same B-tree traversal?
Good question, today, and good discussions!!
I assume you meant me, not Chris. 🙂
The second solution has to do the B-tree traversal at least once, to find out iff the row already exists. If not, it doesn't have to (*) repeat the traversal to perform the actual insertion.
The first solution on the other hand has two statements, that are executed after each other. So the B-tree has to be traversed for the IF, and if the NOT EXISTS is found to be true, the same B-tree traversal will then have to be repeated for the actual INSERT. Since it's two statements, there's no way the optimizer can improve on this.
(*) Disclaimer - I don't know what optimizations are actually in place. This describs theoretically possible behavior; I have not done any tests to assess what the actual behavior is like.