[자료구조] 탐색 트리 : 2-3 트리, B 트리에 관하여

2-3 트리

 

2-3 트리 정의

 

• 2-3 트리는 내부 노드의 차수가 2 또는 3인 균형 탐색 트리
• 차수가 2인 노드는 2-노드라고 부르고, 차수가 3인 노드는 3-노드라고 부른다.
• 2-노드는 1개의 키를 가지며, 3-노드는 2개의 키를 가진다.
• 2-3 트리는 루트로부터 각 이파리까지 경로의 길이가 같고, 모든 이파리가 같은 층에 있는 완전 균형 트리이다.
• 2-3 트리가 2-노드들로만 구성되면 포화 이진 트리와 동일한 형태를 가진다.

 

 

• 2-3 트리에서 중위 순회를 수행하면 키들이 정렬된다.

 

2-3 트리의 연산

 

 

 

탐색 연산

루트에서 시작하여 방문한 노드의 키들과 탐색하는 키를 비교하며 다음 레벨의 노드를 탐색한다.

 

 

삽입 연산

 

먼저, 탐색과 같은 과정을 거쳐 새로운 키가 삽입될 이파리를 찾아야 한다.

이파리를 찾았다면 이제 그 이파리가 어떤 모양의 노드인지를 구분해야 한다.

 

 

삽입될 이파리가 만약 2-노드라면 그 노드에 새 키를 삽입한 후, 종료하면 된다.

 

 

이파리가 3-노드라면 조금 더 복잡해 지는데, 이 노드에 있는 2개의 키와 새 키를 비교하여 중간 값이 되는 키를 부모로 올려 보내고, 남은 2개의 키를 각각 별도의 노드에 저장한다. 이를 분리 연산이라고 한다.

 

 

50을 삽입하는 예시를 보자.

 

 

 

 

 

삽입하려는 50은 탐색 과정과 마찬가지로 이파리를 찾아간다.

이때 비교 대상은 해당 이파리의 키인 80과 90 그리고 삽입 대상인 50이다.

이 중간 값은 상위 노드로 올라가면 아래와 같은 모양새를 보인다.

이러한 모양새는 2-3 트리의 정의 조건을 만족하므로 따로 수정해 줄 필요가 없다.

 

 

 

 

만약 삽입하는 이파리가 3-노드인 경우 (분리 연산 + 차수 증가)를 해주어야 한다.

 

 

 

 

삭제 연산

 

• 삭제 연산은 항상 이파리에서 이루어진다.
• 만약 삭제할 키가 있는 노드가 이파리가 아니라면 이진 탐색 트리의 삭제와 유사하게 중위 선행자 혹은 중위 후속자와 교환한 후에 이파리에서 실질적인 삭제를 수행한다.
• 이때, 이동(Transfer)연산과 통합(Fusion)연산을 사용한다.

 

 

이동연산은 키가 삭제되어 노드가 empty가 되면 이 노드의 형제와 부모의 도움을 받아 1개의 키를 empty 노드로 이동한다. 

 

사실 그림을 보면 간단하게 이해할 수 있다.

 

 

 

 

 

2-3 노드의 정의에 맞도록 위치를 이동시켜주면 되는 것이다.

 

 

통합 연산은 노드가 empty인데 이동 연산이 불가능한 경우 사용한다.

Empty 노드와 그의 형제를 1개의 노드로 통합하고, empty 노드와 그의 형제의 분기점 역할을 하던 부모의 키를 통합된 노드로 끌어내려 저장한다.

즉, 통합 연산과 분리 연산은 상호 역(Reverse) 연산 관계인 것이다.

 

 

 

 

 

간단하게 말해 이동 연산이 안되는 경우 2-3 노드의 조건을 만족 시켜주기 위해 부모 키를 끌여내려 합치는 것이다.

  

 

 

 

이제 제일 중요한 삭제 연산의 경우를 살펴보자.

 

 

 

제일 중요한 것은 모든 삭제 연산은 이파리에서 실시된다는 것이다.

위와 같이 삭제 연산을 수행하더라도 트리의 모양을 유지한다면 딱히 다른 연산을 해줄 필요가 없다.

 

 

 

 

 

 

만약 삭제하려는 노드가 다음과 같이 루트 노드라고 해보자.

