基于Trie字典树实现搜索下拉提示

搜索下拉联想提示是 App 与网站的标准配置功能。本文分享基于 Trie 字典树的完整解决方案，涵盖核心原理、离线构建架构及前端防抖交互，可直接应用于生产环境。

Trie 字典树核心原理

Trie（前缀树）是一种按字符存储、共享公共前缀的多叉树结构。所有拥有相同前缀的搜索词会复用树上的同一串路径，极适合处理「前缀匹配」与「自动补全」场景。

根节点
 └── 苹
     └── 果（完整词：苹果）
         ├── 手
         │   └── 机（完整词：苹果手机）
         └── 电
             └── 脑（完整词：苹果电脑）

原生 Trie 存在致命缺陷：查询需递归遍历所有子节点，当词库量大时性能急剧下降。本方案摒弃了「查询时遍历子树、实时排序」的低效逻辑，采用「空间换时间、预计算前置」的核心思路：

• 预缓存机制：在每个 Trie 节点中，额外缓存当前前缀下热度排名最高的 TopN 搜索词。
• 离线构建：在插入搜索词阶段，词语途经的每一个前缀节点自动完成新增、去重、热度排序及数量截断，提前生成最优候选榜单。
• 线上查询：用户查询时仅需匹配前缀路径，直接读取节点预缓存的榜单数据，无需递归遍历子树或实时排序。

优化后，查询时间复杂度稳定为 O(输入字符长度)，性能与全局词库总量及前缀下子节点数量完全解耦。

核心代码实现

以下代码实现了词语插入、热度排序、前缀联想、自动去重及 Top 截断功能。

<?php
/**
 * Trie 树节点
 */
class TrieNode
{
    // 子节点集合
    public array $children = [];
    // 是否为完整词语结尾
    public bool $isEnd = false;
    // 完整搜索词
    public ?string $word = null;
    // 搜索热度
    public int $hot = 0;
    // 核心：当前前缀下热度最高的候选词列表
    public array $topWords = [];

    public function updateTopWords(string $word, int $hot, int $limit = 10): void
    {
        // 去重
        foreach ($this->topWords as $k => $item) {
            if ($item['word'] === $word) {
                unset($this->topWords[$k]);
            }
        }
        $this->topWords[] = ['word' => $word, 'hot' => $hot];
        // 热度降序排序
        usort($this->topWords, function ($a, $b) {
            return $b['hot'] - $a['hot'];
        });
        // 只保留 TopN
        $this->topWords = array_slice($this->topWords, 0, $limit);
    }
}

/**
 * 搜索提示 Trie 字典树
 */
class SearchSuggestTrie
{
    private TrieNode $root;
    private int $topLimit;

    public function __construct(int $topLimit = 10)
    {
        $this->root = new TrieNode();
        $this->topLimit = $topLimit;
    }

    // 插入搜索词与热度
    public function insert(string $word, int $hot): void
    {
        $node = $this->root;
        $len = mb_strlen($word);
        for ($i = 0; $i < $len; $i++) {
            $char = mb_substr($word, $i, 1);
            if (!isset($node->children[$char])) {
                $node->children[$char] = new TrieNode();
            }
            $node = $node->children[$char];
            // 每一层前缀节点都更新候选词缓存
            $node->updateTopWords($word, $hot, $this->topLimit);
        }
        $node->isEnd = true;
        $node->word = $word;
        $node->hot = $hot;
    }

    // 根据前缀获取联想词
    public function suggest(string $prefix): array
    {
        $node = $this->root;
        $len = mb_strlen($prefix);
        for ($i = 0; $i < $len; $i++) {
            $char = mb_substr($prefix, $i, 1);
            if (!isset($node->children[$char])) {
                return [];
            }
            $node = $node->children[$char];
        }
        return array_column($node->topWords, 'word');
    }
}

// 测试演示
$trie = new SearchSuggestTrie(8);
$list = [
    ['word' => '苹果手机', 'hot' => 9980],
    ['word' => '苹果 16', 'hot' => 8600],
    ['word' => '苹果电脑', 'hot' => 7200],
    ['word' => '苹果耳机', 'hot' => 6100],
    ['word' => '华为手机', 'hot' => 9200],
];
foreach ($list as $item) {
    $trie->insert($item['word'], $item['hot']);
}
var_dump($trie->suggest("苹果"));
?>

