B + 트리 구현, * * vs *

Question

여러 가지 이유로 B + 트리를 작성 중이며 노드 구현에 대해 질문하고 있습니다. 내 현재의 구현 * 사용하고 볼 수있는 것처럼 내가 * * 또는 * 사용할지 여부를 궁금 어디 장소에서 *

struct BPlusNode 
{ 
public: 
    //holds the list of keys 
    keyType **keys; 
    //stores the number of slots used 
    size_t size; 
    //holds the array of pointers to lower nodes NULL if this is a leaf node 
    BPlusNode **children; 
    //holds the pointer to the next load to the 'left' 
    BPlusNode *next; 
    //Data page pointers NULL if this is a branch node 
    Bucket **pages; 
}; 

: 내 노드는 현재처럼 보인다.

* *는 두 개의 역 참조 연산을 필요로하므로 *를 사용하는 것보다 느리다는 것을 잘 알고 있지만이 클래스는 많은 재귀를 사용하며 하위 호출에 대한 포인터를 전달하는 것이 훨씬 편리합니다. 재귀 함수. 이것을하기 위해서 포인터 연산을하고 결과 포인터를 전달해야합니다.

와 **

someFunction(BPlusNode* currNode) 
{ 
    ...... 
    someFunction(currNode->children[ChildIndex]); 
} 

함께

*

someFunction(BPlusNode* currNode) 
{ 
    ...... 
    someFunction((currNode->children) + ChildIndex); 
} 

I에서, * 버전 원하는 포인터를 생성하기 위해 메모리의 추가 판독이 있다는 것을 알 수 있지만 * * 버전은 나를 생각하기에 더 쉽습니다 ("The Art of Computer Programming"과 위키 피 디아에서 그려진 다이어그램을 보는 방법과 더 비슷합니다).

누구에게 어떤 생각이 있습니까? 세 번째 옵션에 대한 제안? 왜 다른 사람보다 우월한 증거? 기타?

편집 :
아래 답변을 게시 할 수 있지만 * * 스키마를 사용하면 각 하위 노드 또는 버킷의 전체 내용을 복사 할 필요가 없다는 것을 깨달았습니다. 배열 (즉, 배열의 크기를 변경) 배열을 다시 할당 할 때 * 스키마에 20 개의 하위 노드가있는 경우 20 * sizeof (BPlusNode) 바이트를 복사해야하며 * * scheme의 경우 20 * sizeof (BPlusNode *) 바이트가 필요합니다.

반면에 나는 모든 인서트와 페이지 분할을 수행했기 때문에 이러한 성능 향상은 불필요하며 검색에서 * * ​​*의 이점이 더 중요 할 수도 있습니다.

Answer 1

키와 포인터 데이터에 대해 다른 구조체를 정의합니다. 디스크 구조와 일치해야하는 고정 크기 노드를 사용하겠다고 약속합니다. 이렇게하면 트리를 훨씬 쉽게 매핑 할 수 있습니다.

BPlusNode 구조체는 이러한 매핑 된 데이터 노드를 가리키는 핸들 클래스가되어 트리를 강등하면서 형제를 읽음으로써 prev 및 next 포인터와 같은 것들을 합성합니다.

enum BPlusNodeType { 
    LEAF, BRANCH 
}; 

struct BPlusNodeData { 
    static const size_t max_size = 511; // Try to fit into 4K? 8K? 
    uint16_t size; 
    uint16_t type; 
    keyType key[max_size]; 
    union { 
     Bucket* data[max_size]; 
     BPlusNodeData* children[max_size]; 
    }; 
}; 

Answer 2

**을 사용하면 각 BPlusNode* 자식 포인터를 보유하기위한 추가 할당 단계가 필요합니다. 또는 블록을 할당하고 children에있는 각 포인터가이 블록 안에있는 BPlusNode* 요소를 순차적으로 가리 키도록 할 수 있습니다. 그러나 노드 생성 당 하나의 동적 메모리 할당 (및 이에 상응하는 추가 할당 해제 단계)은 여전히 ​​있습니다. 그래서 나는 단 하나의 *을 사용할 것을 절대적으로 권할 것이다.

someFunction((currNode->children) + ChildIndex); 

작성하는 당신을 아픈 경우, 당신은 내가 명확하게 찾을 수있는

someFunction(&currNode->children[ChildIndex]); 

로 다시 작성할 수 있습니다.

Answer 3

당신이 'vector<BPlusNode *> children'와 STL 'vector<keyType *> keys'를 사용하는 것이 더 등겠습니까 : 그것은 다음과 같은 것을 볼 수 있었다

?

너무 단순 할 수도 있지만 더블 인다 우트 ​​(double-indirection)가 C++에서 자주 필요하지는 않습니다.