주문 파일을 디스크에 확장하기위한 전략

Question

현재 데이터 분석 프로그램을 연구중인 핵 물리학 대학원생입니다. 데이터는 수십억 개의 다차원 점으로 구성됩니다.

어쨌든 여러 차원을 단일 차원에 매핑하는 공간 채우기 곡선을 사용하고 B + 트리를 사용하여 데이터 페이지를 인덱싱합니다. 각 페이지에는 그 안에 일정한 최대 점 수가 있습니다.

원시 파일 (수 백 기가)을 원본 파일에서 읽고 전처리하고 색인화하면 개별 지점을 페이지에 삽입해야합니다. 분명히 너무 많은 페이지가 메모리에 저장되고 디스크에 덤프됩니다. 그래서 제 질문은 다음과 같습니다. 페이지를 디스크에 쓰는 것이 좋은 전략인데 페이지가 최대 크기에 도달하여 분할해야 할 때 데이터를 최소한으로 재구성해야합니다.

의견을 바탕으로 조금 줄일 수 있습니다.

주문한 레코드가 포함될 파일이 있습니다. 이러한 레코드가 파일에 삽입되고 있으며이 레코드가 너무 많아 메모리에서이 작업을 수행 한 다음 파일에 기록하기 만하면됩니다. 기록을 삽입 할 때 필요한 재편성의 양을 최소화하기 위해 어떤 전략을 사용해야합니까?

이것이 의미가있는 경우이 솔루션에 대한 의견을 보내 주시면 감사하겠습니다.

편집 :
데이터는 다차원 공간의 포인트입니다. 기본적으로 정수 목록입니다. 이 정수는 각각 2 바이트이지만 각 정수에는 추가 2 바이트의 메타 데이터가 연관되어 있습니다. 따라서 좌표 당 4 바이트 및 3에서 20 사이의 좌표. 그래서 본질적으로 데이터는 12 ~ 100 바이트 사이의 각 청크의 수십억 개의 청크로 구성됩니다. (분명히 4 차원이 추출되면 5 차원을 가진 점과 다른 파일에 위치하게됩니다).

나는이 문서에서 설명하는 것과 유사한 기술을 사용하고 있습니다 : http://www.ddj.com/184410998

편집 2 : 나는 좀 그래서 공식적으로 폐지 고려 여기에이 질문을 후회 을; 그러나 선반 제품을 사용하지 않는 이유가 여기 있습니다. 내 데이터는 3 차원에서 22 차원까지의 범위를 지닌 포인트입니다. 각 포인트를 단순한리스트로 생각하면 포인트를 쿼리하려는 방법을 생각할 수 있습니다.이 숫자와 같은리스트에있는 모든 숫자는 무엇입니까? 아래 저 차원 (통상보다 많은 적은 데이터 지점)과 몇 가지 예 예 : 데이터 237, 661, 511, 1,047 1,021, 661, 237 511, 237, 1,021 511, 661, 1,047, 1,021

Queries: 
511 
1021 
237, 661 
1021, 1047 
511, 237, 1047 

Responses: 
237, 661, 1021, 237, 1021, 661, 1047, 1021 
237, 661, 511, 511, 237, 511, 661, 1047 
511, 1021, 1047 
511, 661 
_ 

대부분의 데이터베이스 프로그램에서이 문제는 거의 해결할 수 없지만 잘 처리 할 수있는 일부 기능은 알고 있습니다.

하지만 문제는 더욱 복잡해집니다. 모든 좌표가 동일하지는 않습니다. 여러 번 우리는 단지 gammasphere 만 실행하므로 각 좌표는 감마선 에너지를 나타냅니다. 그러나 다른 시간에 우리는 gammasphere 나 microball이라는 검출기 시스템에 중성자 검출기를 삽입하거나, 때때로 gammasphere에서 생성 된 핵종을 fragment mass analyzer로 보내고 모든 검출기 시스템은 단독으로 또는 gammasphere와 결합하여 사용할 수 있습니다. 불행히도 우리는 거의 항상 위에서 설명한 것과 비슷한 방식으로이 추가 데이터를 선택할 수 있기를 원합니다.그래서 좌표는 다른 의미를 가질 수 있습니다. 만약 gammasphere 이외에 microball을 가지고 있다면 방정식 x + y = n에 대한 긍정적 인 해답이있는만큼 많은 방법으로 n 차원 이벤트를 만들 수 있습니다. 또한 각 좌표에는 이와 관련된 메타 데이터가 있습니다. 그래서 내가 보여준 수는 각각 적어도 2 개의 추가 숫자를 가지게됩니다. 첫 번째는 감지기 번호, 두 번째는 효과 값을 나타냅니다. 특정 감마선의 횟수를 나타냅니다. (실제로 감지되는 감마선의 비율이 감지기 및 에너지에 따라 달라 지므로) 카운트합니다.

