LEE CHANWOO

📝 Blog 2024 version 1.7.0
🔖 NOV 26, 2024

5 분 소요

Database System

Tree Index

Static/Dynamic Tree Indexing

  • Static Indexing(정적 인덱싱)
    • 삽입/삭제는 데이터 파일에 반영됩니다.
    • 오버플로 체인이 사용됩니다.
    • 정기적인 오프라인 파일 재구성.
    • 검색은 자주 업데이트되지 않는 경우 매우 효율적입니다.
    • 오버플로가 없을 때 삽입/삭제가 효율적입니다.
    • ISAM 파일
  • Dynamic Indexing(동적 인덱싱)
    • 삽입/삭제는 인덱스 파일에 반영됩니다.
    • 오버플로 체인은 사용되지 않습니다.
    • 동적으로 온라인 자체 조직화.
    • 검색 및 빈번한 업데이트에 효율적입니다.
    • DBMS에서 가장 많이 사용
    • B 트리, B+ 트리

Static Tree Indexing

ISAM File

  • 데이터 파일은 키값으로 정렬 됩니다
  • 인덱스 파일은 노드 구조가 다음과 같은 다중 검색 트리(multi-way searching tree) 입니다.

image

  • K1, K2, …, Km-1 : Search Keys
  • P0, P1, …, Pm : Tree(Index) Pointers
  • K1 < K2 < … < Km-1

image

  • 처음에는 데이터 파일을 기본 페이지에 순차적으로 할당하고 검색키를 기준으로 정렬합니다.
  • 그런 다음 트리 구조의 인덱스 노드가 할당됩니다. 각 노드는 디스크 페이지에 해당합니다. 이 인덱스는 리프 페이지에 있는 데이터 항목을 검색할 수 있게 합니다.
  • 그런 다음 향후 삽입을 위해 오버플로우 페이지를 위한 공간이 할당됩니다.

image

image

Searching

  • Equality
    • Find 33, Find 99, …
  • Range
    • Find all values >= 33, Find all values < 63, …

image

  • 모든 기본 페이지는 순차적으로 할당되므로 다음 리프페이지는 포인터가 필요하지 X

Searching Cost

  • N을 데이터 파일의 페이지 수라고 하고 F를 팬아웃fanout(=리프가 아닌 노드당 평균 자식 수)이라고 하자
  • 루트에서 시작하여 N·(1/F) 크기의 하위 트리로 이어집니다.
    • 트리를 검색할 때 검색 공간은 F의 인수만큼 반복으로 감소합니다.
    • N·(1/F)·(1/F)·(1/F)···
  • 인덱스 검색은 검색 공간이 크기 1로 줄어들면 t 단계 후에 종료됩니다.
    • 즉, 인덱스 리프 수준에 도달하여 원하는 레코드가 포함된 데이터 페이지를 찾음
    • N· $(1/F)^t$ =1 → t = $log_{F}N$
  • 일반적으로 F는 100 이상이다.

Insertion / Deletion

Insertion

  • 먼저 레코드를 삽입하려면 적당한 기본 페이지를 찾아야함
    • 공간이 충분하다면 삽입
    • 그렇지 않으면 새페이지(오버플로우 페이지)를 할당하고 여기에 삽입
  • 오버플로우 페이지의 레코드는 일반적으로 순서가 지정되지 않음
    • 후속 삽입 후에 오버플로우 체인이 유지 Deletion
  • 먼저 레코드를 삭제하려면 적당한 기본 페이지를 찾아야함
    • 오버플로우 페이지에서 삭제가 완료되어 비어있으면 페이지를 제거(할당 해제)함
    • 기본 페이지에 있는 경우 향후 삽입을 위해 빈 페이지를 남겨둠

Insertion

image


Deletion

image

  • 삽입/삭제는 데이터 페이지만 수정함. 인덱스 페이지를 절대 수정하지 않음
    • 즉, 인덱싱 파일의 모양은 항상 동일함
    • “읽기 전용 인덱스 파일”
  • 모든 삽입은 리프페이지 수준에서 수행되므로 오버플로우 체인이 길어짐 → 성능 저하
  • 데이터 레코드 크기가 인덱스 크기보다 훨씬 크기 때문에 오버플로 체인 블록의 수가 많을 수 있음
  • 오버플로우 체인 액세스 시간은 인덱스 액세스 시간 보다 클 수 있음
  • 특히, 불균일한 데이터 분포는 검색 성능을 심각하게 저하 시킴

