12강. 멀티웨이 탐색 트리 (I)

by

학습개요

앞에서 학습한 이진 탐색 트리를 장점을 살려서 더 효율적으로 사용하기 위해 만든 멀티웨이 탐색 트리에 대해 학습합니다. 처음으로 이진 탐색 트리를 확장한 것으로 ｍ개 이하의 가지를 가질 수 있는 ｍ원 탐색 트리가 있습니다.

탐색 트리의 제한을 유지하면서 2개 이상(ｍ개 이하)의 자식을 가질 수 있습니다. BS 트리가 2-way 탐색에 해당합니다. m원 탐색 트리는 파일의 인덱스를 구현할 경우에 특정 레코드를 빠르게 참조할 수 있습니다. 다음으로 B, B*, B+ 트리가 있습니다. 이 세 가지 트리의 조건을 명확하게 구분해서 이해해야 하고, 삽입과 삭제 방법을 비교하면서 학습하시는 것이 좋습니다.

우선, B트리는 세 가지 조건이 있는 트리입니다. 루트와 잎 노드를 제외한 트리의 각 노드는 최소 ⌈m/2⌉개의 서브트리를 갖으며, 트리의 루트는 최소한 2개의 서브트리를 갖는다. 그리고 트리의 모든 잎 노드는 같은 레벨에 있어야 한다는 조건입니다. 삽입과 삭제 연산을 진행할 경우에는 이 조건에 맞는지를 확인해야 합니다.

B*트리는 노드의 약 2/3 이상이 차야하는 B트리입니다. 삽입, 삭제 시 발생하는 노드 분리를 줄이려고 고안한 것입니다. B*트리는 노드가 꽉 차면 분리하지 않고, 키와 포인터를 재배치하여 다른 형제 노드로 옮깁니다. B+트리는 B트리와 같이 각 노드가 적어도 1/2이 차야 하는 점은 같습니다. 하지만 잎 노드를 순차적으로 연결하는 포인터 집합이 있다는 점에서 다릅니다. 또한 잎 노드가 모든 키값을 포함하고 있습니다. 따라서 순차 처리를 할 때는 왼쪽 끝부터 차례로 처리할 수 있는 장점이 있습니다.

학습목표

  1. m원 탐색 트리의 정의와 탐색 방법을 이해할 수 있다.
  2. B트리의 정의와 삽입 및 삭제 방법을 이해할 수 있다.
  3. B*트리의 정의와 삽입 방법을 이해할 수 있다.
  4. B+트리의 정의와 삽입 및 삭제 방법을 이해할 수 있다.

연습문제

  1. 노드의 약 2/3 이상이 차야하는  B트리는 무엇인가 ?
    1. BS 트리
    2. 레드블랙 트리
    3. B+트리
    4. B*트리
      –
  2. 다음 중 m-원 멀티 트리의 조건이 아닌 것은 무엇인가 ?
    1. i =0, ···, n-2  인 i 에 대해  ki<ki+1를 만족한다.
    2. 모든 단말 노드는 동일한 레벨에 놓인다.
    3. i=0, ···, n-1 인 i 에 대해  pi 가 가리키는 서브트리의 모든 키값은 ki 의 키값보다 작다.
    4. pn이 가리키는 서브트리의 모든 키값은 kn-1의 키값보다 크다.
      –
  3. 다음 중  B트리에 대한 설명이 아닌 것은 무엇인가 ?
    1. 루트와 단말 노드를 제외한 트리의 각 노드는 최소 ⌈m/2⌉개의 서브트리를 갖는다.
    2. 트리의 루트는 최소한 2개의 서브트리를 갖는다.
    3. 트리의 모든 단말 노드는 같은 레벨에 있다.
    4. 노드의 약 2/3 이상이 채워진다.

정리하기

  1. 트리의 노드가 m개 이하의 가지를 가질 수 있는 탐색 트리를 m원 탐색 트리라고 합니다.
  2. m원 탐색 트리는 이진 탐색 트리를 확장한 것으로 탐색 트리의 제한을 따르되 2개 이상(m개 이하) 자식을 가질 수 있습니다.
  3. 인덱스 구조를 구현하는데 가장 일반적으로 사용하는 방법으로 차수가 m인 B트리가 있습니다.
  4. B트리는 루트와 잎 노드를 제외한 트리의 각 노드는 최소 ⌈/2⌉개의 서브트리를 갖습니다.
  5. B트리의 루트는 최소한 2개의 서브트리를 갖습니다.
  6. B트리의 모든 잎 노드는 같은 레벨에 있습니다.
  7. B트리의 삽입 연산에서 노드가 꽉 차있는 경우는 분리해서 키값과 포인터를 재분배해야 합니다.
  8. B트리 삭제 연산에서 삭제 결과 개수가 부족하면 그 노드를 다른 노드와 묶어야 합니다.
  9. 노드의 약 2/3 이상이 차야하는 B트리를 B*트리라고 합니다.
  10. B*트리는 노드가 꽉 차면 분리하지 않고, 키와 포인터를 재배치하여 다른 형제 노드로 옮깁니다.
  11. B+트리는 인덱스된 순차 파일을 구성하는데 사용합니다. 인덱스된 순차 파일은 데이터를 차례로 처리하는 순차 처리와 특정 데이터를 직접 찾아 처리하는 두 가지를 모두 효율적으로 할 수 있는 구조입니다.
  12. B+트리는 잎 노드의 마지막 포인터는 다음 키값을 갖는 노드를 가리킵니다. 따라서 순차 처리를 할 때는 이 포인터를 이용해서 차례로 다음 데이터에 접근해서 처리할 수 있습니다.
  13. B+트리에서는 모든 키값이 잎 노드에 있고 그 키값에 대응하는 실제 데이터에 대한 주소를 잎 노드만이 가지고 있습니다.

Leave a Comment