基于Trie树和Memcached的搜索引擎架构陈如建，李昕（北京邮电大学网络技术研究院，北京100876）51015202530354045摘要：本文介绍一种搜索引擎智能弹出提示字符串的实现方式，着重讨论了如何使用存储在集群中的Trie树和Memcached来实现搜索引擎弹出提示字符串的方法实现。Trie树是一种树形结构，它是基于关键码的空间分解，使用Trie树来存储所有可能的字符串，对用户输入的字符串，利用Trie树来实现快速检索，但当要存储的字符串的数量特别巨大的时候，一台机器是无法存储的，因此本文集群的方式来存储Trie树，即将Trie树中不同的节点存储在集群的不同的机器上。Memecached是一种基于内存对象的缓存系统，它将所有的数据都存在内存中，因此Memcached的存取速度很快，它是基于key-value方式来存储数据的。相比于传统的将数据存储在数据库中，Trie树提高效率，采用集群的方式存储Trie树，这样可以存储数量巨大的字符串。关键词：Memcached；Trie树；集群；搜索引擎中图分类号：TP311SearchenginebasedonTrietreeandMemcachedinChenRujian,LiXin(BeijingUniversityofPostsandTelecommunications,InstituteofNewworkTechnology,Beijing100876)Abstract:Inthispaper，Weintroducearealizationofhowtopop-uppromptStringinasearchengine,ThispaperfocusesonhowtousetheTrietreeandMemcacehdmethodtorealizepopping-uppromptStringsinasearchengine.Trietreeisatreestructure,itisbasedonthespacedecompositionofkeycodes,TrieTreeisusedtostoreallpossiblestrings.Butwhenthenumberofstringswhichneedtostoredishuge,itisinpossibletostrorethesestringsinasignlemachine.Inthispaper,thestringsarestoredinacluster.TheNodeoftheTrietreecouldbesotredindifferentmachinesofthecluster.Memcachedisamemoryobjectcachedbasedsystem,itstorealldatainmemory.Therefore,ithasahighaccess,storedatabasedonthekey-valuemode.Trietreehashighefficiengycomparedtothewaywhichstoringdataindatabasesystem.UsingclustertostoreTrietree,soyoucanstoreabignumberofstringsKeywords:Memcached;Trietree;clusters;searchengine0引言在用户使用搜索引擎的时候，为了提高用户使用的便利性，一般都具有智能提示功能，即在用户敲入一个字符串的时候，会提出一些以这个字符串打头的字符串。这些提示的字符串都是根据以往用户输入搜索字符串汇总而成的。但随着网络技术的发展，使用搜索引擎的用户数量的增多，根据用户已输入的字符串产生的热点字符串也会增多，如何存储这些热点字符串是一个很大的问题。同时随着用户访问搜索引擎网站的人数的增多，如何快速的计算出这些智能提示字符串，也是一个问题。在以往的网站设计中，所有的数据都是存储在数据系统中，但是随着用户访问量的增长，数据库访问速度却成为了提高用户访问量的瓶颈。随着计算机硬件技术的进步，内存的价格也越来越便宜，在这样的背景下，基于内存的数据系统开始走向前台。因此，本文提出一种基于Trie树和Memcached的搜索引擎技术方案。Memcached是一种基于缓存的搜索引擎数据存储方案。与基于数据库的存储方案相比，该方案具有极高的数据读写速度，有效的解决用户量增长造成的搜索引擎访问瓶颈问题。在-1-Memcached中，当用户输入的字符串key已经被其他用户提交过，就会从Memcached中直接得到访问结果，从而加快了检索的速度。Trie[1]树是一种高效的字符串键值检索结构。然而现在的搜索引擎中，通常要存储的热5055点字符串数量巨大，一台低配服务器的内存容量通常不足以支撑整个Trie树结构，为了解决这个问题，本文提出了将Trie树构建在服务器集群上的方案，利用集群[2]的分布式缓存资源来解决Trie树存储问题，该方案能够有效的降低搜索引擎构建成本。1Trie树简介Trie树又称单词查找树、字典树，是一种树形结构（如图1所示）。它的每一个节点都存储了字符串中的一个字符，从根结点到叶子节点的一条路径上的所有节点字符，组合起来就构成了字符串，例如：图1中有字符串，acff，acg，bck等。Trie树的典型应用有：统计单词出现的频数，以频...