엄청난 양의 고유 한 문자열을 저장하는 가장 빠른 방법은 무엇입니까?

Question

엄청난 양의 문자열을 저장하고 중복을 검사하는 가장 좋은 방법은 무엇일까?이

랜덤 액세스 시간은 무엇입니까

• 중복 검사 속도
• 삽입 새 문자열 시간
• 저장 공간이 하드 디스크 :

  우리는 우리의 우선 순위에 대해 생각해야 우리의 목표가 빠른 중복 검사 및 새로운 문자열 삽입 시간 (임의 액세스 또는 저장 공간 없음) 인 경우 최상의 솔루션 e matter)? SQL 데이터베이스에 대해 생각하지만 DB 중 어떤 것이이 솔루션에 가장 적합한가요? MySQL과 같은 SQL DB를 사용한다면 어떤 스토리지 엔진이 가장 좋을까요? (물론 데이터 양 때문에 메모리를 제외해야합니다)

Answer 1

입력 문자열에 해시 함수를 사용하십시오. 출력 해시는 레코드의 기본 키/id가됩니다.

DB를이 해시/ID/기본 키가있는 경우 그럼 당신은 확인할 수 있습니다

• 가 나던 경우 :이 새로운 문자열을; 문자열과 해시를 포함하는 새 레코드를 id로 추가합니다.
• 해당되는 경우 :로드 된 레코드의 문자열이 입력 문자열과 같은지 확인하십시오.
  • 문자열이 동일한 경우 : 문자열이 다른 경우 중복 됨
  • : 충돌입니다. 해결하려면 collision resolution 체계를 사용하십시오. (아래의 예를 몇)

당신은 속도에 따라 문자열 및 해시 충돌 요구 사항/보증의 수를 예상 사용하려면 어떤 해시 함수/계획/강도 고려해야 할 것이다.

방법의 몇 해결하기 위해 충돌 :

• 은 같은 테이블에 새 해시을 마련하기 위해 2 해시 함수를 사용합니다.
• 레코드를 (예 : NULL으로) 표시하고 보조 '충돌'테이블에서 더 강력한 두 번째 해시 함수 (더 넓은 도메인 사용)로 반복합니다. 쿼리에서 문자열이 충돌 한 것으로 표시되면 (예 : NULL) 충돌 테이블에서 다시 조회를 수행합니다. 이 두 번째 테이블에 추가 충돌이 발생하지 않도록 dynamic perfect hashing을 사용할 수도 있습니다.

물론 얼마나 지속성이 필요하고 얼마나 많은 메모리를 차지할 것으로 예상하는지/문자열의 수에 따라 데이터베이스를 사용하지 않고 직접 메모리에서 직접 수행 할 수 있습니다. .

Answer 2

문자열을 저장하기위한 접미어 트리를 생성하십시오. http://www.daimi.au.dk/~mailund/slides/Ukkonen-2005.pdf의 Ukkonen 알고리즘은 접미어 트리를 만드는 방법에 대한 통찰력을 제공합니다.이 접미사 트리를 저장하는 방법은 다양합니다. 하지만 일단 생성되면 검색 시간이 매우 낮습니다.

Answer 3

당신은없는 NoSQL 솔루션을 고려할 수 있습니다 :

Redis합니다. 이용 케이스의 일부 레디 스를 사용하여 해결 :

• http://highscalability.com/blog/2011/7/6/11-common-web-use-cases-solved-in-redis.html
• http://dr-josiah.blogspot.com/2011/02/some-redis-use-cases.html 는
• http://www.paperplanes.de/2010/2/16/a_collection_of_redis_use_cases.html

memcached (시아 L. 칼슨 Redis in Action의 저자). memcached를하고 레디 스 사이의 일부 비교 : one of their success stories로 OMGPOP의 그리기 뭔가를 계산

• http://www.quora.com/What-are-the-differences-between-memcached-and-redis
• Is memcached a dinosaur in comparison to Redis?
• http://coder.cl/2011/06/concurrency-in-redis-and-memcache/

Membase/Couchbase. 레디 스 및 Membase의 비교 :

• What is the major difference between Redis and Membase?
• http://kkovacs.eu/cassandra-vs-mongodb-vs-couchdb-vs-redis

몇 가지 질문 :

• 문자열의 집합이 얼마나 큰
  ?
• 응용 프로그램이 무거운 읽거나 무거운 쓸 것입니까? 아니면 둘다?
• 얼마나 자주 데이터를 디스크에 저장 하시겠습니까?
• 거기에 가장 최근의 문자열이 필요합니까?

희망이 도움이됩니다.