本文整理了 2026 年暑期实习面试（偏数据库存储方向）中出现的问题及详细答案，问题来源于多场面试，涵盖 Raft 协议、TinyKV、Bustub、MVCC、LSM-Tree、B+Tree、全文索引、向量数据库以及 C++ 等多个方向。

一、Raft 协议与分布式一致性

Q1：Follower 给 Candidate 投票需要满足什么条件？

Follower 给 Candidate 投票需要同时满足以下三个条件：

  1. Candidate 的 term ≥ Follower 的 current term：如果 Candidate 的 term 更小，说明是过期的选举请求，直接拒绝。
  2. Follower 在本 term 内尚未投过票，或已投票给该 Candidate：保证每个节点在同一 term 内最多只投一票。
  3. Candidate 的日志不比 Follower 的日志旧（选举限制，Election Restriction）：
    • 先比较各自最后一条日志的 term，term 更大的更新；
    • 若 term 相同，则 index 更大（日志更长）的更新。

选举限制的意义：确保当选的 Leader 一定拥有集群中最完整的已提交日志，防止已提交日志被覆盖——这正是 Raft Leader Completeness 属性的保证。

Q2：Follower 变成 Candidate 需要经过什么检查？

Follower 转变为 Candidate 的触发条件是选举超时（electionTimeout）：Follower 维护一个 electionElapsed 计数器，每 tick 加一，当计数器超过随机化的选举超时阈值且该节点没有收到来自 Leader 的心跳时，触发选举。

转换过程（becomeCandidate()）：

  1. 角色切换为 Candidate，term += 1；
  2. 给自己投票（votes[self] = true），重置计时器；
  3. 广播 MsgRequestVote 给所有其他节点，携带自己的 term、lastLogIndex、lastLogTerm。

“转变之前是否有检查？”
严格来说没有主动检查，转变是被动触发的：Follower 只要在 electionTimeout 内没有收到有效心跳，就会自动触发。这里没有额外的前置条件判断，只要超时就转换。

Q3：是否所有 Follower 会在同一瞬间全部发起选举？为什么？

不会。Raft 通过随机化选举超时来避免这一情况：

每个节点的选举超时时间是在 [ElectionTick, 2×ElectionTick) 范围内随机取值，不同节点的超时时刻不同。在实践中，最先超时的节点率先变成 Candidate 发起选举，其他节点收到该 Candidate 的 RequestVote 消息后，只要 term 和日志条件满足，就会投票，多数情况下该节点能在其他节点超时之前就赢得选举。

只有在极端情况（如多个节点同时超时导致分票）才会出现多个 Candidate 同时竞选，此时由于各自任期号不同且没有节点能获得多数票，会触发下一轮选举，随机超时机制保证最终一定能选出 Leader。

Q4：Raft 日志什么时候算 Commit？什么时候算 Apply？顺序关系？

  • Commit（提交）：Leader 收到来自集群多数节点（含自身）的成功 AppendEntries 响应，且该日志条目属于当前 term（Leader 只能通过当前 term 的日志推进 commitIndex），则将 commitIndex 推进到该日志的 index，此时该日志被认为已 commit。committed 状态由 Leader 通过下一次心跳或 AppendEntries 的 commit 字段告知 Follower，Follower 更新自身 commitIndex。

  • Apply（应用）：节点将 [lastApplied+1, commitIndex] 范围内的日志逐条送入状态机执行，完成后更新 appliedIndex，此时日志才真正影响系统状态（写入 KV 存储等）。

  • 顺序关系：严格满足 applied ≤ committed，即日志必须先 commit 才能 apply，且 apply 是幂等的——已 commit 的日志一定最终会被 apply，这是 Raft 的安全性保证之一。

Q5：快照的作用是什么？快照包含哪些主要信息？

快照解决的问题：Raft 日志是不断增长的，若不加以处理，日志文件会无限增大，导致：

  1. 磁盘空间耗尽；
  2. 节点重启时需要重放所有历史日志才能恢复状态，耗时极长；
  3. 新加入的节点需要从头同步大量历史日志，影响集群扩容速度。

快照通过将某个时间点的状态机状态完整存储下来，并截断该时间点之前的所有日志，来解决上述问题。

快照的主要内容（以 TinyKV 为例）：

  • KV 数据：状态机在快照时刻的完整数据（即 kvDB 的内容）；
  • 元数据：
    • snapshot_index：快照对应的最后一条已应用日志的 index；
    • snapshot_term：快照对应的最后一条已应用日志的 term；
    • region_state：Region 的元信息（StartKey、EndKey、RegionEpoch、Peers 等）；
  • 这些元数据是接收快照的节点用来恢复 RaftLog 状态和 Region 配置的关键依据。

Q6：为什么要实现 Multi-Raft？单个 Raft 的问题是什么？

单个 Raft Group 存在两个根本性瓶颈：

  1. 可扩展性受限：所有数据由同一组节点管理，无法通过增加新节点来线性提升容量，只能垂直扩容。
  2. 并发处理能力有限：所有写请求必须经过同一个 Raft Group 串行提交，即使有多台机器，吞吐量也被单个 Raft Group 的处理速度所限制。

Multi-Raft 的解法：将整个 key 空间划分为多个 Region，每个 Region 负责一段连续的 key 范围，由独立的 Raft Group 管理。不同 Region 的请求可以并行处理，同时支持随数据量增长动态分裂 Region 和迁移 Region，实现水平扩展。

Q7：调度器（Scheduler）根据什么逻辑来做 Region 迁移？

TinyKV 的 Scheduler（类似 TiDB 的 PD）定期收集各 Store 上报的 Region 心跳，维护集群全局视图，主要做以下调度：

  1. Region Balance（负载均衡）：统计每个 Store 上的 Region 数量，若 Store 之间 Region 数量差异超过阈值（默认超过 2），则将一个 Region 从 Region 较多的 Store 迁移到较少的 Store。迁移流程是：先对目标 Store AddPeer（ConfChange），等新 Peer 追上日志后，再 TransferLeader（将 Leader 迁移到目标 Store），最后 RemovePeer（移除旧 Store 上的 Peer）。
  2. Leader Balance：尽量让 Leader 均匀分布在各个 Store，避免单一 Store 承担大量读写请求。

Region 分裂（Split）逻辑：当一个 Region 的数据量超过阈值时，触发分裂：将原 [StartKey, EndKey) 的 Region 在中点 key 处一分为二，生成两个新 Region，各自维护独立 Raft Group。分裂是通过 Raft 日志中的 AdminCmdType_Split 指令来完成的，确保分裂动作在 Raft Group 所有副本上一致执行。

Q8：TinyKV 快照隔离（Snapshot Isolation）是如何实现的？

