面试问到红黑树， B 树这种原理性的问题，怎么回答比较好?不啰嗦，又能回答到点子上

[kikione]

面试问到红黑树，B 树这种原理性的问题，怎么回答比较好?不啰嗦，又能回答到点子上

[0ZXYDDu796nVCFxq]

能回答概念、原理、应用场景就差不多了
如果能结合业务回答就更好

[securityCoding]

从具体的问题入手吧。
比如数据库索引采用 B 树会有什么问题改成 B+有什么效果。很多 hashmap 冲突时为什么会链表转红黑树。
每个面试官并不一样，但是都不希望你在背理论，能结合问题把技术的演进过程串起来就非常不错了。

[sagaxu]

问问面试官，你们在业务中是如何使用红黑树和 B 树的

[janus77]

我觉得面试这个场景不需要考虑语言是否啰嗦，曾经我也像你那样认为，后来我发现说太少很容易被面试官误解成你答的不好。所以只管多点说，啰嗦也没关系，甚至啰嗦是必须的，不要去考虑语言精炼的事

[geebos]

一般不会问原理吧，记住主要的特性和典型的应用场景就差不多了，当然想要流畅回答还是得把原理搞懂，但是我觉得这些原理能口述讲清楚还真有点难度。比如：

问：B+树的特点是什么
答：B+树的特点就是子节点多，层数少。子节点深度一致。所有子节点组成一个链表。
问：为啥这样搞
答：因为层数少减少 IO 次数。子节点深度一致，查询性能稳定。链表更好地支持范围查询。

我觉得这样基本够用了，可能再和 B 树或者红黑树比较一下，顺便问问红黑树。

[myBatis]

@geebos #5 io 次数和层数没有直接关系，io 次数取决于你操作系统每次从存储中拿取页的大小和每个节点的大小

[myBatis]

@geebos #5 而且增加的不是 io 次数，而是磁盘随机访问的时间

[ufan0]

反向面试一波

[marcushbs]

除非是做数据库或者 OS 的公司，面试问红黑树就是不想好好说话

[asanelder]

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

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

比如说. 想以下这样回答

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

[enchilada2020]

@asanelder 大佬🐮🍺 受教了 感谢

[asanelder]

@enchilada2020 #11 哈哈, 能对别人有帮助俺就欣慰了.

其实细节很多人都记不住, 这没关系, 主要是梳理清来龙去脉, 知道它们的应用场景, 面对问题给出方案和方向就可以了嘛.

方向方案对了, 细节可以在实施过程中补充就行.

而且很多时候, 细节也不用管呢, 这些通用的, 都有成熟的实现, 咱们这些普通人, 就别想着写出更好的实现了.

[geebos]

@myBatis 确实不太准确，B+树的内部节点只保存了指针数据都在叶子节点上， 所以 B+树的内部节点比 B 树要小一些，因此同样的页大小能够保存更多的内部节点，所以 IO 的次数会更少一些。但是你说的磁盘随机访问时间我没太搞懂。

[ReferenceE]

都已经内卷到这个地步了吗？(这玩意 99.9%的人都用不上
背八股文得了

[geebos]

@myBatis 另外层数少也确实减少 IO 次数，因为比较的次数减少了 IO 次数自然会减少。

[dorentus]

@ReferenceE 从硅谷开始一路卷过来😂

https://www.v2ex.com/t/197730

[asanelder]

还有, 俺还补充一点.

俺上面的回答其实是以一种简化的模型为前提的, 不考虑 OS 的虚拟内存以及缓存等.

真实情况肯定会更复杂, 但理解一个东西最好还是现简化模型, 抛开无关的, 否则会太复杂.

[w169q169]

天生 hell 模式。。为啥人家都是要我写 b+树的呢？

[Erichailong]

就像算法导论上上原理型介绍，不要具体细节，核心思想，为什么要用 B+树，他的使用场景。。。

[Erichailong]

@asanelder good 大佬