저는 선반 데이터베이스 솔루션에서 벗어난 모든 것들이 엄청난 양의 커스터마이징없이 이러한 모든 작업을 수행 할 수 있으며 동시에 성능이 우수하다는 점을 진심으로 의심합니다. 나는 그 시간을 보냈다는 것이 내 자신의, 훨씬 덜 일반적인 해결책을 쓰는 것이 더 낫다고 믿는다. 일반성의 상실로 인해 databasing 코드에 대해 delete 함수를 구현할 필요가 없기 때문에 여러 유형의 좌표 (단지 한 세트 만 효과적으로 각 포인트를 한 번만 계산)에 게이트를 만들 필요가 없습니다.

Answer 1

나는 스스로 대답을 내놓았다. 페이지를 분할해야 할 때 이벤트가 페이지에 삽입됨에 따라 새 페이지가 파일의 끝에 작성됩니다. 원본 페이지의 이벤트 중 절반이 해당 페이지로 이동됩니다. 이렇게하면 페이지가 정렬되지 않아서 빠른 검색 메커니즘을 다소 손상시킬 수 있습니다.

그러나 나는 단지 하나의 커다란 초기 러시 (아마도 며칠 지속)로 글을 쓰기 때문에 쓰기가 끝난 후 약간의 시간을 소비하여 페이지를 거치고 모든 것이 만들어지면 정렬 할 수 있다고 정당화 할 수 있습니다. 이 부분은 페이지를 색인화하는 데 사용되는 B + 트리의 특성 때문에 실제로 매우 쉽습니다. 간단히 B + 트리의 가장 왼쪽의 리프 노드에서 시작하여 첫 번째 페이지를 읽고 마지막 파일에 첫 번째 파일을 넣은 다음 두 번째 페이지를 읽고 두 번째 페이지를 읽는 등의 작업을 수행합니다.

삽입의 마지막에 모든 페이지가 파일 내에서 정렬되므로 다차원 요청을 다차원 인덱스로 매핑하여 디스크에서 데이터를 읽을 때 효율적이고 신속하게 작업 할 수 있습니다.

Answer 2

그래서 첫 번째 측면은 스레드 응용 프로그램에서이를 수행하여 더 빠르게 처리하는 것입니다. 데이터 덩어리를 실행할 수있는 섹션으로 나누십시오. 어떤 생각이 들게합니까?

처음에는 Lucene을 사용하는 것이 좋습니다 ...하지만이 생각은 실제로는 Hadoop으로 처리해야합니다. 그것은 이런 종류의 일을 위해 만들어졌습니다 (여러분이 인프라를 가지고 있다고 가정).

나는 확실히 데이터베이스에서 이것을하지 않을 것이다.

데이터를 인덱싱하고 데이터 포인트로 문서를 채우는 중 ... 인프라가 없거나 hadoop을 구현하는 방법이나 시간을 알고 있다면 원래의 생각으로 돌아가서 Lucene을 사용해야합니다. . 데이터를 실제로 그런 식으로 인덱싱하고 데이터 포인트를 "문서"(개체) 구조로 인덱스에 직접 저장할 수 있습니다 (생각하는 숫자 범위로).

Answer 3

나는 상용 및 무료 데이터베이스가 제공해야하는 것을 먼저 봐야한다고 생각한다. 이 솔루션은 빠른 범위 검색 (올바른 색인 제공)을 수행하고 메모리를 효율적으로 관리하고 페이지를 디스크에 읽고 쓰도록 설계되었습니다.

이진 파일 Space Partition (BSP)의 변형을 살펴보십시오.