TinyKV 基于 Percolator 协议实现了快照隔离，核心依赖全局时间戳服务（TSO）：

  1. 事务开始时获取 start_ts：从全局 TSO 获取单调递增的时间戳作为事务的起始时间戳，代表这个事务"看到的快照"版本。
  2. 读操作按版本读：所有读都读取 commit_ts ≤ start_ts 的最新已提交版本，不读取 start_ts 之后提交的数据，也不读取任何未提交数据。在 MVCC 存储层，key 以 (user_key, commit_ts) 的复合键存储，读时通过 start_ts 做版本过滤。
  3. 写操作（Prewrite）加锁：写操作先在 CfLock 列族写入锁记录，防止并发写冲突（First-Writer-Wins）；
  4. 提交时获取 commit_ts：提交时再次申请一个 TSO 作为 commit_ts，写入 CfWrite 作为版本标记。

通过 start_ts 构建的一致性快照，保证了同一事务内多次读取相同 key 的结果一致（可重复读），且不会读到并发事务的中间状态。

Q9：TinyKV 事务中冲突检测是如何做的？

TinyKV 采用乐观并发控制（OCC） + Percolator 2PC，冲突检测发生在 Prewrite 阶段：

  1. 写写冲突检测：在对 key 加锁（写 CfLock）之前，检查该 key 上是否已存在其他事务的锁（GetLock）。若存在锁且锁的 ts 不是本事务的 start_ts，说明有另一个并发事务正在写这个 key，当前事务的 Prewrite 失败，需要执行重试或等待（等待锁释放后清理）。
  2. 读写冲突检测（防止写覆盖已读数据）：检查该 key 在 (start_ts, max) 版本范围内是否有已提交的写记录（MostRecentWrite）。如果有，说明有另一个事务在本事务开始之后提交了对这个 key 的修改，本事务的快照已过期，Prewrite 失败，需要重试（First-Writer-Wins 原则）。

Q10：快照隔离和可串行化的区别？

维度快照隔离（SI）可串行化（Serializable）
并发异常可防止脏读、不可重复读、大部分幻读防止所有并发异常
写偏斜（Write Skew）无法防止防止
实现方式MVCC + 时间戳2PL 或 SSI
性能高（读不加锁）低（全局锁或冲突检测开销大）

写偏斜示例：两个事务同时读取"在岗医生 ≥ 1"的条件满足，各自将一名医生设为下班，最终导致在岗医生为零。两者没有写同一行（无写写冲突），但都基于快照做了破坏整体约束的决策。

可串行化快照隔离（SSI）：PostgreSQL 的解决方案是在读上打标记（读依赖图），提交时检测是否存在"反向读依赖循环"，若有则 abort 其中一个事务，在不降低 SI 并发度的前提下消除写偏斜。

二、Bustub Buffer Pool / 内存管理

Q11：Buffer Pool（缓冲池）如何设计？

Bustub Buffer Pool Manager（BPM）负责在有限的内存 Frame 和无限的磁盘 Page 之间做透明管理。核心组件如下：

  1. LRU-K 替换策略：使用两个队列——
    • history_list：访问次数 < K 的 Frame，按 FIFO 淘汰；
    • lru_list：访问次数 ≥ K 的 Frame，按最早的第 K 次访问时间淘汰（更能适应偶发访问，不像 LRU 那样容易被冷页污染）。 当 Frame 访问次数达到 K 时，从 history_list 移至 lru_list。
  2. Disk Scheduler：将磁盘 IO 操作异步化，放在独立线程池中执行，避免 IO 阻塞 BPM 的其他操作。
  3. Page Guard（RAII）：ReadPageGuard 和 WritePageGuard 包裹页面的读写锁生命周期，防止忘记 unpin 或解锁。

并发设计：对 BPM 的元数据（free_list、page_table 等）加一把全局 latch；对 Frame 本身加 frame 级别的读写锁，使得 IO 操作可以独立于 BPM 元数据操作并发执行，从而利用 IO 并发提高吞吐量。

Q12：什么场景下需要使用内存管理（Buffer Pool）？

缓冲池是数据库必需的，原因在于：

  • 磁盘 IO 代价极高：随机磁盘 IO 与内存访问的速度差距在 3-5 个数量级。对热点数据缓存在内存中可以极大减少磁盘访问。
  • 数据管理的透明性：数据库层通过页表（page_table）维护磁盘 Page 与内存 Frame 的映射，上层访问数据就像访问内存一样，不需要关心数据是否在磁盘上。
  • 预取（Prefetch）与顺序扫描：对大表顺序扫描时，BPM 可以按需预取后续页面，减少 IO 等待。

典型应用场景：OLTP 通常有大量随机点查（热点数据常驻内存收益最大）；OLAP 大表扫描则需要控制 BPM 不被扫描数据污染（使用 SCAN 访问模式的页面不应留在 LRU 中太久）。

Q13：Bustub 与 OceanBase 在内存管理上的差异？

对比维度Bustub BPMOceanBase MemStore/BlockCache
粒度以固定大小页（4KB/8KB）为单位OB 分为 MemTable（LSM 写缓存）和 Block Cache（SSTable 读缓存），粒度更灵活
写路径写操作先修改内存 page，脏页延迟刷盘OB 写先进 MemTable（内存），达到阈值后 Minor Compaction 落盘
淘汰策略LRU-KOB Block Cache 基于 LRU 变体，并区分不同数据类型设置不同优先级
多租户无多租户概念OB 支持多租户，每个租户有独立的内存配额限制
内存上限参数化（pool_size）通过 memory_limit 精确控制，并有内存超限保护机制

Q14：业务场景——亿级门店数据的实时支付流缓存如何设计？

针对实时支付流补充门店信息的场景（读多写少、数据量亿级），缓存设计思路如下：

  1. 分层缓存：

    • L1：进程内 LRU 缓存（如 Guava Cache/Caffeine）：缓存最热的数万条门店信息，访问延迟 < 1ms，无网络开销；
    • L2：分布式缓存（如 Redis Cluster）：缓存更大范围的门店数据，以 store_id 为 key，序列化的门店对象为 value，延迟约 1-5ms；
    • L3：数据库（MySQL/TiDB）：兜底查询，亿级数据建立主键索引，查询 < 20ms。

  2. 缓存预热：服务启动时将高频访问的门店（如近 30 天交易量 TopN）预加载到 L1/L2，避免冷启动时大量穿透到数据库。

  3. 缓存更新策略：门店信息更新频率低，可使用 Cache-Aside（旁路缓存）模式：更新数据库后主动删除或更新缓存，设置合理 TTL（如 5 分钟）。

  4. 防穿透/防击穿：对不存在的 store_id 缓存空值（防穿透）；对热点 key 使用分布式锁防止缓存击穿时大量请求同时打到数据库。

