LEE CHANWOO

📝 Blog 2024 version 1.5.2
🔖 JUN 29, 2024

9 분 소요

Database System

  • 주어진 검색 키 K로 레코드 찾기; 루트에서 시작하여 적절한 트리 포인터를 찾으십시오.
  • 그런 다음 올바른 리프 노드에 도달할 때까지 다음 레벨로 포인터를 반복해서 따라갑니다.
  • K가 Kj와 같으면 데이터 포인터 Pj를 따라 값이 K인 레코드를 찾습니다.
  • 키가 20인 레코드를 찾으려면 ? image
  • 키 값이 K인 레코드 찾기
Algorithm Equality Search (K, p)
  p ← root node page;
  read page p into main memory buffer;      
  while (p is not a leaf page) do
    { /* In-Memory Search */
      if K < p.K1 then p = p.P1
      else if K >= p.Km-1 then p = p.Pm
      else
        {
          search page p for entry i such that p.Ki-1 ≤ K < p.Ki
          p ← i ;
        }
      read page p into memory buffer;
    }
    search leaf page p for entry (Ki , Pri ) with K = Ki ;  
    if found, then read data page with address Pri ;
  • B+ 트리는 {<, >, >=, … } 를 사용하는 range 쿼리에도 유용합니다.
  • 범위가 Ka ≤ K ≤ Kb인 키 값이 있는 모든 레코드를 찾으려면
  1. Equality Search 알고리즘을 사용하여 키 값 Ka를 검색합니다. Ka가 있을 수 있는 리프 노드에서 키 >= Ka를 검색합니다.
  2. 획득한 키 값이 ≤ Kb인 한, 오른쪽 잎 블록 포인터를 따라 후속 블록을 추적하고 키 값을 계속 검사합니다.
  3. ≥ Kb 값을 찾거나 블록 체인이 끝날 때까지 2단계를 반복합니다.

Insertion

  • 새 레코드를 삽입하려면 검색 알고리즘을 사용하여 올바른 리프 노드 L을 찾습니다.
  • L에 충분한 공간이 있으면 L에 삽입하십시오. 그렇지 않으면 L을 split하십시오. (L로 그리고 새로운 노드 L’ 로)
    • 항목을 L 과 L’ 에 균등하게 분배하여 각각이 최소 절반(50%)이 되도록 합니다.
    • 중간 키를 상위에 복사합니다.
  • 이 분할은 상위 레벨까지 반복적으로 발생할 수 있습니다.
    • 리프가 아닌 노드를 분할하려면 항목을 균등하게 재배포하되 중간 키를 위로 올리십시오. (리프 노드 분할과 대조됩니다.)
  • split은 tree의 높이를 증가시킵니다; 루트 노드 split은 높이를 증가시킵니다.

No Split

  • 15 삽입
    • L 이 가득 차있지 않기 때문에 그냥 삽입

image

Leaf Split

  • 8 삽입
    • L 이 가득 찼습니다. 새 노드 L’ 로 분할합니다. Distribute entries
    • 가운데 키(5)를 위로 복사합니다. (리프 노드 5개)

image

Non-Leaf(Root) Split

  • 8 삽입
    • L 이 가득 찼습니다. 새 노드 L’ 로 분할합니다. Distribute entries
    • 가운데 키(5)를 위로 복사합니다. (리프 노드 5개)
    • 상위(루트)가 가득 찼습니다. Split; 중간 키(17)를 위로 올립니다. (17은 남지 않음)
    • 이때 tree의 높이는 1 증가합니다.

image

Copy Up vs. Push-Up

image

  • Copy-Up: 가운데 키 5가 복사되고 데이터 레코드를 안내하기 위해 리프 노드에 남아 있음
  • Push-Up: 중간 키 19가 위로 올라와 인덱스 노드에서 안내하기 위해 ‘한 번’만 나타납니다

