I do like your suggestion, but > Make the interview more about working together and capacity to learn, and less about computer science trivia night at the pub

I do like your suggestion, but > Make the interview more about working together and capacity to learn, and less about computer science trivia night at the pub with no beer. Understanding b-trees is pretty useful. If you work with relational databases, most questions concerning query performance require some understanding of b-trees. I wouldn't ask a candidate to implement b-trees (or a sorting algorithm, or red-black trees, etc.), but asking about their basic properties seems reasonable. Or better yet, asking about the performance of a realistic SQL query which uses a b-tree index.