腾讯瑞驰后端一面：索引为什么不用红黑树，以及一道 LCA 的四种追问

《面试题目》

1. 联合索引在什么情况下会失效？
2. 索引结构是什么？为什么不用二叉树或者红黑树？
3. 二叉树一定比 B+ 树效率低吗？
4. B 树和 B+ 树的区别是什么？
5. 哈希表发生哈希冲突会怎样？极端场景下退化成 O(n)，怎么优化？
6. 在有序数组里找第一个重复数据的位置，能不能有比 O(n) 更快的方法？口述实现过程。
7. 项目里你负责了什么？结果数据是怎么得到的？
8. 项目的扩展性如何？内部边界在哪里？
9. 手撕：二叉树的最近公共祖先。
10. 如果要求用迭代法，怎么解决？
11. 如果这棵树是有序的（二叉搜索树），怎么优化？给一组数据，口述实现过程。
12. 这道题的时间复杂度和空间复杂度是多少？考虑到了哪些场景？

《参考解析》

联合索引失效的判据是「最左前缀 + 是否对列做了运算」。 常见失效场景：跳过最左列直接查后面的列；范围查询（>、<、between、like 'x%' 之后的列）会让后续列失去索引能力；在索引列上做函数或运算（where date(create_time) = ...、where id + 1 = 10）；隐式类型转换（字符串列传数字、或字符集不一致的比较）；or 连接了没有索引的列；以及优化器估算全表扫描更便宜时主动放弃索引。答的时候要补一句「失效不是绝对的，explain 看 key、type、rows、Extra 才算数」。

为什么不用二叉树或红黑树：核心是磁盘 IO 次数，不是比较次数。 二叉树每个节点最多两个子节点，树高约 log2(N)；一亿条数据树高约 27 层，意味着最多 27 次随机 IO。B+ 树的节点大小对齐磁盘页（InnoDB 默认 16KB），一个节点能放几百上千个键，三到四层就能覆盖上亿行，IO 次数降到 3–4 次。另外 B+ 树的非叶子节点只存键、不存数据，同样大小的页能容纳更多键，进一步压低树高；叶子节点用双向链表串起来，范围查询与排序可以顺序扫描，红黑树做不到。

「二叉树一定比 B+ 树慢吗」是个陷阱题，答案是不一定。 数据全在内存里时没有磁盘 IO 的惩罚，二叉搜索树、红黑树、跳表都能打；此时 B+ 树反而因为节点内要二分查找、缓存局部性不一定最好而未必占优。真实系统里选 B+ 树是因为「数据在磁盘上、按页读取」这个前提。答完补一句判断依据：看数据规模与存储介质，内存索引（如 Redis 的跳表、内存数据库的 T 树）就完全不这么选。

B 树与 B+ 树的区别。 B 树的每个节点都存数据，非叶子节点也带 value，所以同样一页能放的键更少、树更高；B+ 树只有叶子存数据（或行指针），非叶子纯索引，且叶子之间用链表相连，范围扫描和全表顺序扫描都更友好。代价是 B+ 树的点查必须走到叶子，命中的层数固定。

哈希冲突与退化。 冲突本身用链地址法（拉链）或开放寻址解决。退化发生在「大量键落进同一个桶」时：拉链变成一条长链表，查找退化成 O(n)。触发原因有两类——哈希函数质量差（分布不均）和恶意构造（攻击者故意造出一批同桶的键做 Hash-Flooding）。优化手段：换高质量哈希（如 Java HashMap 用扰动函数混淆高位）、树化（JDK 8 起同一个桶内链表长度超过 8 且表容量不小于 64 时转红黑树，退化成 O(log n)）、扩容重哈希降低负载因子、以及给哈希函数加随机种子防构造碰撞。

有序数组里找第一个重复元素，二分可以做到 O(log n)。 思路是利用「有序 + 重复」的单调性：设数组为 a，若 a[mid] == mid（按 0 起编号的值域对齐），说明 mid 之前没有缺失也没有重复、第一个重复一定在右侧；若 a[mid] != mid，说明 mid 之前已经出现过多余元素，答案在左侧（含 mid）。二分收缩到左右相邻且相等的位置即为答案。复杂度 O(log n) 时间、O(1) 空间。如果数组不是「值域连续」的形式，就退化成「找第一个满足 a[i] == a[i+1] 的下标」，同样可以二分：只要 a[mid] == a[mid+1] 就记录答案并往左找，否则看左右两侧哪边还存在重复的可能。答这题要主动说明前提假设，否则面试官会追问「数组长什么样」。

手撕 LCA（最近公共祖先）。 递归版最稳：把「在左右子树里分别找 p 和 q」写成自底向上的返回——当前节点为空或等于 p/q 就返回当前节点；递归左右子树；若左右都非空，说明 p、q 分居两侧，当前节点就是答案；否则返回非空的那一侧。时间 O(n)、空间 O(h)（递归栈）。

迭代版有两种写法：一是用父指针哈希表——先 DFS 一遍记录每个节点的父节点，再把 p 的所有祖先放进集合，然后从 q 往上走，第一个出现在集合里的就是答案；二是用栈模拟后序遍历，避免递归深度限制。面试官问「用迭代法怎么解决」通常是想看你是否知道递归在深树上会栈溢出，答的时候点明这一点。

有序树（二叉搜索树）的优化。 利用 BST 的有序性可以不用遍历整棵树：从根开始，若当前节点值同时大于 p、q，说明答案在左子树；若同时小于 p、q，答案在右子树；否则当前节点就是分叉点。时间从 O(n) 降到 O(h)，平衡 BST 上就是 O(log n)。给一组数据口述时，边说边更新区间：比如在 [6,2,8,0,4,7,9] 里找 2 和 4 的 LCA，从 6 开始（2<6 且 4<6）往左到 2，此时 2 等于 p，返回 2。要顺带说明退化情况：BST 退化成链表时 O(h) 变成 O(n)，所以工程上用平衡树或跳表。

复杂度与边界要主动报。 时间 O(n)（最坏要访问所有节点）、空间 O(h)（h 为树高，平衡树 O(log n)、链状树 O(n)）。边界场景：p 或 q 就是根节点；p 是 q 的祖先；p 与 q 相同；树只有一个节点；节点值重复时 BST 的优化不再成立（要按引用而不是按值比较）。原作者总结里那句「算法题不难，但会对不同场景和边界问得很细，简单题往往一题多解还要有优化」正是这场的评分点——把一题多解和各自的取舍讲出来，比写出一种就跑更重要。