Q15：LRU 与 LRU-K 算法的区别？

维度LRULRU-K
淘汰依据最近一次访问时间最早第 K 次历史访问时间最早
冷数据抗污染弱（一次全表扫描就能把热数据全部淘汰）强（访问 K 次才能进入主队列，偶发访问不影响热数据）
实现复杂度简单（双向链表 + 哈希表）稍复杂（需维护访问历史队列）
K 值选择—通常 K=2，平衡冷热分离与复杂度

适用场景：数据库缓冲池应使用 LRU-K（如 PostgreSQL 的 Clock-Sweep、InnoDB 的 Young/Old 分区 LRU），防止顺序扫描污染热数据。

三、B+ 树索引与并发控制

Q16：介绍 B+ 树的原理

B+ 树是一种自平衡多路搜索树，所有数据存储在叶子节点，内部节点仅存储路由键。核心特性：

  • 内部节点：存储 m 个 key 和 m+1 个子节点指针，只用于路由，不存数据；
  • 叶子节点：存储 m 个 key 和对应 value（或 RID 行指针），叶子节点之间通过单向/双向链表相连，支持范围扫描；
  • 平衡性：所有叶子节点到根的路径长度相同，保证 O(log n) 的查找复杂度；
  • 高扇出：内部节点可以存储大量 key，树高很低（亿级数据只需 3-4 层），缓存命中率高（内部节点常驻内存）。

相比 B 树，B+ 树不在内部节点存数据，使内部节点扇出更大，且叶子链表使范围查询只需找到起始叶子再顺序遍历即可，效率极高。

Q17：多线程对 B+ 树进行插入、删除、查找时如何保证数据一致性？

核心技术是 Latch Crabbing（锁螃蟹行走）：

查找（乐观）：

  1. 从根节点开始，加读锁；
  2. 定位到子节点后，先加子节点读锁，再释放父节点读锁；
  3. 如此"蟹行"至叶子节点，对叶子持有读锁直到读完后释放。

插入/删除（悲观）：

  1. 从根节点开始，对所有经过的节点加写锁；
  2. 如果当前节点被判断为"安全节点"（插入时未满、删除时超过半满，即不会发生分裂或合并），则释放其所有祖先节点的写锁；
  3. 继续向叶子推进，在根到叶子路径上只保留可能发生结构变更的节点的写锁。

乐观锁优化：对插入/删除先以乐观方式（只加读锁）走到叶子，检查叶子是否安全；如果安全（不会触发分裂/合并），则直接操作；如果不安全，释放所有锁，回退到悲观方式重来。Bustub 的 24fall 版本要求实现此优化以通过 Contention 测试（加大锁检测）。

Q18：MySQL 中索引类型有哪些？

  • 主键索引（Primary Key）：聚簇索引，叶子节点存储整行数据，一张表只能有一个；
  • 唯一索引（Unique Index）：保证索引列值唯一，叶子节点存储主键值（非聚簇）；
  • 普通索引（Index）：无唯一约束，叶子节点存储主键值，查询完需回表；
  • 复合索引（Composite Index）：多列联合建立的索引，需遵循最左前缀原则；
  • 全文索引（Full-Text Index）：基于倒排索引实现，支持 MATCH ... AGAINST 语法；
  • 前缀索引：只对字符串列的前 N 个字节建立索引，节省空间但无法覆盖全值。

Q19：复合索引的基本原则？

  1. 最左前缀原则：复合索引 (a, b, c) 只有查询条件包含最左边的列 a 时才能使用到该索引。WHERE a=1 AND b=2 可走索引，WHERE b=2 AND c=3（跳过 a）则无法走索引；
  2. 选择性高的列放左边：基数（Cardinality）高的列放前面，能更快过滤数据；
  3. 范围查询列放最后：(a, b, c) 中若 b 有范围查询（b > 10），则 c 上的索引条件无法使用；
  4. 覆盖索引：查询的所有列都在索引中，可直接从索引返回结果，无需回表（回表代价高）；
  5. 排序/分组列建索引：ORDER BY 或 GROUP BY 的列如果在索引中，可避免额外的排序操作（filesort）。

Q20：遇到慢查询如何排查？建立索引时应注意什么？

排查步骤：

  1. EXPLAIN 分析执行计划，关注 type（全表扫描为 ALL，最优为 const 或 ref）、key（走了哪个索引）、rows（扫描行数估计）；
  2. 检查是否满足最左前缀，是否发生了索引失效（如对索引列使用函数、隐式类型转换）；
  3. 查看是否有大量回表（Extra: Using index condition vs Using index）；
  4. 使用慢查询日志（slow_query_log）定位线上慢 SQL。

建立索引注意事项：

  • 不要建太多索引：每个索引都增加写操作的开销；
  • 索引列应具有高选择性（重复值少），低基数的列（如性别 0/1）建索引意义不大；
  • 优先考虑覆盖索引，让查询在索引层完成，避免回表；
  • 频繁被排序、分组、连接条件用到的列应建索引。

Q21：什么是索引覆盖（Covering Index）？

索引覆盖是指查询所需的所有数据列都包含在某个索引中，数据库不需要回表（不需要通过主键再去聚簇索引取数据），直接从二级索引的叶子节点就能返回结果。

-- 假设有索引 (name, age)
SELECT name, age FROM users WHERE name = 'Alice';
-- 此查询可以覆盖索引，无需回表

SELECT name, age, address FROM users WHERE name = 'Alice';
-- address 不在索引中，需要回表

覆盖索引可以极大减少 IO：二级索引通常比聚簇索引小得多，且可以只在内存中扫描，避免了随机 IO 的回表操作。

四、MVCC 与事务隔离

Q22：Bustub 的 MVCC 机制如何设计？如何解决写冲突？

Bustub（23fall Project4）的 MVCC 基于时间戳实现快照隔离，核心设计如下：

版本链：每行数据通过 UndoLog 形成版本链，最新版本存储在 table heap 中，历史版本形成链表。每个版本包含：ts（时间戳）、修改前的旧值（用于回滚）。

读操作：事务以 read_ts 读取数据，沿版本链找到 ts ≤ read_ts 的最新版本——即该事务"开始时"存在的版本，保证快照读。

写操作与写冲突检测：

  • 写操作先检查 table 中该行的当前 ts 是否为临时写时间戳（TXN_TEMP_TS，表示有其他事务正在写）；
  • 若存在未提交的写（First-Writer-Wins）：后来的写事务直接 abort；
  • 写操作将该行 ts 标记为 TXN_TEMP_TS，提交后更新为 commit_ts。

