B 데이터 구조의 TREE: 검색, 삽입, 삭제 Opera예시

B-트리에 대한 규칙

B_Tree 생성에 있어서 중요한 규칙은 다음과 같습니다.

• 모든 리프는 동일한 레벨에서 생성됩니다.
• B-Tree는 "순서"(프로그래머와 같은 외부 행위자에 의해 지정됨)라고도 불리는 정도에 따라 결정됩니다.

  m

  앞으로. 의 가치

  m

  데이터가 주로 저장된 디스크의 블록 크기에 따라 달라집니다.

• 노드의 왼쪽 하위 트리는 하위 트리의 오른쪽보다 작은 값을 갖습니다. 즉, 노드도 왼쪽에서 오른쪽으로 오름차순으로 정렬됩니다.
• 하위 노드, 루트 노드 및 해당 하위 노드가 포함할 수 있는 최대 하위 노드 수는 다음 공식으로 계산됩니다.

  m – 1

  예 :

  m = 4
  max keys: 4 – 1 = 3
  

• 루트를 제외한 모든 노드에는 다음의 최소 키가 포함되어야 합니다.

  [m/2]-1

  예 :

  m = 4
  min keys: 4/2-1 = 1
  

• 노드가 가질 수 있는 최대 자식 노드 수는 해당 차수와 같습니다.

  m

• 노드가 가질 수 있는 최소 자식 수는 차수의 절반, 즉 m/2입니다(상한 값이 사용됨).
• 노드의 모든 키는 오름차순으로 정렬됩니다.

B-Tree를 사용하는 이유

B-Tree를 사용하는 이유는 다음과 같습니다.

• 디스크에 대한 읽기 수를 줄입니다.
• B 트리는 디스크 크기에 따라 크기(즉, 하위 노드 수)를 조정하여 쉽게 최적화할 수 있습니다.
• 대용량 데이터를 처리하기 위해 특별히 고안된 기술입니다.
• 데이터베이스와 파일 시스템에 유용한 알고리즘입니다.
• 대규모 데이터 블록을 읽고 쓸 때 선택하는 좋은 선택

B트리의 역사

• 데이터는 블록 단위로 디스크에 저장되며, 이 데이터를 메인 메모리(또는 RAM)로 가져올 때 데이터 구조라고 합니다.
• 방대한 데이터의 경우, 디스크에서 하나의 레코드를 검색하려면 전체 디스크를 읽어야 합니다. 이렇게 하면 디스크 접근 빈도가 높아지고 데이터 크기 때문에 시간이 늘어나고 주 메모리 사용량도 늘어납니다.
• 이를 극복하기 위해 레코드가 상주하는 블록을 기반으로 레코드의 레코드 참조를 저장하는 인덱스 테이블이 생성됩니다. 이를 통해 시간과 메모리 소비가 대폭 줄어듭니다.
• 방대한 데이터를 보유하고 있으므로 다단계 인덱스 테이블을 생성할 수 있습니다.
• 다단계 인덱스는 데이터를 자체 균형 방식으로 정렬하기 위해 B 트리를 사용하여 설계할 수 있습니다.

검색 Opera기

검색 작업은 B 트리에서 가장 간단한 작업입니다.

다음 알고리즘이 적용됩니다:

• 키(값)를 "k"로 검색하도록 합니다.
• 루트부터 검색을 시작하여 재귀적으로 아래로 탐색합니다.
• k가 루트 값보다 작으면 왼쪽 하위 트리를 검색하고, k가 루트 값보다 크면 오른쪽 하위 트리를 검색합니다.
• 노드에 k가 발견되면 간단히 노드를 반환합니다.
• k가 노드에서 발견되지 않으면 더 큰 키를 가진 하위 항목으로 이동합니다.
• k가 트리에서 발견되지 않으면 NULL을 반환합니다.

끼워 넣다 Opera기

B 트리는 자체 균형 트리이므로 임의의 노드에 키를 강제로 삽입할 수 없습니다.

다음 알고리즘이 적용됩니다:

