메모리 (RAM)에 백만/수십억 개의 레코드 (이름과 정수가 포함 된 레코드로 가정)를 저장하는 데 가장 적합한 데이터 구조는 무엇입니까? 최소 검색 시간 (우선 순위 1 위) 및 메모리 효율 (2 위 우선 순위)의 측면에서 가장 좋습니까? 패트리샤 나무 야? 이보다 더 좋은 점은 없습니까?수십억 개의 정수를 저장하는 데이터 구조
검색 키는 정수입니다 (예 : 32 비트 임의의 정수). 모든 레코드는 RAM에 있습니다 (충분한 RAM을 사용할 수 있다고 가정). C에서
, 플랫폼 리눅스는 ..
는 기본적으로 내 서버 프로그램은 사용자에게 32 비트 임의의 키를 할당하고, 나는/검색 효율적으로 기록을 삭제할 수 있도록 해당 사용자 레코드를 저장할. 데이터 구조가 잘 채워질 것이라고 가정 할 수 있습니다.
에 따라 다릅니다.
이름이나 정수로 검색 하시겠습니까?
이름이 모두 거의 같은 크기입니까?
모든 정수는 32 비트입니까, 아니면 큰 숫자입니까?
메모리에 모두 맞습니까? 그렇지 않다면 디스크 I/O 및 메모리 (또는 디스크 사용)에 의해 제한 될 것입니다. 더 이상 걱정할 필요가 없습니다.
색인 (이름 또는 정수)이 공통 접두사를 갖거나 균일하게 배포됩니까? 공통 프리픽스가있는 경우에만 패트리샤 트리가 유용합니다.
순서대로 색인을 조회하나요 (갱 조회)? 모든 것이 균일하고 무작위이며 공통 접두어가 없다면 해시는 이미 얻을 수있는만큼 좋으며 (이는 나쁘다).
색인이 갱 검색을 사용하는 정수이면 기수 나무를 조사 할 수 있습니다.
많은 문제가 램에 들어갈 수 있습니다. 어제 저는 20K 유로 미만의 96GB 램을 Dell에 구성했습니다. –
데이터가 동적입니까? 삽입/삭제 속도에 우선 순위는 무엇입니까? –
+1 '큰 번호 thingy' – seth
내 추측이있는 B-Tree (하지만 난 ... 틀릴 수도) :
B-나무 상당한 장점을 가지고 노드 액세스 시간이 훨씬 노드에서 액세스를 시간을 초과 대체 구현을 통해. 대개 은 대부분의 노드가 하드 드라이브와 같은 보조 저장소 에있을 때 발생합니다. 각 내부 노드 내의 노드 노드의 수를 최대화하면 트리의 높이가 감소하고 균형 조정이 자주 발생하지 않으며 효율성이 증가합니다. 일반적으로이 값은 각 노드가 전체 디스크 블록을 위로 가져 오거나 보조 저장 장치에 크기를 갖도록 설정됩니다. 2,3 - B- 트리가 메인 메모리에서 유용 할 수 있으며 이 분명히 쉬우 며, 노드 크기가 디스크 블록의 크기에 맞게 조정 된 경우 결과는 257-513 B- 트리 (여기서 크기는 2보다 큰 숫자 인 과 관련이 있습니다).
해시 대신 시작하려면 기수를 사용할 수 있습니다.
특정 문제의 경우 btree, 해시 테이블 또는 patricia trie보다 훨씬 잘 수행 할 수 있습니다. 문제를 좀더 자세히 설명하고 무엇이 효과가 있을지 제안 할 수 있습니다.
정수 키로 검색하려는 경우 간단한 해시 테이블이 가장 빠릅니다. 정수가 연속적 (또는 거의 연속적)하고 고유하다면, (레코드에 대한 포인터의) 간단한 배열이 더 빠릅니다.
해시 테이블을 사용하는 경우 예상되는 최종 크기에 맞게 해시 테이블을 미리 할당하여 다시 해시하지 않아야합니다.
을 사용하거나 뻐꾸기 해시를 시도하십시오? – pageman
이름이나 전화 번호를 찾으십니까? 아니면 둘다? –
레코드 집합이 자주 업데이트되고 얼마나 완전하게 업데이트됩니까? 정수의 분포는 어떻게 생겼습니까? 모든 이름을 가진 해시 테이블을 사용 가능한 메모리에 편안하게 맞출 수 있습니까? – reinierpost