与 MySQL Read View 的对比：

  • MySQL InnoDB 使用 Read View 结构（m_ids 活跃事务列表 + m_low_limit_id + m_up_limit_id）来判断版本可见性；
  • Bustub 直接用单调递增的时间戳比较 ts ≤ read_ts，更简洁，但依赖全局严格单调的时间戳。
  • MySQL 的 RC 每次 SELECT 重新创建 Read View（能看到最新提交），RR 只在第一次 SELECT 时创建（整个事务看到相同快照）。

Q23：RC 和 RR 的区别？快照读、当前读的区别？

Read Committed（RC）vs Repeatable Read（RR）：

隔离级别Read View 创建时机可重复读幻读防护
RC每次 SELECT 都创建新的 Read View✗✗
RR事务第一次 SELECT 时创建，之后复用✓InnoDB 通过间隙锁防止

快照读 vs 当前读：

  • 快照读：普通 SELECT，通过 MVCC 读取历史快照版本，不加锁，不阻塞其他事务；
  • 当前读：SELECT ... FOR UPDATE、SELECT ... IN SHARE MODE、INSERT/UPDATE/DELETE，读取最新版本并加锁（行锁 + 间隙锁），确保操作的是最新数据。

五、可扩展哈希索引（Extendible Hash）

Q24：可扩展哈希中每个桶数据很多时如何优化？

当单个桶数据量过多时，可扩展哈希会触发桶分裂（Split）：将桶一分为二，通过增加 local_depth 用更多位来区分数据。但如果数据分布极度不均匀（如哈希碰撞严重），分裂可能频繁发生而收效甚微。

几种优化思路：

  1. 桶溢出链（Overflow Chaining）：桶满时不立即分裂，而是追加一个溢出桶，形成链表。类似 HashMap 的 chaining，但读性能略降；
  2. 更好的哈希函数：使用分布更均匀的哈希函数（如 MurmurHash、xxHash）减少碰撞；
  3. 多级哈希目录：Bustub 的三层设计（Header → Directory → Bucket）通过 Header 将不同前缀的 key 分散到不同 Directory，天然增加并行度，减少单一 Directory 的竞争；
  4. 聚类内优化：若桶内数据有序（如排序），可改用跳表或B+树存储桶内数据，将桶内查找从 O(n) 降到 O(log n)。

六、全文索引与存储结构

Q25：全文索引是怎么做的？Doc ID 如何定义？分词流程？

全文索引基于倒排索引（Inverted Index）：

倒排索引结构：

  • 倒排链（Posting List）：token → [(doc_id, frequency), ...]，记录包含该词的所有文档及词频；
  • 正排索引（Forward Index）：doc_id → doc_length，记录每个文档的词汇数，用于 BM25 分数计算。

Doc ID 定义：在 OceanBase seekdb 实现中，Doc ID 是内部自增的整数 ID，通过 doc_id_rowkey 映射表与主表的 rowkey 相互映射。这样设计的好处是内部用小整数 ID 压缩倒排链体积，最终回表时再通过映射获取真实行数据。

分词（Tokenizer）流程：

  1. 字符过滤：统一转小写、去除 HTML 标签、处理特殊字符；
  2. 分词：英文按空格/标点切词，中文使用分词算法（如结巴、IK Analyzer）；
  3. 停用词过滤：去掉 “the”、“a”、“是”、“的” 等无语义词；
  4. 词形还原/词干提取：英文可对 “running” → “run” 等做词干化处理；
  5. N-gram：LIKE 场景下将文本拆成 n 个字符的滑动窗口（N-gram），构建多粒度倒排索引。

Q26：LIKE 语法如何做查询优化？

LIKE 'prefix%' 可以利用普通索引（前缀匹配），但 LIKE '%suffix' 或 LIKE '%substring%' 会触发全表扫描。

优化途径：

  1. N-gram 全文索引：将文本按 N-gram 切分后建立倒排索引，对于 substring 匹配，用 N-gram 做粗粒度过滤（先用倒排索引找候选集），再用精确匹配验证，大幅减少扫描量；
  2. SkipIndex（Chunk 级跳过）：如 Milvus 的 NgramBF（N-gram Bloom Filter），在 Chunk 粒度上预判整个 Chunk 是否包含目标子串，若不包含则整个 Chunk 跳过，无需加载数据；
  3. 前缀倒排：对于前缀 LIKE 场景，建立字符前缀的倒排索引，支持前缀快速定位。

Q27：全文索引的存储结构如何设计？如何支持实时增删改查？

全文索引维度扩展性极强（一篇文档可能产生成百上千个 token），不适合直接用行列存储。可参考 LSM-Tree 思想：

  1. 内存缓冲层（MemTable）：新写入的文档先在内存中构建增量倒排索引，快速响应写入；
  2. 分 Segment 并行构建：数据按时间或大小划分为多个 Segment，每个 Segment 独立构建完整倒排链，并发写入；
  3. Compaction 合并：后台将多个小 Segment 的倒排链归并成更大的 Segment，同时处理删除（Tombstone 标记）；
  4. 读时多路归并：查询时对所有在用 Segment 的倒排链做多路归并，取合集或交集。

Elasticsearch 和 Lucene 就是采用这种"Segment + Merge"模式，每个 Segment 内部倒排链有序，查询时多路归并。

Q28：LSM Tree 下全文索引的 Compaction 灾难如何避免？

当长文档被大幅修改（如从 10000 词删减到 2 词），旧文档产生的大量 token 需要在 Compaction 时被标记为删除，导致涉及极宽 key 范围的 Compaction，甚至触发 Full Compaction。

优化思路：

  1. Segment 隔离删除：删除不修改旧 Segment，而是在新 Segment 中写入 Tombstone 记录；在 Compaction 时合并时去除已删除条目，避免单次 Compaction 范围过大；
  2. 增量更新（Delta Log）：只写入变更部分（新增/删除的 token），而非重写整个文档的倒排链，大幅减少写放大；
  3. 分层限制 Compaction 范围：类似 LevelDB 的分层策略，控制每次 Compaction 只合并相邻层的特定范围 SSTable，避免全局 Compaction；
  4. 文档版本标记：在 Compaction 时，只有当该文档的所有旧版本 token 都被新版本覆盖后才真正删除，防止误删。

七、LSM-Tree 与 B+ Tree 对比

Q29：LSM-Tree 和 B+ Tree 的区别？各自适合什么场景？

