How big is the chance that you select the candidate who happens to know all solutions (e.g. by learning them by heart recently for the dozens of interviews he's planning on doing), but is not a good technical fit? My estimate is: pretty high; Let me explain why.
If you indeed need someone who knows about B* vs B+ trees, why not ask him about that separately ("explain me the difference between ..."), to see if he has the technical background you need? Even if someone understands that difference, that same person might have problems getting DFS right during the whole live interview, for a number of completely irrelevant reasons (nervousness, a momentary lapse, being a bit "rusty", a.s.f.). For the candidate to know the difference between a B+ and B* index/search and to operate a database correctly doesn't require the ability to implement DFS flawlessly (and most likely will never require the person taking a shot at that, for that matter...)
I think the real problem is that some people don't seem to understand the goal of these questions. If you do algo whiteboard questions (and you should!), you should measure the candidate's behavior, reactions, and analytical skills, while attempting a solution with you - and not to find out if the provided solution is correct or not (indeed, its often more interesting when the solution is not and you work with the candidate on locating the issue!). And all the while, the interviewer can try to figure out if he/she wants to work with that person, given the current interaction, too.