Root Split

  • Split은 리프 수준에서 시작하여 인덱스 노드가 완전히 사용되는 한 위쪽으로 계속됩니다.
  • 결국 이것은 루트 노드의 split으로 이어질 수 있습니다. 이 경우 새 루트를 만들어야 합니다.
  • 루트 분할이 얼마나 자주 발생할 것으로 예상하십니까? 아주 드물다.
    • 루트는 50% 미만의 점유율을 가질 수 있는 유일한 노드입니다. 이것은 tree 높이가 증가하는 유일한 상황입니다.
    • 대부분의 노드 split은 결국 특정 수준에서 중지됩니다.
    • 루트 split 후 많은 리프 노드에 여유 공간이 있을 수 있습니다.

Properties

  • 데이터 파일에 새 레코드가 삽입되면 균형을 유지하기 위해 B+ 트리 인덱스를 변경(기록)해야 합니다. ISAM과 달리 오버플로 페이지를 사용하지 않습니다.
  • 리프 및 리프가 아닌 노드 split 모두에서 최소 점유 및 균형이 어떻게 보장되는지 확인할 수 있다
  • split 유형
    • 리프 노드 분할: Copy-Up
    • 리프가 아닌(인덱스) 노드 분할: Push-Up
  • 노드 split은 리프에서 루트 수준으로 전파되어 높이가 1 증가할 수 있습니다. (그러나 이것은 거의 발생하지 않음)

Variation of Insertion

  • 노드 L을 분할하기 전에 형제와 함께 노드 L의 항목을 재배포합니다.
  • 재배포가 가능한지 여부를 결정하려면 형제를 검색해야 합니다. 형제에 공간이 있으면 거기에 새 키를 삽입합니다. 그렇지 않으면(두 형제가 모두 가득 찼음) 어쨌든 노드를 분할해야 합니다.
  • 재배포가 가능한지 확인하면 특히 두 형제를 모두 확인하는 경우 I/O가 증가할 수 있습니다.
  • 그러나 재배포가 성공하면 노드 분할을 상위 수준으로 전파할 필요가 없기 때문에 I/O가 줄어들 수 있습니다. 우리는 tree가 자라는 것을 피할 수 있습니다. 이것은 B+ 트리의 평균 점유율을 향상시킵니다.
  • 삽입의 또 다른 변형은 presplitting입니다.

Deletion

  • 레코드를 삭제하려면 검색 알고리즘을 사용하여 올바른 리프 노드 L을 찾습니다.
  • 키를 제거한 후 L이 절반 이상 차면 완료! 그렇지 않으면,
    • 형제(L과 부모가 같은 인접 노드)에서 차용하여 re-distribution(재분배)를 시도합니다.
    • 재배포에 실패하면 L과 그 형제를 merge(병합)합니다.
  • 병합이 발생하면 L의 상위 항목(L 또는 형제를 가리킴)을 삭제해야 합니다

  • 병합은 트리를 축소할 수 있습니다. 병합은 높이를 줄임으로써 루트로 전파될 수 있습니다.

  • 삭제로 인해 리프 노드 L이 50% 미만으로 떨어진다고 가정합니다.
    • Redistribution: (왼쪽 또는 오른쪽) 형제 노드에 예비 항목이 있습니다.
      • 항목은 노드 L과 형제 노드 L’ 사이에 재분배됩니다.
      • L을 가리키는 부모 노드의 키 값은 L’에서 가장 작은 키로 변경됩니다.
    • Merge: 형제 노드에 예비 항목이 없습니다.
      • 항목은 노드 L과 형제 노드 L’ 사이에 병합됩니다
        • 리프 노드 병합
        • 리프가 아닌 노드 병합

Simple Case

  • 27 삭제
    • L에는 충분한 공간이 있으므로 삭제하면 됩니다

image

Redistribution

  • 20 삭제
    • 20이 삭제된 후 L은 언더플로입니다. 오른쪽 형제 L’을 보세요.
    • L’에는 충분한 공간이 있습니다. L’에서 25를 빌리십시오.
    • 부모의 25는 복사된 L’의 가장 작은 키(27)에 의해 변경됩니다.

image