维度B+ TreeLSM-Tree
写性能随机写，需要维护树结构有序，写放大大顺序写（WAL + MemTable），写性能极高
读性能直接 O(log n) 定位，读性能稳定需要从多层 SSTable 查找，读放大较大
空间放大低（数据只存一份，但碎片化）高（同一 key 可能在多层都有版本）
适合场景读多写少、随机读、需要事务支持写多读少、日志型数据、时序数据
代表系统MySQL InnoDB、PostgreSQL、SQLiteRocksDB、LevelDB、Cassandra、HBase

B+ 树的 index 节点不一定要全在内存：B+ 树的内部节点通过 Buffer Pool 缓存在内存中，但如果内存不足，内部节点也会被淘汰到磁盘，只是树高越低（内部节点越少），越容易全部缓存在内存中（如 InnoDB 的 BP 热点页缓存）。

分布式 B+ 树：TiDB 的 TiKV 使用 RocksDB（LSM-Tree）作为底层，在其上模拟 B+ 树语义；Google Spanner 使用自研的分布式 B+ 树。

Q30：如何用 LSM 的思想优化 B+ Tree？

核心思路：Append-only（追加写） 代替原地修改，仅在读时合并 delta。

具体设计（类 Bw-Tree 方案）：

  1. Delta Record（增量记录）：不直接修改 B+ 树节点，而是将更新写成 Delta Record 追加到 Page 的链表头部；
  2. Mapping Table：维护逻辑 Page ID → 物理内存地址的映射（CAS 原子操作），读时通过 Mapping Table 定位最新的 Delta 链；
  3. Consolidation（合并）：后台线程定期将 Delta 链合并成完整页面（类似 Compaction），控制 Delta 链长度不超过阈值；
  4. 无锁并发：由于写操作只追加 Delta，不修改原有页面，多个写线程可以通过 CAS 竞争追加，无需页面写锁。

这种设计将 B+ 树的随机写转为顺序追加，写性能大幅提升；但读时需要遍历 Delta 链，读性能略降。Bw-Tree 是微软 Hekaton 内存数据库引擎中实际使用的数据结构。

追问：这种小块合并设计会不会影响事务隔离级别？
不会影响，隔离级别由 MVCC 的版本可见性机制保证，与底层存储是原地写还是追加写无关。Delta 链和 Compaction 只是存储层的实现细节，MVCC 通过 ts 版本号来判断哪个版本可见，该语义在合并前后保持一致。

Q31：基于 LSM 结构如何实现 Repeatable Read？Tombstone 如何打标记？

版本号设计： 在 RocksDB 等 LSM 实现中，key 编码为 (user_key, sequence_number)，其中 sequence_number 单调递增，代表写入顺序（也可用时间戳）。读时指定 snapshot = read_seq，只读取 sequence_number ≤ read_seq 的最新版本。

Repeatable Read 实现：

  1. 事务开始时获取当前 sequence_number 作为 snapshot；
  2. 事务内所有读操作都使用此 snapshot，RocksDB 内部会过滤掉所有 sequence_number > snapshot 的版本；
  3. 由于 snapshot 是事务级常量，整个事务期间看到相同的数据快照，满足 Repeatable Read。

防幻读： 顺着版本链读不仅能防不可重复读，对于范围查询，只要 snapshot 固定，即使后来的事务在该范围插入了新 key，这些 key 的 sequence_number > snapshot，对当前读操作不可见，自然防止了幻读。

Tombstone（墓碑标记）： LSM-Tree 的删除不是原地删除，而是写入一个特殊的 Delete Marker（Tombstone），内容为空值，sequence_number 为当前写入序号：

Key: (user_key, seq=100, type=DEL)   ← Tombstone
Key: (user_key, seq=50,  type=PUT)   ← 旧值

读时，若找到的最新版本是 Tombstone（type=DEL），则认为该 key 已被删除，返回空。在 Compaction 时，当 Tombstone 已经下推到最底层且没有比它更旧的版本，才能真正从磁盘删除该条记录。

八、Milvus SkipIndex 与向量数据库

Q32：Milvus 向量数据库是怎么查的？大致流程？

Milvus 的向量查询采用 ANN（Approximate Nearest Neighbor） 搜索，主要流程：

  1. 请求路由：Proxy 接收用户查询（Query Vector + TopK + Filter），路由到对应 Shard 的 QueryNode；
  2. Segment 查询：QueryNode 对所有已加载的 Segment（Growing Segment + Sealed Segment）并行执行查询；
  3. 向量索引（ANN）：对 Sealed Segment，使用 HNSW/IVF_FLAT/IVF_PQ 等向量索引做近似最近邻搜索，获得候选集；Growing Segment 则暴力全量扫描；
  4. 标量过滤（SkipIndex）：在向量搜索之前或同时，对标量过滤条件（如 age > 18）利用 SkipIndex 跳过不满足条件的 Chunk，减少需要精确计算距离的向量数；
  5. Reduce 合并：将多个 Segment 的 TopK 候选结果在 QueryCoord/Proxy 层归并，返回最终 TopK。

Q33：SkipIndex 在内存中如何表示？结构是如何的？

SkipIndex 的内存表示以 Segment 下 Field 下 Chunk 三级层次组织：

SkipIndex
└── CacheSlot<FieldChunkMetrics>[]  (每个 Field 对应一个数组，每个元素是一个 Chunk 的统计信息)
    └── FieldChunkMetrics（抽象基类）
        ├── MinMaxMetrics<T>       (最小值/最大值，适用于数值型、字符串)
        ├── SetMetrics<T>          (集合统计，适用于低基数字段，IN 查询优化)
        ├── BloomFilterMetrics     (布隆过滤器，适用于点查)
        └── NgramBFMetrics         (N-gram 布隆过滤器，适用于 LIKE 子串匹配)

FieldChunkMetrics 提供统一接口：CanSkipUnaryRange（单值比较）、CanSkipBinaryRange（范围查询）、CanSkipIn（IN 查询），查询时批量判断 Chunk 是否可跳过。

Q34：如何对不同数据类型分类构建 SkipIndex？

开源之夏项目中，我扩展了 SkipIndex 统计信息，对不同类型分别构建不同的 Metrics：

数据类型构建的 Metrics支持的查询优化
数值型（int/float/double）MinMaxMetrics>, <, >=, <=, BETWEEN
字符串（低基数）MinMax + SetMetrics=, !=, IN, NOT IN
字符串（高基数/全文）MinMax + NgramBFMetricsLIKE '%substring%'，子串匹配
通用类型BloomFilterMetrics= 点查（probabilistic 跳过）

构建逻辑在 SkipIndexStatsBuilder 中，通过 std::conditional_t 和模板特化，在编译期根据类型参数选择对应的统计信息构建策略，对 std::string 特殊处理（使用 string_view 避免拷贝）。

Q35：RAG 在 AI 问答平台中起什么作用？Context 是越多越好吗？