• 검색 작업을 실행하여 적절한 삽입 위치를 찾으세요.
• 적절한 위치에 새 키를 삽입합니다. 단, 노드에 이미 최대 키 수가 있는 경우 다음을 수행하세요.
• 노드는 새로 삽입된 키와 함께 중간 요소에서 분할됩니다.
• 중간 요소는 다른 두 하위 노드의 상위 요소가 됩니다.
• 노드는 키를 오름차순으로 다시 정렬해야 합니다.

TIP	삽입 알고리즘에 대한 설명으로 틀린 것은 다음과 같습니다. 노드가 가득 차서 분할되고 새 값이 삽입됩니다.

위의 예에서:

• 노드에서 키에 대한 적절한 위치를 검색합니다.
• 대상 노드에 키를 삽입하고 규칙을 확인합니다.
• 삽입 후 노드에 최소 키 수인 1보다 많은 키가 있습니까? 이 경우에는 그렇습니다. 다음 규칙을 확인하세요.
• 삽입 후 노드에 최대 키 수인 3개보다 많은 키가 있습니까? 이 경우에는 그렇지 않습니다. 이는 B Tree가 어떤 규칙도 위반하지 않고 삽입이 완료되었음을 의미합니다.

위의 예에서:

• 노드가 최대 키 수에 도달했습니다.
• 노드가 분할되고 가운데 키가 나머지 두 노드의 루트 노드가 됩니다.
• 키 개수가 짝수인 경우 왼쪽 바이어스 또는 오른쪽 바이어스에 의해 중간 노드가 선택됩니다.

위의 예에서:

• 노드에 최대 키 미만이 있습니다.
• 1 옆에 3이 삽입되었으나 오름차순 규칙을 위반했습니다.
• 이 문제를 해결하기 위해 키가 정렬됩니다.

마찬가지로 13과 2는 노드에 대한 최대 키 규칙보다 적게 충족되므로 노드에 쉽게 삽입될 수 있습니다.

위의 예에서:

• 노드에는 최대 키와 동일한 키가 있습니다.
• 키가 대상 노드에 삽입되었지만 최대 키 규칙을 위반합니다.
• 대상 노드가 분할되고 왼쪽 바이어스에 의한 가운데 키가 이제 새 하위 노드의 상위가 됩니다.
• 새 노드는 오름차순으로 정렬됩니다.

마찬가지로 위의 규칙과 사례를 바탕으로 나머지 값도 B Tree에 쉽게 삽입할 수 있습니다.

. Opera기

삭제 작업은 삽입 및 검색 작업보다 규칙이 더 많습니다.

다음 알고리즘이 적용됩니다:

• 검색 작업을 실행하고 노드에서 대상 키를 찾습니다.
• 다음 섹션에서 설명한 대로 대상 키의 위치를 ​​기준으로 세 가지 조건이 적용됩니다.

대상 키가 리프 노드에 있는 경우

• Target 최소 키보다 더 많은 리프 노드에 있습니다.
• 이를 삭제해도 B Tree의 속성을 침해하지 않습니다.
• Target 리프 노드에 있고 최소 키 노드가 있습니다.
• 이를 삭제하면 B Tree의 속성에 위배됩니다.
• Target 노드는 바로 왼쪽 노드 또는 바로 오른쪽 노드(형제)에서 키를 빌릴 수 있습니다.
• 동생이 말하겠지 예 최소 키 개수보다 많은 경우
• 키는 상위 노드에서 빌려오고, 최대값은 상위 노드로 전송되며, 상위 노드의 최대값은 대상 노드로 전송되고, 대상 값은 제거됩니다.
• Target 리프 노드에 있지만 형제 중 최소 키 수보다 많은 키가 없습니다.
• 키 검색
• 형제 및 최소 상위 노드와 병합
• 이제 총 키가 최소보다 많아집니다.
• 대상 키는 상위 노드의 최소값으로 대체됩니다.

대상 키가 내부 노드에 있는 경우

• 순서대로 선행자 또는 순서대로 후임자를 선택합니다.
• 순서대로 전임자의 경우 왼쪽 하위 트리에서 최대 키가 선택됩니다.
• 순차 후속 항목의 경우 오른쪽 하위 트리의 최소 키가 선택됩니다.
• 대상 키의 순차 선행 키가 최소 키보다 많은 경우에만 대상 키를 순차 선행 키의 최대값으로 대체할 수 있습니다.
• 대상 키의 순서대로 선행 키가 최소 키보다 많지 않은 경우 순서대로 후속 작업의 최소 키를 찾습니다.
• 대상 키의 순서대로 선행 키와 후속 키가 모두 최소 키보다 작은 경우 선행 키와 후속 키를 병합합니다.

