B+ 트리: 검색, 삽입 및 삭제 OperaTIONS

B+ 트리란 무엇입니까?

A B+트리 B+ 트리는 주로 다단계 동적 인덱싱을 구현하는 데 사용됩니다. B- 트리와 비교했을 때, B+ 트리는 데이터 포인터를 트리의 리프 노드에만 저장하므로 검색 과정이 더 정확하고 빠릅니다.

B+ 트리의 규칙

다음은 B+ 트리 관리를 위한 필수 규칙입니다.

• 잎은 데이터 기록을 저장하는 데 사용됩니다.
• 기록은 트리의 내부 노드에 저장됩니다.
• 대상 키 값이 내부 노드 값보다 작으면 바로 왼쪽에 있는 포인터를 따라갑니다.
• 대상 키 값이 내부 노드보다 크거나 같으면 해당 노드 바로 오른쪽에 있는 포인터를 따라갑니다.
• 루트에는 최소 XNUMX명의 자식이 있습니다.

B+트리를 사용하는 이유

B+ 트리를 사용하는 이유는 다음과 같습니다.

• 키는 주로 올바른 페이지를 가리켜 검색을 돕기 위해 사용됩니다.
• B+ 트리는 "채움률"을 사용하여 트리의 증가 및 감소를 관리합니다.
• B+ 트리에서는 내부 노드와 관련된 데이터가 없기 때문에 수많은 키가 메모리 페이지에 쉽게 배치될 수 있습니다. 따라서 리프 노드에 있는 트리 데이터에 빠르게 액세스합니다.
• B+ 트리의 모든 리프 노드는 서로 연결되어 있기 때문에 모든 요소를 ​​포괄적으로 전체 스캔하는 데에는 단 한 번의 선형 패스만 필요합니다.

B+ 트리 대 B 트리

다음은 B+ 트리와 B 트리의 주요 차이점입니다.

검색 Opera기

B+ 트리에서 검색은 실행하기 가장 쉬운 절차 중 하나이며 빠르고 정확한 결과를 제공합니다.

다음 검색 알고리즘이 적용됩니다.

• 필요한 레코드를 찾으려면 다음을 실행해야 합니다. 이진 검색 트리에서 사용 가능한 레코드에 대해
• 검색 키와 정확히 일치하는 경우 해당 레코드가 사용자에게 반환됩니다.
• 검색을 통해 부모 노드, 현재 노드 또는 리프 노드에서 정확한 키를 찾을 수 없는 경우 "키를 찾을 수 없음" 메시지가 사용자에게 표시됩니다.
• 보다 정확하고 나은 결과를 얻기 위해 검색 프로세스를 다시 실행할 수 있습니다.

검색 Opera알고리즘

1. Call the binary search method on the records in the B+ Tree.
2. If the search parameters match the exact key
       The accurate result is returned and displayed to the user
   Else, if the node being searched is the current and the exact key is not found by the algorithm
       Display the statement "Recordset cannot be found."

출력: 정확한 키와 일치하는 레코드 집합이 사용자에게 표시됩니다. 그렇지 않으면 실패한 시도가 사용자에게 표시됩니다.

끼워 넣다 Opera기

다음 알고리즘은 삽입 작업에 적용할 수 있습니다.

• 노드에 있는 요소의 50%가 저장을 위해 새 리프로 이동됩니다.
• 새로운 리프 노드의 부모 노드는 최소 키 값과 트리의 새로운 위치에 정확하게 연결됩니다.
• 완전히 활용되는 경우 상위 노드를 더 많은 위치로 분할합니다.
• 더 나은 결과를 얻기 위해 중앙 키는 해당 리프의 최상위 노드와 연결됩니다.
• 최상위 노드를 찾을 수 없을 때까지 위 단계에서 설명한 프로세스를 계속 반복합니다.

끼워 넣다 Opera알고리즘

1. If inserting at least 1 entry into the leaf container does not make it full, then add the record.
2. Else, divide the node into more locations to fit more records.
   a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the tree.
   b. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.
   c. Divide the top-level node if it gets full of keys and addresses.
      i. Similarly, insert a key in the center of the top-level node in the hierarchy of the Tree.
   d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore.
3. Build a new top-level root node of 1 key and 2 indicators.

출력: 알고리즘은 요소를 결정하고 필요한 리프 노드에 성공적으로 삽입합니다.

