别给面试官感觉是背理论,背八股文就行.
可以不必记细节.
但要回答出, 红黑树, B 树是什么? 用来解决什么问题的? 该问题如何不使用红黑树, B 树, 可以使用什么来解决?

俺比较赞同 2 楼老哥的, 你把技术演进过程串起来就很不错了.

比如说. 想以下这样回答

----------------

无论红黑还是 B 树, 都是用来解决搜索问题的, 搜索越快越好嘛.

其实最初的, 就是二叉搜索树. 如果这颗树比较平衡的话, 其搜索效率就等同于二分查找了.

但是呢? 现实是, 二叉搜索树不平衡, 如果不平衡, 你想想, 搜索效率就很差了.

所以呢? 能不能构建二叉搜索树时能让它尽量平衡一些?

于是就有了平衡二叉搜索树.

但是呢, 平衡二叉搜索树插入删除比较麻烦. 为了这种平衡, 付出代价太大(如果你就创建一次, 不经常变动也没事, 反正只有变动时才有代价)

为了即要平衡, 又不想付出太大代价, 就有了红黑树了

当然, 红黑树消除了插入删除的代价, 所以, 对于 HashMap 的某一个 bucket, 如果元素很多, 使用红黑树是很适合了.(因为 HashMap 一般经常要删除和修改)

到了这里, 红黑树还是二叉树, 层还是比较深的, 和搜索的过程是和层的深度是有关的, 每一次要到某一层的节点加载到内存来比较.

如果所有数据都在内存没问题, 但数据要是在磁盘呢? 每加载一次就是从磁盘到内存的一次 IO, 你也知道, 磁盘读写是很慢的. 所以能不能尽量减少这种 IO 呢?

B 树就可以了, B 树不是二叉树, B 树是一种多叉搜索树, 每一个节点都有多个元素.

这样, 对于全部节点固定情况下, B 树肯定比红黑树要浅了, 这样, 潜在的最大 IO 次数一定少了啊.

所以 B 树就应用在数据库的场景下.

同理, 如果你的搜索涉及到多种速度不一的存储介质, 也是可以考虑 B 树的.


-----------------------

俺觉得答成以上这样, 就很好了.

至于现场手写红黑, B 树, 或者问你红黑 B 树的细节的, 俺觉得这是面试官的问题.

你想想, 这些算法是什么人想出来的? 是数学家, 计算机科学家啊? 如果不是你自已想出来的, 你怎么可能熟记于心?

如果你能熟悉写出来, 只有一种情况, 你基本上每隔几天就写一遍, 可能自己默写了几十遍, 几百遍.

只一种算法你就要花这么多时间熟记于心, 还有很多算法呢? 你也能做到每天写一遍?

所以, 遇到什么都不问, 就让你手写红黑或细节的. 都是面试官的问题. 可能是以下几种情况

1. 面试官是天才, 其智商和数学家一样, 这些红黑树对于他们就像 1+1 一样简单
2. 面试官什么也不会, 就是最近背了几遍红黑树, 在你面前炫耀罢了
3. 面试官根本不想要你

以上三种, 这种公司不进也罢.