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

我有一套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

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

回答

相關問題