Merge

  • 20 삭제
    • L은 언더플로입니다. 오른쪽 형제 L’을 보세요. L’에는 공간이 충분하지 않습니다.
    • L과 L’ 병합 25, 29를 L’에서 L로 이동하고 노드 L’을 제거합니다.
    • 부모의 25는 더 이상 필요하지 않으므로 삭제하십시오.

image

  • 병합 P와 P’; 5, 14를 P로 이동하고 노드 P’를 삭제합니다.
  • 상위 P는 이제 언더플로입니다. 왼쪽 형제 P’를 보십시오. P’에는 공간이 충분하지 않습니다.
  • 병합 P와 P’; 부모에서 17을 아래로 당겨 부모(루트)를 제거합니다.

image

Properties

  • 데이터 파일에서 레코드가 삭제되면 균형을 유지하기 위해 B+ 트리 인덱스 구조를 변경(기록)해야 합니다.
  • 재배포 및 병합을 사용하여 리프 노드와 인덱스 노드 모두에서 최소 점유 및 균형이 어떻게 보장되는지 관찰하십시오.
  • Merge(병합) 유형
    • 리프 병합
    • 리프가 아닌(루트) 병합
  • 병합은 리프에서 루트 수준으로 전파되어 높이가 1 감소합니다. (그러나 이것은 거의 발생하지 않습니다)

꼭 Delete를 해야하나?

  • 삭제를 전혀 수정하지 않는 B+ 트리 구현이 있습니다. 리프 노드에 키가 너무 적으면 그대로 두는 것이 허용됩니다.
  • 실제 DBMS 구현은 종종 병합 및/또는 재배포 비용을 피하지만 최소 점유 규칙을 완화합니다.
  • 리프가 언더플로가 되는 삭제가 가끔 있을 수 있지만 대부분의 파일은 증가하고 리프는 곧 다시 최소 점유율에 도달합니다.
  • 또한 동시성을 향상시키기 위해 삭제된 인덱스 항목은 삭제된 것으로 표시되고 나중에만 제거됩니다. 이를 위해서는 전체 인덱스 재구성이 필요합니다.

Performance Analysis

  • B+ 트리에서 등식 검색, 삽입 및 삭제를 위한 I/O 비용은 O(logFN) 로 제한됩니다. 여기서 N: 검색 키의 수, n/2 ≤ F ≤ n (n: fanout)
  • 범위 검색의 경우 O((logFN + α)) 여기서 α는 인덱스 유형에 따라 다릅니다.
  • B+ 트리는 같음, 범위 검색, 삽입 및 삭제에 모두 효율적입니다. 바이너리 검색과 비교 O(log2N)
  • B+ 트리에서 I/O 비용(데이터가 방대하더라도)은 최대 5를 초과하지 않습니다.

B+ Trees in Parctice

  • 최대 fanout: 200. 일반적인 최소 채우기 계수: 67%(B* 트리라고 함)
    • 평균 fanout = 133
  • 일반적인 용량:
    • 높이 2 : 133^2 = 17,689 검색 키
    • 높이 3 : 133^3 = 2,352,637 검색 키
    • 높이 4 : 133^4 = 312,900,700 검색 키
  • 버퍼 풀의 B+ 트리에서 최상위 수준을 유지할 수 있습니다.
    • 수준 1 = 1페이지 = 8KB
    • 수준 2 = 133페이지 = 1MB
    • 레벨 3 = 133^2(17,689)페이지 = 133MB
  • 3 * 108 레코드의 경우 4개의 I/O만 필요합니다. 두 번째 수준을 미리 가져오면 2개의 I/O만 있으면 충분합니다.

Prefetching

  • B+ 트리의 루트 블록은 최대 한 블록을 차지하므로 메인 메모리로 프리페치(pre-fetch)하는 것이 일반적이다.
  • 때로는 B+ 트리의 두 번째 수준에 있는 모든 블록을 미리 가져오는 것도 가능합니다.
  • 프리페치된 블록을 메인 메모리에 유지함으로써 반복적인 디스크 액세스를 피할 수 있습니다.
  • 총 액세스 수를 1 또는 2로 줄일 수 있습니다.
  • LRU가 B+ 트리에서 프리페칭에 적합합니까?