离线构建 CLI 脚本

通过定时任务从词库读取数据，全量构建 Trie 树，并序列化缓存至 Redis 与本地文件，实现读写分离。

<?php
namespace app\command;
use think\console\Command;
use think\console\Input;
use think\console\Output;
use think\facade\Db;
use think\facade\Redis;

class BuildSuggestTrie extends Command
{
    protected function configure()
    {
        $this->setName('build:suggest-trie')
             ->setDescription('离线构建搜索提示 Trie 字典树');
    }

    protected function execute(Input $input, Output $output)
    {
        $output->writeln("开始构建 Trie 词库...");
        $trie = new \SearchSuggestTrie(10);
        
        // 从关键词数据表读取词 + 热度
        $rows = Db::table('search_keyword')
            ->where('hot', '>', 0)
            ->limit(100000)
            ->select()
            ->toArray();

        foreach ($rows as $row) {
            $word = trim($row['keyword']);
            $hot = (int)$row['hot'];
            if (!empty($word)) {
                $trie->insert($word, $hot);
            }
        }

        // 序列化存入 Redis
        $data = serialize($trie);
        Redis::set('suggest_trie_data', $data);
        Redis::expire('suggest_trie_data', 86400 * 7);
        
        // 本地文件降级备份
        file_put_contents(runtime_path() . 'suggest_trie.cache', $data);
        
        $output->writeln("✅ 字典树构建完成并缓存");
        return 0;
    }
}

定时任务配置

配置每两小时自动更新一次热搜词库：

0 */2 * * * cd /你的项目 && php think build:suggest-trie >> runtime/trie.log 2>&1

线上查询接口

接口优先读取 Redis 缓存，若失败则降级读取本地文件，确保服务高可用。

public function suggest()
{
    $prefix = trim(input('get.prefix',''));
    if (mb_strlen($prefix) < 1) {
        return json([]);
    }
    
    // 优先读 Redis，失败降级读本地文件
    $cache = Redis::get('suggest_trie_data');
    if (!$cache) {
        $cache = file_get_contents(runtime_path() . 'suggest_trie.cache');
    }
    
    $trie = unserialize($cache);
    return json($trie->suggest($prefix));
}

前端防抖交互

为解决连续输入导致的频繁请求问题，前端采用 300ms 防抖策略，提升用户体验。注意：中文处理必须使用 mb_substr，禁止使用原生字符串下标截取以防乱码。

<input type="text" id="search-input" placeholder="输入搜索" style="width:300px;padding:8px;">
<ul id="suggest-box" style="list-style:none;padding:0;margin:5px 0 0;display:none;border:1px solid #eee;"></ul>
<script>
const input = document.getElementById('search-input');
const box = document.getElementById('suggest-box');

// 防抖函数
function debounce(fn, delay = 300) {
    let t = null;
    return function(...args){
        clearTimeout(t);
        t = setTimeout(()=>fn.apply(this,args), delay);
    }
}

// 请求联想词
async function getSuggest(prefix){
    if(!prefix){
        box.style.display = 'none';
        return;
    }
    const res = await fetch(`/search/suggest?prefix=${encodeURIComponent(prefix)}`);
    const list = await res.json();
    render(list);
}

// 渲染下拉列表
function render(list){
    if(!list || !list.length){
        box.style.display = 'none';
        return;
    }
    box.innerHTML = '';
    list.forEach(word=>{
        let li = document.createElement('li');
        li.innerText = word;
        li.style.padding = '6px 10px';
        li.style.cursor = 'pointer';
        li.onclick = ()=>{
            input.value = word;
            box.style.display = 'none';
        };
        box.appendChild(li);
    });
    box.style.display = 'block';
}

input.addEventListener('input', debounce(e=>{
    getSuggest(e.target.value.trim());
}));

input.addEventListener('blur', ()=>{
    setTimeout(()=>box.style.display='none',200);
});
</script>

架构总结

• 构建与查询分离：构建过程走离线定时任务，线上接口仅负责只读查询。
• 节点预存 Top 热度词：这是 Trie 树能支撑线上高并发查询的关键优化点。
• 双缓存降级策略：采用 Redis + 本地文件双重保障，确保服务极端情况下不宕机。