모든 삭제 연산은 이파리에서 수행해야 하므로 해당 루트 노드와 이파리에 있는 노드를 교환해 줄 필요가 있다.

교환 후, 이동 연산을 통해 모양새를 유지시킬 수 있도록 한다.

 

 

 

 

 

마지막으로 비슷한 경우지만, 이동 연산이 불가능해 통합 연산을 수행하는 경우이다.

위 경우는 좌우 서브트리의 균형이 맞지 않아 통합 연산을 두 번 적용한다.

 

 

 

즉, 2-3 노드의 삭제 연산은 항상 이파리에서 일어나고, 이를 위해 이동/통합 연산을 수행한다.

 

 

 

2-3 트리의 수행시간

 

• 2-3 트리의 탐색, 삽입, 삭제 연산은 각각 트리 높이에 비례하는 시간을 소요한다.
  • 각 연산은 루트부터 이파리까지 탐색하고, 삽입이나 삭제의 경우 분리나 통합 연산을 수행하며 다시 루트까지 올라가기 때문이다.
• 개별적인 분리 연산이나 통합 연산은 트리의 지역적인 부분에서 실시 되므로 O(1)의 시간이 소요된다.
• 2-3 트리가 가장 높은 경우는 모든 노드가 2-노드인 경우이며 이 경우 트리의 높이는 log2(n+1)이다.

• 트리의 모든 노드가 3-노드이면 트리의 높이가 최소이며 트리의 높이는 log3n = 0.63log2n이다.
• 2-3 탐색, 삽입, 삭제 연산의 수행 시간은 각각 O(logn)이다.
• 2-3 트리는 이진 탐색 트리에 비해 우수한 성능을 보이나, 실제로 구현하기 매우 어렵다!

 

 

 

---

 

 

 

2-3-4 트리

• 2-3 트리를 확장한 2-3-4 트리는 노드가 자식을 4개까지 가질 수 있는 완전 균형 트리이다.
• 장점은 2-3 트리보다 높이가 낮아 빠른 탐색, 삽입, 삭제 연산이 수행가능하다.
• 삽입과 삭제 연산은 이론적으로 2-3 트리의 수행시간과 동일한 O(log2n)

 

 

 

---

 

 

 

B-트리

• 다수의 키를 가진 노드로 구성되어 다방향 탐색이 가능한 균형 트리
• 2-3 트리는 B-트리의 일종으로 노드에 키가 2개까지 있을 수 있는 트리이다.
• B-트리는 대용량의 데이터를 위해 고안되어 주로 데이터베이스에서 사용된다.

 

즉, 노드에 수백, 수천 개의 키를 저장하여 트리의 높이를 낮추자는 것이다!

 

 

B트리는 아래와 같은 특징을 가진다.

 

차수가 M인 B-트리는 다방향 탐색 트리로서 모든 이파리는 같은 동일한 깊이를 갖는다.

각 노드(루트 제외)의 자식 수는 M/2(소수면 올림) 이상 M이하이다.

루트의 자식 수는 2 이상이다.

 

 

 

탐색 연산

 

• B-트리에서의 탐색은 루트로부터 시작한다.
• 방문한 각 노드에서는 탐색하는 키와 노드의 키들을 비교하여, 적절한 서브트리를 탐색한다.
• 일반적으로 B-트리의 노드는 수백 개가 넘는 키를 가지므로 각 노드에서는 이진 탐색을 수행한다.

 

 

 

삽입 연산

• B-트리에서의 삽입은 탐색과 동일한 과정을 거쳐 새로운 키가 저장되어야 할 이파리를 찾는다.
• 이파리에 새 키를 수용할 공간이 있다면, 노드의 키들이 정렬 상태를 유지하도록 새키를 삽입한다.
• 이파리가 M-1개의 키를 가지고 있으면, M-1개의 키와 새 키 중에서 중간 값이 되는 키를 부모로 올려보내고, 남은 M-1개의 키를 1/2씩 나누어 각각 별도의 노드에 저장한다.

 

이렇게 말하면 또 어려워 보이는데, 사실 간단하다.

전체적으로 자식 수는 M/2(소수면 올림)부터 M이하까지 이다.

또한 키의 수는 이 자식 수에 -1한 결과와 같다.

이 규칙을 생각하면서 키를 삽입한다고 하자.

 

