B + 트리 검색은 리프 노드의 모든 키 - 데이터가 메모리에있는 바이너리 검색 트리 검색보다 잘 수행 할 수 있습니까?

Question

우리는 메모리에 B + 트리를 구현하고 키는 내부 노드에 있고 키 데이터 쌍은 리프 노드에 있다고 가정합니다. B + tree가 fan-out f 인 경우 B + tree는 log_f N의 높이를 가지며 여기서 N은 키의 수입니다. 반면 해당 BST의 높이는 log_2 N입니다. 우리가 아무 것도하지 않으면 디스크 읽기 및 쓰기, B + 트리 검색 성능 이진 검색 트리 검색 성능보다 좋을 수 있습니까? 방법? 각 내부 노드의 B + 트리의 경우 BST에 대해 1을 선택한 경우 F 대신 여러 가지를 결정했습니다.

Answer 1

적어도 캐시와 비교할 때 주 메모리는 디스크 드라이브와 많은 특성을 가지고 있습니다. 캐시는 캐시보다 훨씬 높은 대역폭을 가지지 만 대기 시간은 훨씬 길습니다. 최소 읽기 크기가 상당히 크며 읽기가 예측 가능한 경우 (예 : 인접한 주소에서 여러 개의 캐시 행을 읽은 경우) 상당히 높은 대역폭을 제공합니다. 이와 같이, 동일한 일반 종류의 최적화 (비록 세부 사항은 종종 조금씩 다르지만)로부터 이익을 얻습니다.

B- 트리 (B * 및 B + 트리와 같은 변형)는 디스크 드라이브에서 지원되는 액세스 패턴과 잘 작동하도록 명시 적으로 설계되었습니다. 어쨌든 상당히 많은 양의 데이터를 읽어야하기 때문에 읽어야하는 메모리에서 얻는 양을 최대화하기 위해 데이터를 압축 할 수도 있습니다. 두 경우 모두 예측 가능한 패턴 (특히 연속적인 주소에서 연속적인 읽기 횟수)에서 최소 판독 값의 여러 배를 읽음으로써 상당한 대역폭 이득을 자주 얻게됩니다. 따라서 한 페이지의 크기를 한 번에 읽을 수있는 최소 크기보다 더 크게 늘리는 것이 좋습니다.

마찬가지로 두 경우 모두 우리가 정말로 신경을 쓰는 데이터를 찾기 전에 트리의 여러 노드 레이어를 통해 내림차순으로 계획 할 수 있습니다. 디스크에서 읽을 때와 마찬가지로 우리가 읽은 데이터의 키 밀도를 최대화하여 실제로 우리가 관심있는 데이터를 찾을 때까지 이점을 얻습니다. 일반적인 이진 트리로 :

template <class T, class U> 
struct node { 
    T key; 
    U data; 
    node *left; 
    node *right; 
}; 

... 우리는 우리가 실제 사용이없는 데이터 항목의 수를 읽는 끝낸다. 관련 데이터를 얻고 자하는/원하는 키를 찾았을 때만입니다. 공정에서, 우리는 노드 구조 만 상당히 약간의 수정과 함께,뿐만 아니라 이진 트리와 함께이 작업을 수행 할 수 있습니다

template <class T, class U> 
struct node { 
    T key; 
    U *data; 
    node *left; 
    node *right; 
}; 

이제 노드는 데이터가 아닌 데이터 자체에 대한 포인터 만 포함되어 있습니다. data이 작 으면 아무 것도 수행하지 않지만 큰 경우 많은 작업을 수행 할 수 있습니다.

요약 : CPU의 관점에서, 메인 메모리로부터의 읽기는 디스크로부터의 읽기와 동일한 기본 특성을 갖는다. 디스크는 이러한 동일한 특성의 극단적 인 버전을 보여줍니다. 따라서 B- 트리 (및 변형)의 설계를 이끌어 낸 설계 고려 사항의 대부분은 이제 주 메모리에 저장된 데이터와 유사하게 적용됩니다.

B- 트리는 잘 작동하며 메모리 내장 스토리지로 사용될 때 상당한 이점을 제공합니다.