B+ TREE : 검색, 삽입, 삭제 Opera설명 예
B+ 트리란 무엇입니까?
A B+트리 주로 여러 레벨에서 동적 인덱싱을 구현하는 데 사용됩니다. B-트리와 비교했을 때, B+트리는 트리의 리프 노드에만 데이터 포인터를 저장하므로 검색 프로세스가 더 정확하고 빠릅니다.
B+ 트리의 규칙
B+ Tree의 필수 규칙은 다음과 같습니다.
- 잎은 데이터 기록을 저장하는 데 사용됩니다.
- 이는 트리의 내부 노드에 저장됩니다.
- 대상 키 값이 내부 노드보다 작으면 바로 왼쪽에 있는 지점을 따릅니다.
- 대상 키 값이 내부 노드보다 크거나 같으면 바로 오른쪽에 있는 지점을 따릅니다.
- 루트에는 최소 XNUMX명의 자식이 있습니다.
B+트리를 사용하는 이유
B+ Tree를 사용하는 이유는 다음과 같습니다.
- 키는 주로 적절한 Leaf로 안내하여 검색을 돕는 데 사용됩니다.
- B+ 트리는 트리의 증가와 감소를 관리하기 위해 “채우기 요소(Fill Factor)”를 사용합니다.
- B+ 트리에서는 내부 노드와 관련된 데이터가 없기 때문에 수많은 키가 메모리 페이지에 쉽게 배치될 수 있습니다. 따라서 리프 노드에 있는 트리 데이터에 빠르게 액세스합니다.
- 모든 요소에 대한 포괄적인 전체 스캔은 B+ 트리의 모든 리프 노드가 서로 연결되어 있기 때문에 단 하나의 선형 패스만 필요한 트리입니다.
B+ 트리 대 B 트리
B+ 트리와 B 트리의 주요 차이점은 다음과 같습니다.
B+트리 | B 트리 |
---|---|
검색 키는 반복될 수 있습니다. | 검색 키는 중복될 수 없습니다. |
데이터는 리프 노드에만 저장됩니다. | 리프 노드와 내부 노드 모두 데이터를 저장할 수 있습니다. |
리프 노드에 저장된 데이터는 검색을 더욱 정확하고 빠르게 만듭니다. | Leaf와 내부 노드에 데이터가 저장되어 있어 검색 속도가 느립니다. |
요소는 리프 노드에서만 제거되므로 삭제는 어렵지 않습니다. | 요소 삭제는 복잡하고 시간이 많이 걸리는 프로세스입니다. |
연결된 리프 노드는 검색을 효율적이고 빠르게 만듭니다. | 리프 노드를 연결할 수 없습니다. |
검색 Opera기
B+ Tree에서 검색은 실행하고 빠르고 정확한 결과를 얻는 가장 쉬운 절차 중 하나입니다.
다음 검색 알고리즘이 적용됩니다.
- 필요한 레코드를 찾으려면 다음을 실행해야 합니다. 이진 검색 트리에서 사용 가능한 레코드에 대해
- 검색 키와 정확히 일치하는 경우 해당 레코드가 사용자에게 반환됩니다.
- 검색을 통해 부모 노드, 현재 노드 또는 리프 노드에서 정확한 키를 찾을 수 없는 경우 "키를 찾을 수 없음" 메시지가 사용자에게 표시됩니다.
- 보다 정확하고 나은 결과를 얻기 위해 검색 프로세스를 다시 실행할 수 있습니다.
검색 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%가 저장을 위해 새 리프로 이동됩니다.
- 새 리프의 부모는 최소 키 값 및 트리의 새 위치와 정확하게 연결됩니다.
- 완전히 활용되는 경우 상위 노드를 더 많은 위치로 분할합니다.
- 이제 더 나은 결과를 위해 중앙 키가 해당 Leaf의 최상위 노드와 연결됩니다.
- 최상위 노드를 찾을 수 없을 때까지 위 단계에서 설명한 프로세스를 계속 반복합니다.
끼워 넣다 Opera알고리즘
1. Even 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을 추가하십시오.
- 이제 트리의 오른쪽 계층이 생성되고 오른쪽의 키-값 노드에 대해 값보다 크거나 같은 적용 가능한 규칙을 염두에 두고 나머지 데이터 값이 그에 따라 조정됩니다.
. Opera기
B+ 트리의 삭제 절차의 복잡성은 삽입과 검색 기능의 복잡성을 능가합니다.
다음 알고리즘은 B+ 트리에서 요소를 삭제할 때 적용할 수 있습니다.
- 먼저 키와 포인터를 보유하고 있는 트리에서 리프 항목을 찾아야 합니다. , 리프가 레코드 삭제의 정확한 조건을 충족하는 경우 트리에서 리프 항목을 삭제합니다.
- 리프 노드가 절반만 채워진 만족스러운 요소를 충족하는 경우 작업이 완료됩니다. 그렇지 않으면 리프 노드는 최소한의 항목을 갖게 되어 삭제할 수 없습니다.
- 오른쪽과 왼쪽에 연결된 다른 노드는 항목을 비운 다음 리프로 이동할 수 있습니다. 이러한 기준이 충족되지 않으면 트리 계층 구조에서 리프 노드와 연결된 노드를 결합해야 합니다.
- 리프 노드를 오른쪽이나 왼쪽의 이웃과 병합하면 리프 노드 또는 최상위 노드를 가리키는 연결된 이웃의 값 항목이 삭제됩니다.
위의 예는 특정 순서의 B+ 트리에서 요소를 제거하는 절차를 보여줍니다.
- 첫째, 삭제할 요소의 정확한 위치가 트리에서 식별됩니다.
- 여기서 삭제할 요소는 인덱스 배치가 아닌 리프 수준에서만 정확하게 식별할 수 있습니다. 따라서 최소 키 값인 삭제 규칙에 영향을 주지 않고 요소를 삭제할 수 있습니다.
- 위의 예에서는 트리에서 31을 삭제해야 합니다.
- Index와 Leaf에서 31의 인스턴스를 찾아야 합니다.
- Index 및 Leaf 노드 수준 모두에서 31을 사용할 수 있음을 알 수 있습니다. 따라서 두 인스턴스 모두에서 삭제합니다.
- 하지만 우리는 42를 가리키는 인덱스를 채워야 합니다. 이제 25세 미만의 오른쪽 자식을 보고 최소값을 가져와 인덱스로 배치하겠습니다. 따라서 존재하는 유일한 값인 42가 인덱스가 됩니다.
. Opera알고리즘
1) Start at the root and go up to 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 및 해당 상위 노드의 값을 조정하기 위해 형제로부터 키를 빌려옵니다.
요약
- B+ Tree는 자기 균형을 유지하는 나무입니다. 데이터 구조 데이터에 대한 정확하고 빠른 검색, 삽입 및 삭제 절차를 실행하기 위해
- 연결된 트리 구조를 통해서 효율적으로 전체 데이터나 부분 데이터를 쉽게 검색할 수 있습니다.
- B+ 트리 구조는 저장된 레코드 수의 증가/감소에 따라 증가하고 감소합니다.
- 리프 노드에 데이터를 저장하고 그에 따라 내부 노드를 분기하면 트리 높이가 현저히 줄어들어 디스크 입출력 작업이 줄어들고, 궁극적으로 저장 장치에서 소모하는 공간이 대폭 줄어듭니다.