Processing Overflow Chains

  • 존재하지 않는 레코드 검색:
    • 평균적으로 체인의 절반을 검색해야 함
    • 존재하지 않는 레코드는 전체 체인을 검색해야 함
    • 체인을 정렬된 목록으로 유지하는 것이 도움이 될수 있음
  • 자주 필요한 레코드 가져오기:
    • 사용빈도순으로 체인에 기록을 보관하면 기존 기록을 더 빨리 찾을 수 있음
    • 최근 업데이트가 필요할 가능성이 높으므로 체인의 전면에 새 업데이트를 삽입하는 것이 효율적일 수 있음
  • 체인 길이 분포:
    • 실제로 오버플로우 체인의 길이가 같지 않아 성능이 저하될 수 있음
    • 추가 작업은 마지막 페이지에 긴 체인을 만듬
      • 무작위 삽입(추정 체인 길이 기반)이 도움이 될 수 있음

요약

  • 긴 오버플로우 체인은 성능을 저하 시킴
  • 정기적인 재구성이 필요
    • 재구성(Merging + Re-Sorting + Re-Indexing)은 시간이 오래걸림
    • 일반적으로 오프라인 기반으로 수행
  • 자주 업데이트하지 않으면 효율적
    • 오버플로우 체인이 없는 정적 인덱스는 인덱스 페이지가 읽기만 하고 쓰지 않기 때문에 동적 인덱스보다 빠름
  • 삽입할 검색 키 집합을 미리 알고 있으면 향후 삽입을 위해 여유 공간(일반적으로 20% 여유 공간)을 예약하고 오버플로우를 줄여 인덱스를 작성할 수 있음
  • ISAM 인덱스는 정적이므로 동시 인덱스 액세스 중에 인덱스 페이지를 잠글 필요가 없음
    • 동시성 제어 필요하지 않음

Dynamic Tree Indexing

  • B Tree는 빠른 검색 및 업데이트를 위해 엄청난 양(백만/십억 항목)의 데이터를 저장하기 위한 우수한 인덱싱 구조
  • B Tree는 일반적으로 얕지만 넓은 데이터 구조
    • 다른 Tree는 매우 높아질 수 있지만 일반적인 B Tree는 수십억 개의 데이터가 있어도 높이가 한 자릿수(3~5)
  • 따라서 실용적인 관점에서 B-Tree는 매우 큰 데이터 세트에 대해서도 10ms 미만의 액세스 시간을 보장함(Bayer, inventor of B tree)
  • 읽기 또는 쓰기를 위해 트리의 임이의 부분에 액세스하려면 상위 수준 트리 노드를 캐싱하여 몇 개의 노드만 필요하며 이는 몇번의 헤드 검색으로 변환됨
  • 이후 변형된 B tree
    • B* tree(Knuth)
    • B+ tree(Knuth, Comer)
    • R tree(Guttman)

B+ Tree

  • 가장 일반적으로 사용되는 B+ Tree는 ISAM과 B Tree 아이디어에서 파생됨
  • “B”는 “balanced“을 나타냄
    • 루트에서 각 리프까지의 모든 경로는 동일한 길이를 갖음
  • 인덱싱되는 파일 크기에 대한 인덱싱 수준 수를 자동으로 유지(Self-organizaed)
  • B+ Tree는 오버플로우 체인이 필요하지 않기 때문에 효율적인 삽입/삭제 성능을 제공함
    • 기본 인덱스 파일은 동적으로 증가/축소할 수 있음

image

Non-leaf (Internal) Node

