本题考察二叉排序树查找的时间复杂度。最坏情况下，查找一个不存在的关键字需要遍历整棵树，特别是在树呈现链状结构时，比较次数为树的高度，即O(n)。选项A错误，因为O(log n)适用于平衡树的查找。选项C错误，因为O(n log n)并不适用于查找操作。选项D错误，因为O(1)表示常数时间查找，不适用于此情况。正确答案是B。