디스크 btrees의 아키텍처를 가장 잘 이해 한 것은 this입니다.on-disk 데이터 구조의 구조
아주 간단하고 이해하기 쉽습니다. 그러나 나는 여전히 혼란 스럽다. 메모리 데이터 구조가 전혀없는 것 같지 않습니다. 내가 놓친 게 있니? 이것을 btree로 만드는 것은 무엇입니까? 자식 노드의 키를 "가리키는"long 배열입니까? 그렇게 효율적입니까? 대부분의 데이터베이스와 파일 시스템이 설계된 방식일까요?
메모리에 디스크 btree (또는 다른 데이터 구조)를 구현하는 방법이 있습니까? 각 노드에는 파일 오프셋 또는 무언가가 포함되어 있습니까?
노드 포인터는 일반적으로 디스크에 주소로 저장됩니다 (예 : long 정수 사용). 일반적으로 구현에서
는 물리적 또는 논리적 중 주소를 사용하도록 선택합니다실제 주소 지정이 더 빠릅니다 (해결 메커니즘이 필요하지 않으므로). 그러나 논리적 주소 지정을 사용하면 포인터를 다시 쓰지 않아도 노드를 재구성 할 수 있습니다. 이러한 방식으로 노드를 재구성 할 수있는 능력은 우수한 클러스터링, 공간 활용 및 낮은 수준의 데이터 배포를 구현하기위한 기초로 사용할 수 있습니다.
일부 구현은 논리적 및 물리적 주소 지정의 조합을 사용하여 각 주소가 세그먼트 (BLOB) 및 해당 세그먼트 내의 물리적 주소를 참조하는 논리 주소로 구성됩니다.
노드 주소는 디스크 기반이므로 메모리 내 포인터로 직접 변환 할 수 없다는 점에 유의해야합니다.
데이터가 메모리로로드 될 때 디스크 기반 포인터를 메모리 포인터로 변환 한 다음 쓰기 작업을 수행 할 때 디스크 기반 포인터로 다시 변환하는 것이 유리한 경우도 있습니다.
이 변환은 포인터 스위 즐링이라고도하며 여러 가지 방법으로 구현 될 수 있습니다. 기본적인 생각은 에 의해 어드레싱 된 데이터가 포인터가 네비 게이팅/트래버스되기 전에 메모리에로드되지 않아야한다는 것입니다.
일반적인 접근 방식은 논리적 인 메모리 주소 지정 체계를 사용하거나 메모리 매핑 된 파일을 사용하는 것입니다. 메모리 매핑 된 파일은 메모리 페이지가 액세스되기 전에 메모리에로드되지 않는 가상 메모리 주소 지정을 사용합니다. 가상 메모리 매핑 파일은 OS에서 제공합니다. 이 접근 방식은 때로는 페이지 주소가 인 메모리로 매핑되지 않은 메모리 페이지의 데이터에 액세스하면 페이지 오류이 (가) 인터럽트되기 때문에 폴트 된 주소라고도합니다.
어떤 메모리 내 데이터 구조가 필요합니까? 디스크상의 b-tree는 그것을 사용하는 프로세스보다 오래 남아 있어야합니다.; 인 메모리 트리는 디스크상의 것과 같습니다 (작은 차이를 제외하고는 큰 차이점이 있습니다). – usr
@usr 디스크 데이터 구조가 어떻게 구현되는지 혼란스러워합니다. 노드는 어떻게 자신의 자식 노드를 가리 킵니까?그들은 오프셋에 대한 참조를 보유하고 있습니까? 그들의 열쇠? 일반적으로 단일 트리가 단일 파일로 유지됩니까? – alf