自动完成服务器端实现
在html输入框中为自动完成function实现服务器端组件的快速有效方法是什么？
我正在编写一个服务，在我们的Web界面的主搜索框中自动完成用户查询，完成显示在ajax驱动的下拉列表中。 我们运行查询的数据只是我们系统知道的大型概念表，大致与维基百科页面标题集相匹配。 对于这项服务，显然速度至关重要，因为网页的响应性对用户体验很重要。
当前实现只是将所有概念加载到有序集合中的内存中，并对用户击键执行简单的log（n）查找。 然后使用尾部提供超出最接近匹配的额外匹配。 该解决方案的问题在于它无法扩展。 它目前正在运行虚拟机堆空间限制（我已设置-Xmx2g，这是我们可以在我们的32位计算机上推送的最多），这阻止我们扩展我们的概念表或添加更多function。 在具有更多内存的计算机上切换到64位VM不是一个直接的选择。
我一直犹豫是否开始研究基于磁盘的解决方案，因为我担心磁盘搜索时间会影响性能。 有没有可能的解决方案可以让我更好地扩展，无论是完全在内存中还是在一些快速磁盘支持的实现中？
编辑：
@Gandalf：对于我们的用例，重要的是自动完成是全面的，而不仅仅是对用户的额外帮助。 至于我们正在完成的内容，它是概念类型对的列表。 例如，可能的条目是[（“Microsoft”，“Software Company”），（“Jeff Atwood”，“Programmer”），（“StackOverflow.com”，“Website”）]。 一旦用户从自动完成列表中选择一个项目，我们就会使用Lucene进行完整搜索，但我还不确定Lucene是否可以自动完成自动完成。
@Glen：这里没有使用数据库。 当我在谈论桌子时，我只是指我的数据的结构化表示。
@Jason Day：我对这个问题的原始实现是使用Trie ，但由于需要大量的对象引用，因此内存膨胀实际上比排序集更差。 我将阅读三元搜索树，看它是否有用。
使用一个大的集合，我会尝试像Lucene索引一样找到你想要的术语，并设置一个在每次击键后重置的计时器任务，延迟为.5秒。 这样，如果用户快速键入多个字符，则只有当用户暂停一秒钟时，才会在每个笔划中查询索引。 可用性测试将让您知道该暂停应该有多长。
Timer findQuery = new Timer(); ... public void keyStrokeDetected(..) { findQuery.cancel(); findQuery = new Timer(); String text = widget.getEnteredText(); final TimerTask task = new TimerTask() { public void run() { ...query Lucene Index for matches } }; findQuery.schedule(task, 350); //350 ms delay } 一些pseduocode那里，但这是主意。 此外，如果设置了查询术语，则可以预先创建和优化Lucene索引。
我有类似的要求。
我使用关系数据库和一个索引良好的合成表（避免连接和视图来加速查找），以及内存缓存（Ehcache）来存储最常用的条目。
通过使用MRU缓存，您将能够获得大多数查找的即时响应时间，并且在访问存储在磁盘上的大表中的索引列时，可能无法击败关系数据库。
这是您无法存储在客户端上的大数据集的解决方案，并且它的工作速度非常快（在我的情况下，总是在0.5秒内检索非缓存查找）。 它还可以横向扩展 – 您可以随时添加其他服务器和数据库服务器。
您还可以在客户端上缓存最常用的结果，特别是如果您已经实现了它。 就我而言，服务器端解决方案足够快，并且客户端加载时间足够慢，因此不能保证。
PS仅在用户暂停一定时间以避免重复查找时才进行客户端查询是一个很好的解决方案。 在我的客户端上，我只在输入前三个字符后才查询数据库，因为少于该值会在所有实例中返回太多结果。
对于那些偶然发现这个问题的人……
我刚刚在Google Code上发布了服务器端自动完成实现 。 该项目包括一个可以集成到现有应用程序的Java库和一个独立的HTTP AJAX自动完成服务器。
我希望能够让人们将高效的自动完成function整合到他们的应用程序中。 踢轮胎！
我最终通过Lucene解决了这个问题。 初始性能测试似乎足以满足我们的用例。 为了使前缀查询有效，需要进行一些小的黑客操作，因为在扩展诸如“Jeff At *”之类的查询时，我遇到了TooManyClausesexception。 我最终用FilterIndexReader包装我的IndexReader，并对前缀术语调用返回的术语数量设置硬限制。 这是我的代码：
Directory directory = FSDirectory.getDirectory(indexDir); IndexReader reader = IndexReader.open(directory); FilterIndexReader filteredReader = new FilterIndexReader(reader) { @Override public TermEnum terms(Term t) throws IOException { final TermEnum origEnum = super.terms(t); return new TermEnum() { protected int count = 0; @Override public boolean next() throws IOException { if (count++ < (BooleanQuery.getMaxClauseCount() - 10)) return origEnum.next(); else return false; } @Override public Term term() { return origEnum.term(); } @Override public int docFreq() { return origEnum.docFreq(); } @Override public void close() throws IOException { origEnum.close(); } }; } }; IndexSearcher searcher = new IndexSearcher(filteredReader);
我使用三元搜索树为小数据集做了这个。 DDJ代码转换为Java并不太难，但它假设整个数据集适合内存。 有三元搜索树的磁盘实现（ 这里是python中的一个），但当然它们的性能会降低。 但是，由于三元搜索树在部分匹配方面表现优异，因此性能可能适合您的需求。
我使用hashtable和mmap（）而10,000,000+记录术语列表不是问题。 请参阅此处的演示： http ： //olegh.ath.cx/autocomplete.html
在这里使用trie数据结构是wiki http://en.wikipedia.org/wiki/Trie
如果您无法将所有数据物理加载到RAM中，那么您将不得不处理磁盘上的某些数据。
你用的是什么数据库？
例如，Oracle有一个选项，您可以将整个表保留在内存中，并针对该表执行查询。
MySQL也声称拥有一些内存function，但我对MySQL知之甚少。
然后，您可以取消基于Java的缓存，或者可以将缓存用于最常用/最近的搜索。
显然当你用完RAM时，当你查询它时，一些数据会在磁盘上，但是根据系统上的负载，这只会是第一个按键的问题，而不是后续的按键，如行在此之后将会在记忆中。
如果磁盘搜索速度降低，那么您可以调查使用SSD驱动器来加快读取速度。
也许我误解了你的问题，但你不能使用JQuery插件将Ajax信息发送到你的应用程序？
我以前用过这个：
Ajax Auto Suggest v2
是否有可能让我更好地扩展的解决方案
是的，Oracle。 这是为数据库构建的东西。 只需索引相关列。 如果您在内存解决方案的墙上运行，那么与磁盘寻道时间或网络延迟的权衡可能没有实际意义。 特别是如果在其间插入缓存层。
此外，如果稍微调整客户端代码，您可以减少命中数。 例如在运行查询之前设置最小数量的字符数，或者在用户停止键入后设置延迟的一小部分。 如果您已经在使用它们，请将它们设置得更高一些。