On the other hand I've seen so much hand-optimized code that used the correct data structures to solve the wrong problem.
Yes, that is kind of unfair - you want people who grasp the problem and find a good solution. But I prefer the people who solve the problem at hand in a wrong way instead of solving the wrong problem in the best imaginable way.
And in order for the reviewer to recognize the situation at all, and then point it out, they would need knowledge of the underlying data structures, their performance, and as you mention, pragmatism to know when to use it.
(I'm presuming that everyone on your team shares the responsibility of code review, and you don't funnel it through a few people with knowledge of how things work. (I believe that robs those that don't of the opportunity to learn through review.))
Have I ever implemented one? Not yet. Do I ask for a BTree implementation or exact, low-level understanding on an interview? No.
* I routinely find people using the wrong data structure, when there exists a better one, with better O() time/space.
* I find people tend to not understand BTrees, particularly when there are two attributes being indexed. Given an index on (a, b), I find it common misconception that the BTree can efficiently answer `$a_min < a < $a_max AND $b_min < b < $b_max`. (I.e., people do not understand that the tree cannot make use of the second < condition, and must scan potentially many more rows than they intend.)
* Graph theory. git uses it. Any sort of dependency tree uses it.
That said, I acknowledge that software engineering does require a lot of non-theoretical knowledge, which is why I ask both types of questions in an interview.