대상 키가 루트 노드에 있는 경우

• 순서대로의 선행 하위 트리의 최대 요소로 교체
• 삭제 후 대상의 최소 키 미만인 경우 대상 노드는 형제의 부모를 통해 형제로부터 최대 값을 빌립니다.
• 부모의 최대값은 대상에 의해 사용되지만 노드는 형제의 최대값을 사용합니다.

이제 예를 들어 삭제 작업을 알아보겠습니다.

위의 다이어그램은 B-트리에서 삭제 작업의 다양한 사례를 보여줍니다. 이 B-트리는 5차이며, 이는 모든 노드가 가질 수 있는 최소 자식 노드 수가 3이고 모든 노드가 가질 수 있는 최대 자식 노드 수가 5임을 의미합니다. 반면 모든 노드가 가질 수 있는 최소 및 최대 키 수는 각각 2와 4입니다.

위의 예에서:

• 대상 노드에 삭제할 대상 키가 있습니다.
• 대상 노드에 최소 키보다 많은 키가 있습니다.
• 키를 삭제하면 됩니다.

위의 예에서:

• 대상 노드에는 최소 키와 동일한 키가 있으므로 조건을 위반하므로 직접 삭제할 수 없습니다.

다음 다이어그램은 이 키를 삭제하는 방법을 설명합니다.

• 대상 노드는 직계 형제(이 경우에는 순서대로의 후속 노드(오른쪽 형제)가 없기 때문에 순서대로의 전임자(왼쪽 형제))로부터 키를 빌립니다.
• 중위 선행 노드의 최대값은 상위 노드로 전송되고, 상위 노드는 최대값을 대상 노드로 전송합니다(아래 다이어그램 참조).

다음 예제는 값이 필요한 키를 순서대로 나열된 후속 키에서 삭제하는 방법을 보여줍니다.

• 대상 노드는 직계 형제, 이 경우 순서대로의 후속 노드(오른쪽 형제)로부터 키를 빌립니다. 왜냐하면 순서대로의 전임자(왼쪽 형제)가 최소 키와 동일한 키를 갖기 때문입니다.
• 순서대로 계승되는 노드의 최소값은 상위 노드로 전달되고, 상위 노드는 최대값을 대상 노드로 전달합니다.

아래 예에서 대상 노드에는 대상 노드에 키를 제공할 수 있는 형제가 없습니다. 그러므로 병합이 필요합니다.

해당 키를 삭제하는 절차를 참조하세요.

• 부모 키와 함께 직계 형제 노드와 대상 노드를 병합합니다.
• 두 병합 노드 사이에 있는 형제 노드의 키가 선택됩니다.
• 병합된 노드에서 대상 키 삭제

. Opera의사 코드

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

산출:

B-Tree에서 가장 큰 요소가 삭제됩니다.

요약

• B 트리는 디스크에서 데이터를 더 효과적으로 검색, 삽입 및 삭제하기 위한 자체 균형형 데이터 구조입니다.
• B 트리는 지정된 정도에 따라 규제됩니다.
• B 트리 키와 노드는 오름차순으로 정렬됩니다.
• B 트리의 검색 작업은 가장 간단한 작업으로, 항상 루트에서 시작하여 대상 키가 노드 값보다 크거나 작은지 확인합니다.
• B 트리의 삽입 작업은 다소 세부적입니다. 먼저 대상 키에 대한 적절한 삽입 위치를 찾고, 이를 삽입하고, 다양한 경우에 대해 B 트리의 유효성을 평가한 다음, 이에 따라 B 트리 노드를 재구성합니다.
• B 트리의 삭제 연산은 먼저 삭제할 대상 키를 검색하여 삭제한 후, 대상 노드의 최소, 최대 키, 형제 노드, 부모 노드 등 여러 가지 사례를 기반으로 유효성을 평가합니다.