基于Trie树和Memcached的搜索引擎架构.doc

文档介绍：
基于 Trie 树和 Memcached 的搜索引擎架构
陈如建,李昕
(北京邮电大学网络技术研究院,北京 100876)
5
10
15
20
25
30
35
40
45
摘要:本文介绍一种搜索引擎智能弹出提示字符串的实现方式,着重讨论了如何使用存储在
集群中的 Trie 树和 Memcached 来实现搜索引擎弹出提示字符串的方法实现。Trie 树是一种
树形结构,它是基于关键码的空间分解,使用 Trie 树来存储所有可能的字符串,对用户输
入的字符串,利用 Trie 树来实现快速检索,但当要存储的字符串的数量特别巨大的时候,
一台机器是无法存储的,因此本文集群的方式来存储 Trie 树,即将 Trie 树中不同的节点存
储在集群的不同的机器上。Memecached 是一种基于内存对象的缓存系统,它将所有的数据
都存在内存中,因此 Memcached 的存取速度很快,它是基于 key-value 方式来存储数据的。
相比于传统的将数据存储在数据库中,Trie 树提高效率,采用集群的方式存储 Trie 树,这
样可以存储数量巨大的字符串。
关键词:Memcached;Trie 树;集群;搜索引擎
中图分类号:TP311
Search engine based on Trie tree and Memcached in
Chen Rujian, Li Xin
(Beijing University of Posts and munications,Institute of Newwork Technology,Beijing
100876)
Abstract: In this paper,We introduce a realization of how to pop-up prompt String in a search engine,
This paper focuses on how to use the Trie tree and Memcacehd method to realize popping-up prompt
Strings in a search engine. Trie tree is a tree structure, it is based on the space position of key
codes, Trie Tree is used to store all possible strings. But when the number of strings which need to
stored is huge, it is inpossible to strore these strings in a signle machine. In this paper, the strings are
stored in a cluster. The Node of the Trie tree could be sotred in different machines of the cluster.
Memcached is a memory object cached based system, it store all data in