RAG（Retrieval-Augmented Generation）的作用：大模型的知识截止于训练时间，无法感知实时或私有数据。RAG 将用户问题向量化，在外部知识库（向量数据库）中检索相关文档片段，将其拼入 Prompt，为模型提供"实时外挂记忆"。以 Milvus 为后端的 RAG 系统中，用户问题经嵌入模型（Embedding Model）转换为向量，再通过 ANN 检索召回相关文档，最后将文档作为 Context 输入 LLM 生成答案。

在 Agent 对话场景中，外置记忆库可存储历史对话摘要、用户偏好等，使 Agent 在有限 Context Window 内获取更相关的背景信息。

Context 并非越多越好：

  • Lost-in-the-middle 问题：研究表明 LLM 对长上下文中首尾位置的信息关注度高，对中间位置信息的注意力显著下降，关键信息容易被"遗忘"；
  • 增加 Token 消耗和推理延迟；
  • Context 利用率在 30%~50% 时效果最佳，超过后边际收益递减甚至下降。

因此 RAG 的核心优化方向是召回精度（检索到真正相关的片段）和 Re-Ranking（对召回结果重新排序），而非一味增大检索数量。

Q36：向量索引的落盘与非落盘方法有哪些？各有什么特点？

类型代表算法特点
纯内存（非落盘）HNSW层次化导航小世界图，查询精度和速度最优，内存占用大
纯内存ANNOY随机超平面树，构建快，不支持动态更新
磁盘友好（落盘）DiskANN图结构 + 磁盘分级存储，支持亿级向量，内存占用小
落盘IVF_FLAT聚类中心存内存，原始向量存磁盘，精度高但内存消耗较大
落盘IVF_PQProduct Quantization 压缩向量，大幅降低存储开销，精度略损

HNSW：通过多层跳表图结构实现快速近似检索，查询时从最高层逐层定位，每层用贪心搜索找最近邻节点，复杂度约 $O(\log n)$，是目前精度与速度综合最优的内存向量索引。

DiskANN：通过分层设计（高层节点驻内存，底层节点存磁盘），实现单机十亿级向量检索，适合存储受限但规模超大的场景。Milvus 默认推荐 HNSW 用于内存场景，DiskANN 用于超大规模落盘场景。

九、C++ 知识

Q37：std::move 底层是如何实现的？

std::move 本质上只是一个类型转换（static_cast），并不做任何数据移动：

// 标准库实现（简化版）
template<typename T>
typename std::remove_reference<T>::type&& move(T&& t) noexcept {
    return static_cast<typename std::remove_reference<T>::type&&>(t);
}

它的作用是将任意类型的引用（左值引用或右值引用）无条件转换为右值引用（T&&），从而使编译器选择调用移动构造函数或移动赋值运算符，而非拷贝构造函数。真正的"移动"（资源转移）是由用户定义的移动构造函数完成的，std::move 只是给编译器一个"可以对这个对象执行移动语义"的信号。

Q38：把移动构造 delete 掉，对 std::move 结果赋值会触发移动构造还是拷贝构造？

如果一个类只删除了移动构造（MyClass(MyClass&&) = delete）但保留了拷贝构造（MyClass(const MyClass&)），则 std::move 之后赋值会触发拷贝构造。

原因：std::move 只是产生一个右值引用类型，编译器在重载决议时优先寻找移动构造，但移动构造被 delete 后，编译器会退而求其次，尝试拷贝构造。右值引用可以绑定到 const T&（拷贝构造的参数类型），因此拷贝构造会被调用。

struct MyClass {
    MyClass(const MyClass&) { /* 拷贝构造 */ }
    MyClass(MyClass&&) = delete;  // 移动构造被删除
};

MyClass a;
MyClass b = std::move(a);  // 触发拷贝构造，因为移动构造不可用

注意区分：如果同时删除了移动构造和拷贝构造，则 std::move 后的赋值会编译报错。

十、Raft 工程化进阶问题

Q39：Raft 中 Leader 选举如何保证一致性？每个 term 最多几个 Leader？

每个 term 最多只有一个 Leader。这由 Raft 的投票机制保证：

  • 每个节点在同一 term 内最多投出一票（持久化 votedFor）；
  • Leader 需要获得多数节点（quorum） 的投票才能当选；
  • 多数派中不可能存在两个互不重叠的子集，因此同一 term 内不可能有两个节点同时获得多数票，即不可能出现两个 Leader。

一致性保证：

  • 选举安全性（Election Safety）：每个 term 最多一个 Leader；
  • Leader 完整性（Leader Completeness）：当选的 Leader 一定包含所有已提交日志（由选举限制保证）；
  • 日志单调性：Leader 的日志是所有已提交日志的超集，不会回退。

Q40：发生网络分区时 Raft 如何处理？分区恢复后会怎样？

场景：5 节点集群分区为 A（3 节点，含原 Leader）和 B（2 节点）。

分区期间：

  • A 区（多数派，3 节点）：原 Leader 仍然有效，能获得多数派心跳确认，继续正常提供读写服务；
  • B 区（少数派，2 节点）：因收不到 Leader 心跳，会超时发起选举，但只有 2/5 的票，无法获得多数派支持，选举永远失败，不会产生新 Leader。B 区对外停止服务，term 会不断递增但无实际效果。

分区恢复后：

  • B 区节点带着更高的 term 重新连接，A 区原 Leader 收到更高 term 后退化为 Follower；
  • 重新触发选举，由拥有最新日志且 term 满足条件的节点（通常是 A 区的节点之一）当选新 Leader；
  • B 区节点的日志被截断并与新 Leader 同步，B 区期间任何未提交的操作不会对外产生影响；
  • 最终整个集群恢复一致状态。

Q41：什么是脑裂（Split-Brain）？Raft 如何防止脑裂？

脑裂（Split-Brain） 是指分布式系统发生网络分区后，被隔离的节点无法感知自己处于少数派，仍然以为自己是合法 Leader 并继续对外提供写服务，导致集群中同时出现两套独立演进的数据版本，最终无法协调的严重一致性问题。

