노드 내 CSB + 트리에서 검색

Question

나는이 논문을 읽고있다. making B+-trees cache conscious in main memory. 섹션 3.1.2에서 저자는 CSB + 트리 노드 내에서 검색하는 몇 가지 방법을 설명합니다.

da 기본 접근법은 기존의 while 루프를 사용하여 간단히 이진 검색을 수행하는 것입니다.

균일 방법은 사용되는 모든 키를 가정 if-then-else 문으로 while 루프를 전개, 코드 확장 통해서이다.

저자는 최대 9 개의 키가있는 노드를 검색 할 때 다음과 같은 예를 보여줍니다. 5 키가 실제로 존재하는 경우

, 우리는이 트리를 탐색 할 수 : 노드의 수는 키의 위치가

   4 
      / \ 
      2  6 
     /\ /\ 
     1 3 5 8 
       /\ 
       7 9 

은 그런 혼란 일부 오는 if 시험에 사용되는 대표 정확히 비교. 반면에 오른쪽 대신에 가장 깊은 하위 트리를 배치하는 전개는 일부 브랜치에서 비교를 필요로합니다.

그래서 왜 다음 트리에 더 많은 비교를해야합니다 : 또한

   6 
      / \ 
      4  8 
     /\ /\ 
     2 5 7 9 
     /\ 
     1 3 

,

우리는 우리가 다섯 유효한 키를 알고 있었다, 우리는 나무를 하드 수있는, 평균적으로 사용 2.67 비교보다는 3

어떻게 2.67이 나옵니까?

힌트를 보내 주시면 감사하겠습니다. 또한 코드 확장 지식을 안내하는 링크가 도움이 될 것입니다.

사실, 필자는 여기에서 필사 될 때 일부 주요 정보가 생략되었을 수 있으므로 질문을하는 것이 적절한지 여부를 확신하지 못합니다 (질문을 다시 포맷해야 할 수도 있음). 나는 그저 종이를 읽은 누군가가있을 수 있기를 바란다.

감사

Answer 1

여기서 중요한 점은 동일 섹션에서 다음 견적이다

우리 노드 패드의 모든 않는 키 (하여 keyList [nKeys..2d-1]) 가능한 가장 큰 키를 가진

또한 B +/CSB + 트리에서 노드 값이 아니라 이러한 값 사이의 간격을 검색하는 것이 중요합니다. 가능한 값의 집합은 5 개의 키로 6 개의 간격으로 나뉩니다.

이

   4 
      / \ 
      2  L 
     /\ /\ 
     1 3 5 L 
       /\ 
       L L 

루트 노드의

오른쪽 자손이 가능한 가장 큰 키를, 아니이있다 : 우측 서브 트리의 대부분은 가능한 가장 큰 키 (L)로 가득하기 때문에

, 우리는 평소보다 덜 비교가 필요합니다 노드의 오른쪽에있는 노드를 확인해야합니다. 그리고 정확히 3 비교 모든 구간에 필요한 :

   L 
      / \ 
      4  L 
     /\ /\ 
     2 5 L L 
     /\ 
     1 3 

:

interval comparisons 
up to 1 k>4, k>2, k>1 
1..2  k>4, k>2, k>1 
2..3  k>4, k>2, k>3 
3..4  k>4, k>2, k>3 
4..5  k>4, k>L, k>5 
5..L  k>4, k>L, k>5 

우리가 왼쪽에있는 깊은 하위 트리를 두는 경우에, 우리는 한 단계 더 깊은 배치 비어 있지 않은 노드 트리를 가지고 이 트리에서 노드 "1"을 검색하려면 4 개의 노드가있는 키 (L, 4, 2 및 1)를 비교해야합니다.

유효한 키가 5 개 뿐인 경우 다음 트리가 있습니다.

는 여기에서 우리는 평균 2.67 비교를 제공하는, 방법으로 비교를 정렬 할 수 있습니다 :

이

interval comparisons 
up to 1 k>2, k>1 
1..2  k>2, k>1 
2..3  k>2, k>4, k>3 
3..4  k>2, k>4, k>3 
4..5  k>2, k>4, k>5 
5..L  k>2, k>4, k>5 

"코드 확장"는 널리 사용되는 용어되지 않습니다, 그래서 당신에게 가장 관련성이 링크를 줄 수 없습니다. 내 생각에 이것은 "Loop unwinding"과별로 다르지 않습니다.