Chapter 11. Multiway Search Trees

이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요.

1. M-way Search Trees
   - 다원 탐색 트리
   - 메모리 접근 시간이 산술/논리 연산을 수행하는 것보다 훨씬 더 많은 시간을 소비함.
    ⇒ 프로세서 속도와 메모리 접근 시간 간의 큰 차이 때문에 메인메모리에서 캐시로 캐시 라인 크기 단위로 옮겨지고, 디스크에서 메인메모리로는 블록 단위로 옮겨짐.
   
   

   

   
   
   - 참고 url : http://www.intelligence.tuc.gr/~petrakis/courses/datastructures/btrees.pdf
                    http://webdocs.cs.ualberta.ca/~holte/T26/m-way-trees.html
   - AVL 트리, Red-Black 트리는 노드 크기가 몇 바이트 정도로 작기 때문에 느린 저장장치(디스크)에서 더 빠른 저장장치(캐시나 메인 메모리)로 데이터를 옮길 때 블록과 같은 큰 단위를 이용할 수 없다. 또한 이러한 트리들에서 특정원소를 찾는다 할 때, 탐색 시간의 대부분이 메모리 접근에 쓰일 수 있다. 메모리접근 횟수를 반으로 줄이면 비교횟수는 2배가 되지만 총 탐색시간은 감소한다.
   탐색 트리의 높이와 메모리 접근횟수는 밀접한 상관관계가 있으므로 탐색 트리의 높이를 줄여야 한다. BST를 이용하면 트리 높이가 log(n+1)로 커지기 때문에, 이를 개선하기위해, 차수(degree)가 2보다 큰 탐색 트리를 이용해야 한다. (실제로, 트리 노드들이 하나의 캐시 라인이나 디스크 블록을 채울 수 있는 가장 큰 차수를 사용하고 있다.)
   ⇒ suitable for disk

1. 각 노드는 최대 m-1 개의 원소를 가질 수 있다.

2. B Trees

1. 외부 노드 (externel node)
   : 탐색 중에 트리에서 찾고자 하는 원소를 검색하지 못했을 때만 도달할 수 있는 노드
   : Null 포인터가 있을때마다 외부노드가 추가되거나 검색실패가 된다
   : 외부노드가 아닌 것은 내부노드(internal node)라고 한다.

2. 차수가 m인 B tree는 공백이거나 다음 성질을 만족하는 m-way search tree이다
   - 루트 노드는 적어도 2개의 자식을 갖는다
   - 루트노드와 외부 노드를 제외한 모든 노드는 적어도 [m/2]개의 자식을 갖는다
   - 모든 외부노드들은 같은 레벨에 있다.
   

3. m-way search tree에서 모든 내부 노드는 차수가 [m/2] 이상 m 이하이다.
   → 차수가 3인 B tree는 2-3 Tree , 차수가 4인 B tree는 2-3-4 Tree 라고도 한다.
   * 차수가 5인 B tree는 루트를 제외하면 차수가 2인 노드를 가질 수 없으므로 2-3-4-5 트리가 아니다.
   * 차수가 2인 B tree는 포화 이진 트리 (full binary tree)이다. 이 트리는 어떤값 k에 대해서 키 값의 수가 2k-1일 때만 존재한다.
   * 모든 n0, m>2에 대해서 키가 n개이고 차수가 m인 B-tree는 항상 존재한다.
   
   [트리 예]
   

   

   
   
   

4. 외부노드는 컴퓨터 내에서 물리적으로 표현되지 않는다. 자식 포인터가 NULL로 설정.

5. 삽입/삭제는 2-3, 2-3-4 트리 참고
   

2. B+ Trees
   - 참고 URL
    : http://ko.wikipedia.org/wiki/B%2B_%ED%8A%B8%EB%A6%AC
    : http://en.wikipedia.org/wiki/B%2B_tree
    : http://sweeper.egloos.com/899699

1. 특징
   - 키(key) 값에 의하여 각각 식별되는 레코드의 효율적 삽입/삭제/검색을 통해 정렬된 데이터를 표현
   - 모든 레코드들이 트리의 가장 하위레벨에 정렬. 키들만 내부 블록에 저장
   - 블록-지향적인 storage context에서 효율적인 검색을 위해 데이터를 저장하는 것이 목표
   - 블록 인덱싱을 위해 B+ Tree 타입을 사용하는 파일시스템
    :         ReiserFS filesystem (Unix and Linux)

XFS filesystem (IRIX, Linux)

JFS2 filesystem (AIX, OS/2, Linux)

NTFS filesystem (Microsoft Windows)

2. B Tree와의 차이점 ( 비슷한 계통이긴하지만… )
   *** B+ Tree에는 2가지 종류의 노드가 존재함 ***
    > 인덱스(index) 노드 :
      - B tree의 내부노드와 상응
      - 키(원소는 저장안함)와 포인터를 저장
   
    >  데이터(data) 노드  :
      -  B tree의 외부노드와 상응
      -  키와 함께 원소를 저장한다. (포인터는 저장안함)
      - 왼->오 순으로 서로 링크 되어있고, 이중 연결 리스트를 형성
   

3. 탐색
   - 2가지 종류의 탐색 지원

1. 정확히 일치하는 값에 대한 검색

2. 범위 검색
   

4. 삽입/삭제
   

Addition.
http://www.cis.temple.edu/~wangp/3223-DA/Lecture/04-BalancingTree-3.htm

이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요.