Raft 防止脑裂的三重机制：

  1. 多数派写入（核心保障）：Raft 中一条日志只有被超过半数节点持久化后，Leader 才会 commit 它。设 Leader A 被网络隔离在少数派（如 5 节点集群中仅剩 2 节点），它接受的写请求无法获得多数确认，永远无法提交，客户端不会收到成功响应。由于任意两个多数派集合必有交集，同一 term 内不可能在两个分区同时产生被持久化的提交版本，脑裂从根本上不会发生。

  2. 孤岛检测（Leader 主动退化）：实践中（如 etcd/TiKV），Leader 在每个心跳周期统计收到响应的节点数，若连续若干轮收到的有效响应数未超过半数，Leader 主动退化为 Follower，立即停止对外提供写服务。这样即使 Leader 已经被孤立在了少数派分区中，也能主动让位，彻底杜绝少数派 Leader 继续服务的可能。

  3. Term 机制自动收敛：分区期间，少数派因反复选举超时而不断递增 term（虽无法成功 commit）。分区恢复后，少数派携带更高 term 重新接入，多数派原 Leader 收到更高 term 的消息后立即退化为 Follower；新一轮合法选举产生唯一 Leader，少数派期间写入的未提交日志被新 Leader 的日志覆盖，集群自动收敛到一致状态。

与 Pre-Vote 的关系：Pre-Vote（见 Q42）主要解决少数派 term 虚高造成的"选举风暴"，是对 Q41 第 3 点的补充优化，防止分区恢复时高 term 节点破坏正在运行的合法 Leader。

Q42：Pre-Vote 机制是什么？解决什么问题？

问题：标准 Raft 中，少数派节点在分区期间不断递增 term。分区恢复后，高 term 的 B 区节点重新加入，会导致 A 区正常工作的 Leader 立即退化，引发不必要的选举，造成短暂服务中断。

Pre-Vote 机制：节点在正式发起选举（term+1）之前，先以当前 term 发送一轮预投票探测。若能获得多数节点的预投票确认，才真正递增 term 并发起正式选举；否则不递增 term，继续等待。

效果：分区中的少数派节点无法获得预投票，因此不递增 term，分区恢复后也不会以高 term 冲击已在工作的 Leader，消除了选举风暴问题。

Q43：Region 分裂时如果 Leader apply 成功但 Follower 失败了怎么办？

Region Split 是通过 Raft 日志项提交的，受 Raft 一致性保护：

  1. Split 指令被 propose 为一条 AdminCmdType_Split 的 Raft Entry；
  2. 该 Entry 必须被集群多数节点写入日志后，Leader 才推进 commitIndex 标记其为 committed；
  3. 一旦 committed，Raft 保证所有节点最终都会 apply 该条日志——Follower 崩溃重启后通过日志重放或快照追进度，必然执行该 Split；
  4. 不存在"Leader 已分裂成功但 Follower 永久分裂失败"的情况。

核心原理：已 commit 的日志必须确保所有节点最终 apply，这是 Raft 的基本安全性保证。

Q44：TinyKV Region 分裂时，底层数据如何处理？

Region 分裂只修改元信息，不移动任何底层数据：

  1. Raft 提交分裂命令：Leader 将分裂命令封装为 AdminCmdType_Split 的 Raft Entry，多数节点持久化后 commit，所有副本按序 apply。

  2. Apply 阶段更新元信息：根据分裂点 key 将原 Region 的 [StartKey, EndKey) 一分为二：原 Region 缩短 key 范围，新 Region 承接另一半 key 范围；将两者的 Region 元信息（Region ID、Epoch、Peers）写入 raftDB，并向 Scheduler 上报新 Region 的存在。

  3. 数据原地不动：底层 KV 数据全部存储在 badger（LSM-Tree）中，所有行仍按原有 key 存储，物理位置一字未动。分裂后，两个 Region 各自通过 key range 过滤，服务自己范围内的读写请求。

  4. 物理迁移延后执行：数据的实际搬迁（将新 Region 均衡到其他 Store）是在后续 Region Balance 调度中，通过快照机制异步完成的——分裂操作仅负责范围划分，搬迁操作与分裂解耦。

这种设计使分裂极其轻量，避免了分裂时执行大规模数据复制带来的耗时和 IO 压力。

Q45：一个完整的事务除了 MVCC 还需要什么？

MVCC 只解决了读写隔离（快照隔离），完整的事务系统还需要：

  1. 原子性（WAL + Undo Log）：WAL 保证崩溃恢复时已提交事务不丢失；Undo Log 保证事务可以完整回滚；
  2. 写写冲突检测：MVCC 的快照读不加锁，但写操作之间需要冲突检测防止丢失更新，可用悲观锁（2PL）或乐观验证（如 Percolator 的 Prewrite 阶段冲突检查）；
  3. 持久性（WAL 刷盘）：通过 fsync 保证已提交事务的 WAL 在返回客户端前落盘；
  4. 全局时间戳服务（分布式场景）：分布式事务需要全局单调递增的 TSO 保证跨节点快照一致性，如 TinyKV 的 TinyScheduler 提供的 TSO；
  5. 两阶段提交（分布式场景）：跨 Region/节点的原子提交需要 2PC 协调，如 Percolator 的 Prewrite + Commit 两阶段。

Q46：Raft 日志复制的完整流程是怎样的？

Raft 日志复制是 Leader 将客户端命令安全持久化到集群所有节点的核心流程，共 7 个阶段：

  1. Client 请求：客户端将写命令发送到 Leader（若发给 Follower，Follower 通过 leader redirect 将请求重定向至 Leader）。

  2. 追加本地日志：Leader 将命令封装为 Log Entry（带当前 term 和递增 index），先追加到自己的 RaftLog 并持久化（WAL 刷盘），再对外广播。

  3. 并行广播 AppendEntries：Leader 向所有 Follower 并发发送 AppendEntries RPC，携带 prevLogIndex/prevLogTerm（一致性校验用）、新日志条目和当前 leaderCommit。

  4. Follower 校验与追加：Follower 检查 prevLogIndex/prevLogTerm 是否与自己日志末尾匹配：

    • 匹配：追加新条目，持久化，回复成功；
    • 不匹配：拒绝，返回冲突信息（冲突 term 和该 term 的首条 index），Leader 据此快速回退 nextIndex[i] 并重发。

  5. 多数确认后 Commit：Leader 计数确认该条目的节点数，一旦超过半数（含自身），将 commitIndex 推进到该 index；通过随后一次 AppendEntries 的 leaderCommit 字段通知各 Follower 更新其 commitIndex。

  6. Apply 到状态机：Leader 和 Follower 各自将 [lastApplied+1, commitIndex] 范围内的日志按序送入上层状态机（KV 写入、配置变更等），完成后推进 appliedIndex。

  7. 响应 Client：Leader Apply 完成后将执行结果返回给客户端；若 Leader 在 Apply 前崩溃，客户端会超时重试，新 Leader 当选后幂等重放即可。

核心不变式：appliedIndex ≤ commitIndex ≤ len(log)，apply 严格落后于 commit，committed 日志在任何节点故障下都不会丢失。

十一、OceanBase 全文索引优化

Q47：TopN 下推与 Bitset 在全文索引优化中如何起作用？