위의 B+ Tree 샘플 예제는 아래 단계에서 설명됩니다.

• 먼저, 3개의 노드가 있고, 처음 3개의 요소인 1, 4, 6이 각 노드의 적절한 위치에 추가됩니다.
• 데이터 계열의 다음 값은 12이며, 이 값을 트리 구조에 포함시켜야 합니다.
• 이를 위해 노드를 분할하고 포인터 요소로 6을 추가합니다.
• 이제 트리의 오른쪽 계층 구조가 생성되고 나머지 데이터 값은 kee에 의해 그에 따라 조정됩니다.ping 오른쪽에 있는 키-값 노드에 대해 '같음' 또는 '큼'과 같은 적용 가능한 규칙을 염두에 두십시오.

. Opera기

B+ 트리의 삭제 절차의 복잡성은 삽입과 검색 기능의 복잡성을 능가합니다.

다음 알고리즘은 B+ 트리에서 요소를 삭제할 때 적용할 수 있습니다.

• 먼저, 키와 포인터를 보유하고 있는 트리의 리프 항목을 찾은 다음, 해당 리프 항목이 레코드 삭제 조건을 정확히 충족하는 경우 트리에서 해당 리프 항목을 삭제해야 합니다.
• 리프 노드가 최소 입력값인 절반만 채워져 있어도 삭제 작업이 완료됩니다. 그렇지 않으면 리프 노드는 최소 입력값만 충족하므로 삭제할 수 없습니다.
• 좌우에 연결된 다른 노드들은 모든 항목을 비운 후 리프 노드로 이동시킬 수 있습니다. 만약 이러한 조건이 충족되지 않으면, 리프 노드와 연결된 노드를 트리 계층 구조에서 결합해야 합니다.
• 리프 노드가 오른쪽 또는 왼쪽 이웃 노드와 병합될 때, 리프 노드 또는 최상위 노드를 가리키는 연결된 이웃 노드의 값 항목이 삭제됩니다.

위 예시는 특정 차수의 B+ 트리에서 요소를 제거하는 절차를 보여줍니다.

• 첫째, 삭제할 요소의 정확한 위치가 트리에서 식별됩니다.
• 여기서 삭제할 요소는 인덱스 위치가 아닌 리프 레벨에서만 정확하게 식별할 수 있습니다. 따라서 삭제 규칙에 영향을 주지 않고 요소를 삭제할 수 있으며, 이것이 바로 최소 키의 가치입니다.

• 위의 예에서는 트리에서 31을 삭제해야 합니다.
• 인덱스와 리프에서 숫자 31이 나타나는 위치를 찾아야 합니다.
• 31이라는 값이 인덱스 노드와 리프 노드 모두에서 사용 가능함을 알 수 있습니다. 따라서 두 인스턴스 모두에서 해당 값을 삭제합니다.
• 하지만 우리는 42를 가리키는 인덱스를 채워야 합니다. 이제 25 아래에 있는 오른쪽 자식 요소를 살펴보고 최솟값을 가져와 인덱스로 사용하겠습니다. 42는 유일하게 존재하는 값이므로 인덱스가 됩니다.

. Opera알고리즘

1) Start at the root and go up to the leaf node containing the key K.
2) Find the node n on the path from the root to the leaf node containing K.
   A. If n is root, remove K
      a. if root has more than one key, done
      b. if root has only K
         i)  if any of its child nodes can lend a node
             Borrow key from the child and adjust child links
         ii) Otherwise merge the children nodes. It will be a new root
      c. If n is an internal node, remove K
         i)  If n has at least ceil(m/2) keys, done!
         ii) If n has less than ceil(m/2) keys,
             If a sibling can lend a key,
                Borrow key from the sibling and adjust keys in n and the parent node
                Adjust child links
             Else
                Merge n with its sibling
                Adjust child links
      d. If n is a leaf node, remove K
         i)  If n has at least ceil(M/2) elements, done!
             In case the smallest key is deleted, push up the next key
         ii) If n has less than ceil(m/2) elements
             If the sibling can lend a key
                Borrow key from a sibling and adjust keys in n and its parent node
             Else
                Merge n and its sibling
                Adjust keys in the parent node

출력: 키 "K"가 삭제되고, 필요한 경우 n과 그 부모 노드의 값을 조정하기 위해 형제 노드에서 키를 빌려옵니다.

자주 묻는 질문