삽입 되었을 때, 자식의 키의 수가 M-1보다 작은 경우는 그냥 정렬만 되도록 하면 된다.
하지만, 키의 수가 M/2 -1보다 커지는 경우가 문제인데, 이 경우는 분리 연산을 시행해야 한다는 것이다.

 

 

아래 예시를 한 번 보자.

 

 

차수가 5인 B-트리가 있다고 할 때, 값을 삽입하면 위와 같이 키의 수가 4를 넘는다.(M-1)

 

그러면 5개의 값 중 중간 값을 가져와 부모로 올려보내야 하는데, 마침 부모도 키의 수가 4개이다.

 

이러한 경우 부모(여기선 루트)는 더 이상 올려보낼 부모도 없다. 그래서 아래와 같이 분리 연산을 수행해야 한다.

 

 

 

 

삭제 연산

 

• B-트리에서 삭제는 항상 이파리에서 이루어진다(그래서 2-3트리도 항상 이파리에서 이루어졌었다)
• 삭제할 키가 내부 노드에 있으면, 중위 선행자나 중위 후속자를 삭제할 키와 교환 후, 이파리에서 삭제를 수행한다.
• 이때, 이동 연산과 통합 연산을 이용한다.(2-3 트리와 동일)

 

 

B-트리에서 삭제 연산을 하는 경우 사실 2-3트리와 거의 유사하다.

주로 기억해야 할 것은 이파리에서 키가 삭제된 이후, 키의 수가 M/2(소수면 올림)-1보다 작게 되면, 자식 수가 M/2보다 작게 되어 B-트리의 조건을 위반하게 된다.

 

 

그래서 좌우의 형제의 도움을 받는데, 이 과정에서 아까 사용했던 이동 연산을 사용하면 되는 것이다.

 

 

 

B-트리에서 사용되는 통합 연산은 키가 삭제된 후 underflow, 즉 B-트리 조건에 위반될 때 이동 연산이 불가능한 경우 사용한다.

 

한줄로 말하자면 B-트리에서의 통합 연산은 이동 연산이 불가능 할 때, 부모를 끌여다 쓴다고 보면 된다.

 

 

이 역시 2-3 트리에서의 통합 연산과 유사하다고 볼 수 있다. 사실은 당연한 거긴 하니까...

 

 

아래 예시를 살펴보자.

 

 

위 B-트리에서 차수가 5라고 하자.

7을 삭제하려고 할 때, 이동 연산을 실시해도 B-트리의 조건을 만족시키지 못한다.(최소 키의 수는 2)

그래서 키 7의 분기점 역할을 하는 5(혹은 12도 가능)를 끌어내려 사용해야 한다.

 

 

부모를 끌어다썼을 때, 그 부모가 B-트리의 조건을 만족시키지 못할 경우가 있다.

이때도 마찬가지로 그의 분기점 역할을 하는 부모를 끌여다 쓰면 된다.

 

 

 

 

---

 

 

B-트리의 확장

 

사실 실세계에서 가장 널리 활용되는 B-트리는 B+-트리이다.

이게 뭔 말장난인가 싶지만 B-트리와의 차이점은 조금 더 공간을 효율적으로 사용한다고 생각하면 된다.

 

주요한 특징은 아래와 같다.

• B+-트리는 두가지 영역으로 나뉜다. 한 부분은 키만으로 구성된 B-트리, 그리고 나머지는 키+관련된 정보로 구성된 이파리 노드이다.
• 키로 구성된 B-트리는 그저 삽입, 삭제 연산을 위해 관련된 이파리로 안내해주는 역할만을 수행해준다.
• 이파리들은 전체레코드를 순차적으로 접근할 수 있도록 연결리스트로 구성한다.
• B+-트리는 루트를 제외한 다른 노드의 자식 수가 2/3M~M이어야 한다.

 

 

 

성능적인 분석

• B-트리에서 삽입이나 삭제 연산의 수행시간은 각각 B-트리의 높이에 비례한다. 이때, 최대 높이는 O(logm/2n)이다.
• B-트리는 키들의 비교 횟수보다 디스크와 메인 메모리 사이의 블록 이동 수를 최소화 해야 한다.
• B-트리는 최고의 성능을 위해서는 1개의 노드가 1개의 디스크 페이지에 맞도록 차수 M을 정해야 한다.
  • 실제로 B-트리들은 M의 크기를 수백에서 수천으로 사용한다.