这两个优化来自 OceanBase2025 决赛的全文索引性能优化工作。

TopN 下推：

原始执行路径是全量全文检索后取 TopN。TopN 下推将"只要 Top-10"的信息提前传递给全文索引扫描算子，底层 BMW（Block-Max WAND）合并算法在计算过程中可以提前剪枝——一旦某个候选文档的 BM25 分数上界低于当前 Top-10 的最低分，直接跳过，大幅减少无效计算。TopN 下推将查询性能从约 5 分提升到约 100 分（以比赛评分衡量）。

Bitset 过滤：

查询带有固定标量条件（base_id IN (...) 且 id < 1000），条件结果集极小。预先计算满足标量过滤条件的 doc_id 集合，构建 Bitset，在倒排链扫描时用 Bitset 快速跳过不满足条件的文档，将有效计算范围缩减到极小，避免大量无效的 BM25 计算和回表操作。

Q48：查询最近 30 天点赞数最高的 10 条记录，如何快速查找？

基础方案：建立 (create_time, like_count) 复合索引，利用时间范围过滤 + 排序取 TopN。

优化方向：

  1. 覆盖索引 + 降序索引：建立 (create_time DESC, like_count DESC) 索引，ORDER BY 可直接利用索引顺序，避免 filesort；
  2. 定时缓存：用定时任务每分钟异步计算 Top-10 并存入 Redis，查询时直接读缓存，统计计算离线化；
  3. 按天分桶预聚合：将 30 天拆为 30 个日维度桶，每天维护 Top-N 有序集合（Redis SortedSet），查询时合并 30 个桶的结果，复杂度 O(30×K)；
  4. 近似统计：超大规模场景下用 Count-Min Sketch + 堆做近似 Top-K，适合对精确性要求不严格的业务。

十二、算法题

算法1：带过期时间的 LRU 缓存

在 LRU 基础上，对缓存中的对象增加淘汰机制：超过 x 时间没有访问就被淘汰。

设计思路：在 LRU 的双向链表 + 哈希表基础上，为每个节点增加 expire_time = last_access_time + x。

  • Get 时：先判断是否过期，若过期则从缓存中删除并返回不存在；否则更新 last_access_time，移到链表头；
  • Put 时：写入时记录当前时间为 last_access_time；
  • 后台清理：可以维护一个按 expire_time 排序的优先队列（或在 LRU 链中，由于每次访问都刷新时间，过期节点自然会沉到链尾），每次 Get/Put 时捎带清理链尾过期节点；也可以用定时后台线程扫描清理。
struct Node {
    int key, val;
    long long last_access;  // 上次访问时间戳
    // 双向链表指针
};

int get(int key) {
    auto now = current_time_ms();
    if (map.count(key)) {
        auto node = map[key];
        if (now - node->last_access > x) {  // 过期检查
            remove(node);
            map.erase(key);
            return -1;
        }
        node->last_access = now;
        move_to_front(node);
        return node->val;
    }
    return -1;
}

算法2：滑动窗口最大值

窗口从左往右移，求滑过的每个窗口的最大值。

经典解法：单调递减双端队列（Deque），时间复杂度 O(n)：

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;  // 存下标，队头始终是当前窗口最大值的下标
    vector<int> result;
    for (int i = 0; i < nums.size(); i++) {
        // 弹出窗口外的元素
        while (!dq.empty() && dq.front() < i - k + 1)
            dq.pop_front();
        // 维护单调递减：弹出队尾所有比当前元素小的元素
        while (!dq.empty() && nums[dq.back()] < nums[i])
            dq.pop_back();
        dq.push_back(i);
        // 窗口形成后记录结果
        if (i >= k - 1)
            result.push_back(nums[dq.front()]);
    }
    return result;
}

算法3：回文数

给定整数 x，判断是否是回文整数（不允许转字符串，O(1) 空间）。

bool isPalindrome(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)) return false;
    int reversed = 0;
    while (x > reversed) {
        reversed = reversed * 10 + x % 10;
        x /= 10;
    }
    // 奇数位数时 reversed/10 去掉中间那位
    return x == reversed || x == reversed / 10;
}

算法4：找出数组中出现两次的数字（O(n) 时间，O(1) 空间）

数组中数字出现一次或两次，值域 [1, n]，找出所有出现两次的数字。

利用原数组下标做标记（原地哈希）：遍历数组，将 nums[|nums[i]| - 1] 的位置取负号作为访问标记，若该位置已经是负数，说明对应值已出现过一次，即出现了两次：

vector<int> findDuplicates(vector<int>& nums) {
    vector<int> res;
    for (int i = 0; i < nums.size(); i++) {
        int idx = abs(nums[i]) - 1;
        if (nums[idx] < 0)
            res.push_back(idx + 1);  // 已被标记过，出现两次
        else
            nums[idx] = -nums[idx];   // 第一次出现，打标记
    }
    return res;
}

时间 O(n)，空间 O(1)（结果数组不算，原地修改输入数组）。

算法5：搜索旋转排序数组

给定旋转过的有序数组，查找目标值，时间复杂度 O(log n)。

int search(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) return mid;
        if (nums[l] <= nums[mid]) {  // 左半段有序
            if (nums[l] <= target && target < nums[mid])
                r = mid - 1;
            else
                l = mid + 1;
        } else {  // 右半段有序
            if (nums[mid] < target && target <= nums[r])
                l = mid + 1;
            else
                r = mid - 1;
        }
    }
    return -1;
}

算法6：最长重复子串

给定一个字符串，找出其中最长的重复子串（出现至少两次）。

最优解：二分答案 + Rolling Hash，时间复杂度 O(n log n)：

string longestDupSubstring(string s) {
    int n = s.size();
    long long mod = 1e9 + 7, base = 31;
    vector<long long> pw(n + 1, 1);
    for (int i = 1; i <= n; i++) pw[i] = pw[i-1] * base % mod;

    auto check = [&](int len) -> string {
        long long h = 0;
        for (int i = 0; i < len; i++) h = (h * base + s[i]) % mod;
        unordered_map<long long, vector<int>> seen;
        seen[h].push_back(0);
        for (int i = len; i < n; i++) {
            h = (h * base - s[i-len] * pw[len] % mod + s[i] + mod * 2) % mod;
            for (int start : seen[h])
                if (s.substr(start, len) == s.substr(i-len+1, len))
                    return s.substr(start, len);
            seen[h].push_back(i - len + 1);
        }
        return "";
    };

    int lo = 1, hi = n - 1;
    string res = "";
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        string t = check(mid);
        if (!t.empty()) { res = t; lo = mid + 1; }
        else hi = mid - 1;
    }
    return res;
}