題幹與適用場景
實作 ART 保存可變長度位元組鍵和值，支援插入、精確查找、最長前綴匹配與刪除。節點按孩子數在 Node4、16、48、256 間自適應，路徑壓縮不可改變鍵語義。核心考察壓縮樹與記憶體配置，歸為 coding。
面試官考察點
- 處理壓縮路徑、鍵結束標記與任意位元組。
- 正確維護四種節點升級和降級。
- 實作最長前綴並區分精確命中與祖先值。
- 證明刪除不會留下空節點。
- 說明複雜度、記憶體和並發策略。
回答前需要釐清的問題
- 鍵是否可包含零位元組？
- 內部節點能否存值？
- 最長前綴要回傳什麼長度？
- 刪除後立即收縮還是延遲回收？
- 是否需要無鎖讀或快照？
30 秒回答框架
「我按位元組比較鍵，內部節點保存壓縮前綴和終止值。孩子少用 Node4/16，增多升級 Node48/256，刪除後按閾值降級並合併單孩子路徑。最長前綴匹配記錄最近帶值節點。先驗證單執行緒不變量，再討論鎖或不可變快照。」
分步驟深入解答
第一步：定義節點
內部節點保存壓縮前綴、長度、是否有值與孩子；葉子保存完整鍵。前綴長度獨立於終止符，因為鍵可為任意位元組。
第二步：插入與分裂
比較節點前綴與剩餘鍵。部分匹配時建立公共前綴父節點，依分歧位元組掛載舊節點和新葉子；若新鍵在公共前綴結束，父節點設值。
第三步：自適應布局
Node4/16 保存緊湊鍵與指標陣列；Node48 用 256 位元組映射到 48 個槽位；Node256 直接按位元組索引。升級複製孩子時不能丟值或前綴。
第四步：查找與最長前綴
精確查找必須消費完整鍵並命中值。最長前綴每次通過前綴後記錄帶值節點，再沿下一位元組前進，失敗時回傳最近候選。
第五步：刪除與收縮
刪值後無孩子就移除；無值且只剩一個孩子可合併前綴。四種節點按孩子數降級，合併時保留葉子完整鍵。
第六步：不變量與複雜度
根到葉拼接必須等於原鍵，內部節點邊位元組不可重複，hasValue 表示鍵在此結束。查找 O(L)，記憶體避免稀疏節點固定 256 槽位。
第七步：測試與並發
以 Map 對照隨機操作，覆蓋空鍵、零位元組、前綴鍵和全分支。並發先用讀寫鎖，再考慮 copy-on-write、epoch 或 RCU，不能在未解決回收前使用裸指標。
高品質示範回答
「我把鍵視為任意位元組串，節點保存壓縮前綴、終止值和孩子。部分匹配拆出公共前綴；孩子跨閾值在 Node4、16、48、256 間升級，刪除反向降級並合併單孩子。精確查找消費完整鍵，最長前綴記錄最近帶值節點。測試以 Map 對照並覆蓋零位元組、空鍵和前綴鍵，無鎖讀需搭配安全回收。」
常見錯誤
- 按字元處理 → 非文字鍵失敗 → 按位元組比較。
- 忘記內部值 → 前綴鍵無法命中 → 保留
hasValue。 - Node48 配 256 指標 → 浪費記憶體 → 用映射槽位。
- 刪除不合併 → 空節點堆積 → 按閾值收縮。
- 無鎖裸指標 → 回收後使用釋放記憶體 → 先用鎖或 epoch。
追問及應對
追問一：為何不總用 Node256？
多數節點稀疏，256 槽位浪費記憶體；自適應布局更平衡。
追問二：鍵是另一鍵前綴怎麼辦？
在內部節點保存值並繼續保留更長鍵孩子。
追問三：何時合併？
無值且只有一個孩子時合併前綴與邊位元組。
追問四：如何支援並發快照？
copy-on-write 發布新根，epoch 或引用計數延遲回收舊樹。