Deferred Updating of Indexes

  • 여러 B+ 트리 인덱스를 업데이트하려면 많은 노력이 필요하고 응답 시간이 지연되면 온라인 업데이트 작업이 방해를 받습니다.
  • 레코드가 변경된 직후에 모든 인덱스를 업데이트하는 것은 비실용적입니다.
  • 해결책은 인덱스 업데이트를 연기하는 것입니다. 이 업데이트는 시스템이 상대적으로 유휴 상태일 때 낮은 우선 순위로 수행됩니다.
  • 이러한 파일에 대한 검색은 최근 변경 사항을 포함하지 않을 수 있습니다.
  • 그러나 많은 애플리케이션(대량 데이터 분석)이 이 접근 방식을 채택했습니다. 몇 시간이 지나도 문제가 되지 않으므로 이 오류는 중요하지 않습니다.

Key Compression

  • B+ 트리의 높이는 검색 키의 수와 인덱스 항목의 크기에 따라 다릅니다.
  • 인덱스 항목의 크기(키 값, 포인터)는 블록(= fanout)에 맞는 인덱스 항목의 수를 결정합니다.
    • 예를 들어, F = 50, F = 200, F = 1,000
  • B+ 트리의 높이는 fanout에 비례하므로 fanout을 최대화하고 높이를 최소화하는 것이 중요합니다.
  • 인덱스 항목의 검색 키 값은 때때로 길고 가변적입니다. 사람 이름, 주소, 기술 용어 등

  • 긴 검색 키는 공간을 낭비하고 fanout을 줄여 B+ 트리의 높이를 높일 수 있습니다.

  • B+ 트리의 키 값은 올바른 리프를 검색하도록 “안내”하는 데만 사용됩니다. 따라서 압축할 수 있습니다(키 전체를 저장하지 않음).
  • 예를 들어, 이 노드에서 검색을 안내하려면 접두사 ‘Da’와 ‘De’를 저장하는 것으로 충분합니다.

image

  • ‘Da’의 왼쪽 하위 트리에 있는 모든 값은 ‘Da’보다 작고 오른쪽 하위 트리에 있는 모든 값은 ‘Da’보다 크거나 같습니다(‘De’보다 작음).
  • “David Smith”를 압축하는 동안 항목에 대한 이러한 의미 체계가 유지되도록 하는 방법은 무엇입니까?

image

  • “David Smith”의 왼쪽 하위 트리에서 가장 큰 키 값과 “David Smith”의 오른쪽 하위 트리에서 가장 작은 키를 조사해야 합니다. (주변 인덱스 항목인 “Daniel Lee”, “Devara”… 뿐만 아니라!)
  • 이 경우 “Davey Jones”는 “Dav”보다 큽니다. 따라서 “David Smith”는 “Davi”로만 축약될 수 있습니다(“Dav”가 아님).
  • 참고: 삽입/삭제 알고리즘은 적절하게 수정해야 합니다.

Exercise

  • IMDB : 영화배우 검색을 위한 B+ 트리

image

  • 키 압축 후 표시

Bulk Loading

  • 다음 테이블 및 인덱스 생성을 고려하십시오.
CREATE TABLE CUSTOMERS (
  ID    INT
, NAME  VARCHAR(10)
  );

[... INSERT 1,000,000 rows into TABLE CUSTOMERS ...]

