[데이터베이스] B 트리 & B+ 트리

복습하기 위해 학부 수업 내용을 필기한 내용입니다.
이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다.
그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다.

▶B - 트리

• 차수가 m인 B - 트리의 특성
  • 비어있거나 높이가 1 이상인 m - 원 탐색 트리(m-way search tree)이다.
  • 루트와 리프를 제외한 노드는 최소 ⌈ m/2 ⌉, 최대 m개의 서브 트리를 갖는다.
  • 루트는 리프가 아닌 이상 적어도 두 개의 서브 트리를 갖는다.
  • 모든 리프는 같은 레벨에 있다.
  • 리프가 아닌 노드의 키 값의 수는 그 노드의 서브 트리 수 보다 하나 적다.
  • 각 리프 노드는 최소 ⌈ m/2 ⌉ - 1개, 최대 m - 1개의 키 값을 갖는다.
  • 한 노드 안에 있는 키 값들은 오름차순을 유지한다.

https://ko.wikipedia.org/wiki/B_%ED%8A%B8%EB%A6%AC

B 트리 - 위키백과, 우리 모두의 백과사전

차수가 3인 B 트리 구조

728x90

▶B - 트리의 연산

• 검색
  • 키 값의 왼쪽 포인터로 지시된 서브 트리의 모든 키 값들은 이 키 값보다 작고, 오른쪽은 이 키값보다 크다.
  • 리프 노드에는 하부 서브 트리에 대한 포인터가 없다.
• 삽입
  • 항상 리프 노드에서 수행하게 된다.
  • 빈 공간이 있는 경우 : 단순히 빈 공간에 삽입하면 된다.
• 삭제
  • 리프 노드에서는 그대로 삭제한다.
  • 리프가 아닌 노드에 있을 경우 후행 키 값과 자리를 바꾸어 삭제를 진행한다.
  • 삭제 뒤 남아 있는 키 값의 수가 ⌈ m / 2 ⌉ - 1에 미달하게 되면 재분배 방법, 합병방법을 시용해 최소 키 값을 유지해야 한다.

 

▶B+ - 트리

• B+ - 트리는 인덱스 세트와 순차 세트로 구성되어 있다.
  • 인덱스 세트 (index set)
    • 리프 노드에 있는 키들에 대한 경로만 제공한다.
    • 직접 접근을 지원한다.
  • 순차 세트 (sequence set)
    • 리프 노드로 구성되고 모든 키 값들을 저장한다.
    • 순차 세트는 순차적으로 연결한다.
      • 순차 접근을 지원한다.
    • 리프 노드는 내부 노드와 상이한 구조를 가진다.

차수가 3인 B+ 트리

▶(m차) B+ - 트리 특성

• 루트는 0이거나 2에서 m개 사이의 서브 트리를 가진다.
• 루트와 리프를 제외한 모든 내부 노드는 최소 ⌈ m/2 ⌉, 최대 m개의 서브 트리를 가진다.
• 모든 리프 노드는 같은 레벨이다.
• 리프가 아닌 노드에 있는 키 값의 수는 그 노드의 서브 트리 수보다 하나 적다.
• 한 노드 안에 있는 키 값들은 오름차순이다.
• --------------------------------------------------------------------
• 노드 구조는 (P0, K1, P1, K2, P2,... , Pn-1, Kn, Pn)
  • n : 키 값의 수( 1 ≤ n <m )
  • P0,..., Pn : 서브 트리에 대한 포인터
  • K1,..., Kn : 키 값
• Pi, (0≤i≤n-1)가 지시하는 서브 트리에 있는 노드들의 모든 키 값들은 Ki+1보다 작거나 같다.
• Pn이 지시하는 서브 트리에 있는 노드들의 모든 키 값들은 Kn보다 크다.
• 잘 이해가 되지 않는 부분이다.
• --------------------------------------------------------------------
• 순차 세트를 구성하는 리프 노드는 모드 링크로 연결된 연결 리스트를 구성한다.
• 리프 노드의 구조
  • ((K1, A1), (K2, A2),... , (Kq, Aq), Pnext)
  • Ai : 키 값 Ki를 가지고 있는 레코드에 대한 주소
  • Pnext : 다음 리프 노드에 대한 링크
  • q는 ⌈ m / 2 ⌉ ≤ q이다.

 

▶B - 트리와의 차이점

• 인덱스 세트에 있는 키 값은 리프 노드에 있는 키 값을 찾아가는 경로로만 제공하기 위해 사용한다.
  • 인덱스 세트에 있는 키 값은 모두 순차 세트에 다시 나타난다.
• 인덱스 세트의 노드와 순차 세트의 노드는 그 내부 구조가 서로 다르다.
  • 리프 노드 : 키 값(Ki)과 이 키 값을 가진 레코드에 대한 주소(Ai)가 함께 저장된다.
  • 인덱스 세트 노드 : 키 값만 저장
  • 노드에 저장할 수 있는 원소의 수도 서로 다르다.
• 순차 세트의 모든 노드가 순차적으로 연결된 연결 리스트이다.
  • 순차 접근을 효율적으로 지원한다.

 

▶B+ - 트리의 연산

• 탐색
  
  • 인덱스 세트 : m - 원 탐색 트리와 같다.
  • 레코드는 리프에서 검색한다.
• 삽입
  • B 트리와 유사하다.
  • 리프가 오버플로가 되면 분할한다.
    • 중간 키 값은 부모 노드로 올라가 저장되지만 분할 노드에도 존재한다.
  • 순차 세트의 연결 리스트의 순차성을유지해야 한다.
• 삭제
  • 리프 노드에서만 삭제한다. (재분배, 합병이 필요 없는 경우)
    • 인덱스 세트에 있는 키 값은 분리자로 유지한다.
    • 키 값을 탐색하는 데 분리 키 값으로 사용한다.
  • 재분배 : 인덱스 키 값 변경, 트리 구조 유지
  • 합병 : 인덱스 키 값도 삭제