快速，可伸缩的字符串查找

我有一套500万字符串。这些目前存储在单个列MySQL表中。我的应用程序必须执行查找并检查给定的字符串是否在集合中。这当然可以使用HashSet（使用Java）完成。但是，与其构建定制解决方案，我想知道是否有任何现有的，广泛使用的，经过验证的解决方案来实现这一点？这似乎是一种常见的情况。该解决方案应该是可扩展的（该集合可能增加超过5百万），具有故障转移（可能是分布式的）并且在大量请求下运行良好。有什么建议么？快速，可伸缩的字符串查找

更新：我的应用程序还可以查询以检查给定的字符串集是否存在于全局（500万个）集中。

来源

2010-09-29 talonx

也许我不明白你的意思是“执行查找”和“检查给定的字符串是否在集合中” - 是不是这只是SQL选择语句的用途？故障转移和缩放也或多或少是正常的RDBMS功能。 – Sorpigal 2010-09-29 11:20:44

尝试用于快速字符串查找。它们比hashtables/hashset更有效率，并且速度并不慢。 – leppie 2010-09-29 11:23:47

@Sorpigal：是的，但正常的RDBMS查询速度不够快。我还用确切的场景更新了我的问题。希望清除它。 – talonx 2010-09-29 11:50:46

您可以尝试Trie或Patricia-trie。第二个是更多的内存efficient.Also here你可以找到2层数据结构[特里，TreeSet中]，内存数据库和其性能的比较。

来源

2010-09-29 11:35:10 Emil

Trie项目前面的消息并不是很令人鼓舞 - “对于任何访问者来说，这是很好的SAMPLE代码，但不是生产代码，它是在一个晚上由一个没有经验的程序员（我当时是这样写的）。” – talonx 2010-10-10 02:08:59

尽管Trie可能是最好的解决方案，但对已排序的字符串列表进行二分搜索也应该能够很好地运行。

来源

2010-09-29 11:47:03 michid

尝试memcached，一个高性能的分布式内存对象缓存系统。你使用键/值哈希查找。 Facebook uses memcached与许多其他高度可扩展的网站一样。需要存储更多的字符串？只需将更多的memcached实例添加到集群。另外，您可以在第一次查询memcached的2层缓存设置中使用，如果缓存未命中，则可以查询完整数据库。

您是否考虑过将column indexing添加到您的MySQL数据库？支持哈希，B树和R树。

对于高可伸缩性，MySQL也可以是replicated and clustered。

来源

2010-09-29 11:51:54 burkestar

它是如何解决问题的？ – reinierpost 2010-09-29 11:55:04

这是一个用于高效键/值查找的分布式哈希系统。 – burkestar 2010-09-29 11:56:45

快速，可伸缩的字符串查找

回答

相关问题