CREATE INDEX CUST_IDX ON CUSTOMERS (ID ASC)
  • 마지막 SQL 명령은 B+ 트리 INSERT 알고리즘에 대한 1,000,000번의 호출을 시작해야 합니다.
  • DBMS는 성장하는 B+ 트리를 루트에서 리프 페이지까지 1,000,000번 탐색합니다.
  • 많은 레코드 컬렉션이 있고 일부 필드에 B+ 트리를 생성하려는 경우 레코드를 반복적으로 삽입하여 그렇게 하는 것은 매우 느립니다. O(N*logFN)
  • 대부분의 DBMS 설치는 위와 같은 작업 비용을 줄이기 위해 대량 로딩 유틸리티를 제공합니다.
    • 데이터 파일에서 키 k가 있는 각 레코드에 대해 인덱스 리프 항목 k* 블록의 정렬된 목록을 만듭니다. (이것이 반드시 데이터 자체를 정렬한다는 의미는 아닙니다.
    • 빈 인덱스 루트 블록을 할당하고 p0 블록 포인터가 정렬된 k* 항목의 첫 번째 블록을 가리키도록 합니다.
    • 각 리프 레벨 블록 p에 대해 인덱스 항목을 삽입합니다. <p의 최소 키, p에 대한 포인터> 리프 수준 바로 위의 가장 오른쪽 인덱스 노드로 이동합니다. 가장 오른쪽 노드는 왼쪽에서 오른쪽으로 채워집니다. 분할은 리프 수준에서 루트까지의 가장 오른쪽 경로에서만 발생합니다.

Building B+ Tree

  • 초기화: 모든 데이터 항목을 정렬한 다음 새(루트) 블록의 첫 번째 리프 블록에 대한 포인터를 삽입합니다.

image

  • 정렬된 데이터 항목의 각 블록에 대해 루트 블록에 하나의 항목을 추가합니다. 새 항목은 다음으로 구성됩니다.

<블록의 가장 낮은 키 값, 블록에 대한 포인터>

image

  • 리프 블록에 대한 인덱스 항목은 항상 리프 수준 바로 위의 맨 오른쪽 인덱스 블록에 입력됩니다. 이것이 채워지면 분할됩니다.
  • 분할은 루트에서 리프 수준까지 가장 오른쪽 경로에서만 발생합니다.

image

image

Analysis

  • 대량 로딩 비용을 고려해 보겠습니다. R이 레코드를 포함하는 블록의 수이고 E가 데이터 항목을 포함하는 블록의 수라고 가정합니다. R > E
    • 인덱스에 삽입할 데이터 항목을 생성합니다. 기록을 스캔하고 해당 데이터 항목을 작성하십시오. 비용은 (R + E)
    • 데이터 항목 정렬 비용은 O(E * logB-1E) : 3E
    • 정렬된 데이터 항목에서 인덱스를 생성합니다. 인덱스에 항목을 삽입하는 것은 모든 인덱스 페이지를 작성하는 데 드는 비용일 뿐입니다.

Standard Insertion vs Bulk Loading

  • Standard Insertion
    • 느리다
    • 리프의 순차적 저장을 제공하지 않습니다.
  • Bulk Loading
    • 동시성 제어에 대한 장점이 있습니다.
    • 빌드 중 I/O가 적습니다.
    • 리프는 순차적으로 저장됩니다(물론 연결됨).
    • 모든 리프 블록을 완전히 채울 수 있습니다.

요약

  • B+ 트리 인덱스는 검색에 이상적이며 업데이트에도 좋습니다.
  • B+ 트리는 동적 구조입니다.
    • 삽입/삭제는 트리 높이 균형을 유지합니다. O(logFN) 비용.
    • 높은 fanout(F)은 깊이가 거의 3 또는 4를 넘지 않음을 의미합니다.
    • 정렬된 파일을 유지 관리하는 것보다 거의 항상 낫습니다.
  • 키 압축은 fanout을 증가시키고 높이를 줄입니다.
  • 대량 로드는 대규모 데이터 세트에서 B+ 트리를 생성하기 위한 반복 삽입보다 훨씬 빠를 수 있습니다.
  • 다양성 때문에 데이터베이스 관리 시스템에서 가장 널리 사용되는 인덱스입니다. DBMS의 가장 최적화된 구성 요소 중 하나입니다.
  • B+ Tree: http://www.youtube.com/watch?v=UQxHh2Mpwno

댓글남기기

참고