image

  • 각 내부 노드에는 최대 n개 트리 포인터가 있음(n: 최대 fanout); m ≤ n
  • 각 내부 노드(루트 제외)는 최소 n/2개 의 트리 포인터를 가지고 있음; n/2 ≤ m
  • 루트 노드에는 적어도 두개 의 트리 포인터가 있음; 2 ≤ m (≤ n)
  • 검색 키는 정렬됨; K1 < K2 < … Km-1
  • 포인터 P1은 X < K1인 하위 트리를 가리키고 Pi는 Ki-1 ≤ X ≤ Ki인 하위 트리를 가리키고 Pm은 하위 트리 X ≥ Km-1 을 가리킴
  • m개의 트리 포인터가 있는 내부 노드에는 (m-1)개의 검색 키가 있음

Leaf Node

  • 각 Pri는 각 검색 키 Ki 가 있는 레코드를 포함하는 데이터 페이지를 가리키는 데이터 포인터
  • 검색 키는 정렬됨; K1 < K2 < … Km-1
  • 각 리프 노드에는 최대 n 개의 데이터 포인터가 있음
  • 각 리프 노드에는 최소 n/2 -1 개의 데이터 포인터가 있음
  • 2개의 리프 노드 포인터 가 있음 → 왼쪽/오른쪽 리프 포인터
  • 모든 리프 노드는 동일한 수준

Example : B+ Tree

image

  • 내부 노드에 몇 개 의 트리 포인터가 있나?
    • 3 ~ 5 (2 ~ 4 검색 키)
  • 루트 노드에 몇 개 의 트리 포인터가 있나?
    • 2 ~ 5 (1 ~ 4 검색 키
  • 리프 노드에 몇 개 의 트리 포인터가 있나?
    • 2 ~ 4 (2 ~ 4 검색 키)
  • 이 B+ 트리에 몇 개의 검색 키가 있나?
    • 17
  • 이 B+ Tree의 높이는 얼마인가?
    • 3
  • 균형(balanced)이 맞나?
    • O

Properties

  • 리프가 아닌 노드와 리프 노드의 구조가 다름
  • 모든 검색 키 (데이터 포인터 포함)는 리프 수준에만 있음
  • 모든 리프 노드는 동일한 수준 → 높이 균형
  • 검색 키 K 가 주어지면 다른 K 값에 대해 동일한 액세스 시간이 주어짐
    • 루트에서 각 리프까지의 모든 경로의 길이가 동일하기 떄문
  • 루트를 제외한 각 노드는 최소 절반(최소 50%)이 차있음
  • 모든 리프 노드는 이중 연결 목록, 이른바 시퀀스 집합으로 연결됨
    • 효율적인 range 검색

Exercise

  • ID를 검색 키로 사용하여, Customer(ID, name, age, …) 파일에 대한 B+ 트리 인덱스를 빌드함
  • 검색 키 크기(ID)가 6바이트이고 트리 포인터 크기가 4바이트라고 가정
  • 데이터 포인터 크기는 8바이트

  • 페이지 크기는 2,048바이트

  • 리프가 아닌 노드에 몇 개의 트리 포인터가 있는가?
    • (n-1)6 + n4 ≤ 2,048 → 최대 팬아웃 = 205
    • 최소 팬아웃은 50% * 205 = 103
    • 리프가 아닌 노드는 103 ~ 205개의 트리 포인터를 저장함(102 ~ 204개의 검색 키)
  • 리프 노드에 몇 개의 트리 포인터가 있는가?
    • n6 + n8 + 4(리프 포인터)*2 ≤ 2,048 → 최대 n = 142
    • 최소 n은 50% * 142 = 71
    • 리프 노드는 71 ~ 142개의 데이터 포인터를 저장함(71 ~ 142개의 검색 키)
  • 높이가 4인 B+ Tree에 저장되는 최대 검색 키는 몇 개 인가?
level #nodes #tree pointers #search keys
level 1 1 205 204
level 2 205 205^2 205 * 204
level 3 205^2 205^3 205^2 * 204
(leaf) 4 205^3   205^3 * 142
  • 높이가 4인 B+ Tree에 저장되는 최소 검색 키는 몇 개 인가?
level #nodes #tree pointers #search keys
level 1 1 2 1
level 2 2 2 * 103 2 * 102
level 3 2 * 103 2 * 103^2 2 * 103 * 102
(leaf) 4 2* 103^2   2 * 103^2 * 71
  • 이 B+ Tree는 약 150만 ~ 12억 2천만 개의 검색키를 저장할 수 있음

댓글남기기

참고