1. Pick a simple but relatively obscure data structure, something they are unlikely to have crammed the night before. I always start by asking the candidate if they are familiar with it; the answer is almost universally "no". I then pull out a wikipedia printout and a notepad, and spend 10 minutes explaining it to them, with diagrams. Once they are sure they have understood the basic operations, I ask them to implement one of these basic operation we just walked through. The amount of code here should be ~10 lines; keep on adding simplifying assumptions until it is.
2. Pick a fundamental data structure from a high-level language runtime, something you would use without thinking: python lists, javascript objects, that kind of thing. I emphasise that familiarity with said language is not required, and list some real-world properties and performance characteristics (access speed, iteration, ordering, mutation), as well as common and less-common use cases. I then ask the candidate how they think it is implemented under the hood (i.e., if you wanted these semantics in a language that didn't natively provide them, how would you do it?) I often don't have a full answer myself, so we brainstorm the requirements and implementations together; no code, just open-ended discussion. The best candidates have often emailed me afterwards, having looked up an actual open-source implementation.
Maybe not the healthiest attitude ...
> 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.
Your ability to efficiently teach people stuff that you claim is important is a chance to hold yourself accountable for how well you actually know something AND whether it is actually important at all. If an interviewer taught me something I didn't know, and then quizzed me on it, I'd be impressed as heck, and I'd wanna work with that person (if they were not an asshole).