[자료구조] 12강 - 멀티웨이 탐색 트리(1)

✅ 1. 멀티웨이 탐색 트리

• Mulit: 접두사로 '많은(many)', **'다수의(multiple)'**라는 의미를 가짐.
• way: '방향(direction)', '경로(path)', 또는 **'방식(mode)'**을 의미합니다.
• 즉, Multiway는 글자 그대로 **"다수의 방식/방향"**을 의미하며, 자료구조에서는 하나의 노드가 2개(이진)를 초과하는 다수의 자식 노드나 분기 경로를 가질 수 있음을 표현합니다. 이 때문에 '다원(多元)' 또는 **'m-원(m-way)'**으로 번역되기도 함.
• 즉, **멀티웨이 탐색 트리(m-way Search Tree, 다원 탐색 트리)**는 이진 탐색 트리(BST)의 탐색 규칙을 확장하여, 하나의 노드가 여러 개의 키를 저장하고 최대 m개의 자식 노드를 가질 수 있도록 일반화한 트리 자료구조입니다.
• 자식이 여러 개라는 복합적 상황을 강조하는 이름. ( 몇 개까지 가능한지 규칙을 특정하지 않음. )

✅ 2. m원 탐색 트리

• m원 탐색 트리는 멀티웨이 탐색 트리와 동일한 의미를 가지고 있지만, 한 가지 차이점은 멀티웨이 트리는 자식이 3개일 수도 있고, 10개일 수도 있다는 여러 갈래가 있을 수 있다는 큰 그림을 의미하고, m-원 트리는 정확히 이 트리는 최대 m 개 자식을 가진다라고 수학적으로 모델링한 형태로 볼 수 있음.
• 즉, 자식 노드의 최대 수를 정확히 m개 라는 수학적 정의를 강조한 표현이다. ( 2개 자식 노드 = 2 way, 3개 = 3 way... )

(1) 이진 탐색 트리

• 트리에서 특정 데이터를 검색하고, 노드의 삽입/삭제 연산이 자주 발생하는 응용 문제에 효과적인 이진 트리임.
• 즉, 왼쪽과 오른쪽 이라는 방향성을 비교하며 다루기 때문에 삽입/삭제 연산에 효율적임.
• m원 탐색 트리에서 2-way 탐색 트리가 이진 탐색 트리로 볼 수 있음.

[ 이진 탐색 트리 문제점 ]

• 이진 탐색 트리는 일반적으로 노드의 개수가 많아지면 트리의 높이가 커지게 될 수 있음.
• 쉽게말해, 2개의 노드가 고정이기 때문에 노드가 늘어날수록 높이가 높아질 수 있다는 의미임.

[ 이진 탐색 트리의 문제점 ~ 멀티웨이 탐색 트리의 발전 ]

• 멀티웨이 탐색트리는 위와같이 이진 탐색 트리의 높이의 문제로 만들어지게 됨.
• **즉, 같은 개수의 노드에도 불구하고 트리의 높이를 높지 않게 유지할 수 있는 트리 자료구조가 필요하게 됨.**

(2) m원 탐색 트리 - 정의

• 트리의 노드가 m 개 이하의 노드를 가질 수 있는 탐색 트리이다.
• 이진 탐색 트리의 확장된 형태이며, BST 와 동일하게 왼쪽 작은 값 오른쪽 큰 값의 형태를 띔.
• 탐색 트리의 제한을 따르면서, 2개 이상 ~ m개 이하의 자식 노드를 가질 수 있음.
• 즉, 핵심은 BST 의 하위가 아닌 형제 개념으로 볼 수 있음.

(3) m원 탐색 트리 - 구조

• 3-way 탐색 트리의 예시이며, 하나의 노드는 두 개의 key 값과 3개의 포인터를 가지게 된다.
• 3개의 포인터 중 제일 왼쪽은 86 보다 작은 키값을 비교해주고, 중간 포인터는 86 ~ 90 사이의 포인터에 해당하는 키값인지 비교를 해주고, 오른쪽 포인터는 90보다 큰 값을 비교해주게 되는 것이다. 이 포인터 들은 각각 서브트리의 루트에 해당한다.

• 결과적으로, m원 탐색 트리 중 3-way 탐색 트리는 위와 같이 하나의 노드가 키값을 두 개 가지게 표현이 될 수 있고, 최대 3개의 자식 노드를 가지는 구조가 될 수 있으며, 최대 3개라 1, 2, 3개는 되지만 3개를 초과하는 노드는 가질 수 없는 특징이 있음.
• 또한, 왼쪽은 키 값들의 작은 값 오른쪽은 키 값들의 큰 값 으로 이진 탐색 트리와 동일한 규칙을 가지게 된다.
• 다른점은 가운데 포인터 필드는 키값들의 가운데에 해당하는 값들을 포인터로 가리키고 있음.

(3) m원 탐색 트리 - 노드 구조

• int n: 노드에 현재 저장된 키의 개수를 나타냄.
• keyptrs[n-1]: n개의 키가 있을 때, n-1개의 키/포인터 쌍을 저장하는 배열 선언 ( 구조체 배열 )

(4) m원 탐색 트리 - 탐색 연산(key값 찾는 연산)

• 찾고자 하는 키값을 자식 키값과 비교하면서 내려가는 연산임.
• 즉, 찾는 키값과 자식 키값을 비교하는데 찾는 키값이 더 크면 오른쪽 포인터를 통해 주소를 참조하게 되는 원리임.
• 일반적으로 노드의 가지 개수가 많을수록(높이가 작다라는 의미) 최대 탐색 시간이 짧아짐. ( 서브 트리가 많다는 의미 )
• 즉, 결과적으로 m원 탐색 트리는 트리의 깊이가 얕으므로 더 빨리 찾을 수 있음.
• 하지만, 이렇게 키값이 많으면 많을수록 탐색이 빨라질 수 있지만 어느정도 키값을 늘리게 되면 노드 내부에서의 탐색 시간이 눈에 띄게 길어지게 된다는 단점이 있어, 보통은 3원, 4원 트리 까지만 쓰는듯.
• 높이는 줄어들지만, 메모리 낭비가 커질 수 밖에 없음.

---

✅ 3. B 트리

(1) B 트리 - 만들어진 이유

• m원 탐색 트리의 균형을 맞추기 위해서 등장한 것이 바로 B 트리임. 즉, BST 의 균형을 맞추기 위해서 AVL 트리가 나온 것과 동일한 이유임.
• m원 탐색 트리는 서브 트리의 균형에 대해서는 특별히 제한하지 않기 때문에, 이러한 이유에서 각 노드가 자식을 많이 갖게 하여 트리의 높이를 줄이고 전체적으로 균형을 유지한다면 탐색 성능을 더욱 향상할 수 있을 것 이라고 판단해서 만들어짐.
• 또한, m원 탐색 트리는 개념적으로 하나의 노드가 여러 Key 를 갖고, 여러 자식을 가질 수 있는 구조가 전부인 트리 자체의 균형 유지 규칙이 존재하지 않는다. 이러한 균형을 유지해주는게 바로 B트리이다. ( 즉, 스스로 균형 유지하는 m원 탐색 트리 )
• **m원 탐색 트리를 개선한 B 트리는 인덱스 구조를 구현하는데 가장 일반적으로 사용이 됨.**
• 차수 m인 B 트리의 탐색 경로 길이는 같은 개수의 키를 가지는 이상적인 m원 탐색 트리보다 길 수 있지만, 이상적인 m원 탐색 트리의 유지 비용에 비해 키 값을 삽입하거나 삭제할 때 B 트리를 유지하는 것이 더 효율적임(쉬움).

(2) B 트리 - 개념

[ B 트리 - 특징 ]

출처: https://www.youtube.com/watch?v=H_u28u0usjA&t=761s

• m원 탐색 트리에 위와 같은 규칙성을 더해서 균형을 맞추는 것이 B 트리임.
• m원 탐색 트리의 파생이기 때문에 자녀 노드의 최대 개수를 직접 지정해서 사용 할 수 있음.
• 즉, 최대 몇 개의 자녀 노드를 가질 것인지가 B tree를 사용할 때 중요한 파라미터가 됨.

[ B 트리 - 파라미터 조건 ]

출처: https://www.youtube.com/watch?v=H_u28u0usjA&t=761s

• [ M/2 ] : 각 노드의 최소 자녀 노드 수는 M의 2를 나눈 몫을 올림 하라는 의미이다. 
• 즉, M = 3 : 3/2 = 1.5 = 2(올림) 그리고 root node, leaf node 는 제외한다.
• [ M/2 ] - 1: 각 노드가 가지는 최소한의 key 수에 대한 조건은 root node 를 제외한다.
• 또한, M의 크기에 따라서 B tree가 갈리기 때문에, M차 B tree 로 부름.

출처: https://www.youtube.com/watch?v=H_u28u0usjA&t=761s

• 또한, B트리는 부모 노드의 key 수가 x 개라면, 자녀 노드의 수는 언제나 x + 1개이여야 한다.
• 즉, 위와같이 key 값이 k1, k2 2개인 경우 2 + 1 = 3 인 자식 노드의 개수를 가져야함.
• 그리고 노드가 최소 하나의 key 는 가지고 있는 형태라, 몇 차 B tree 인지와 관계없이 최소 2개의 자녀는 가짐.

[ B 트리 - 정리 ]

• 루트와 잎 노드를 제외한 트리의 각 노드는 최소 [m/2](올림) 개의 서브 트리를 갖는다.
• 트리의 루트는 최소한 2개의 서브 트리를 갖는다.
• 트리의 모든 잎 노드는 같은 레벨에 있다. 즉, B(balanced tree) tree 로 삽입 연산 시 모든 잎 노드는 같은 레벨로 유지시켜줌.
• 한 가지 특징은 노드의 키값은 오름차순으로 정렬이 지속적으로 됨.

(3) B 트리 - 데이터 삽입

[ 삽입 알고리즘 ]

출처: https://www.youtube.com/watch?v=H_u28u0usjA&t=761s

[ 3차 B tree - 데이터 삽입 예시 ]
(1) 데이터 삽입 -> root 에서부터 아래로 내려가면서 비교
- 3차 B tree 의 경우 키 값이 최대 2개가 존재 할 수 있음.
- 그렇기 때문에 키 두개다 비교를 해줘야함.
(2) 최종적으로 잎 노드로 내려오게 됨.
(3) 잎 노드의 키 값이 가득차지 않았다면, 오름차순으로 정렬 하며 삽입
(4) 만약 가득차 있는 경우(넘치는 경우)
- 가운데 key를 기준으로 좌우 key 들을 분할하고 가운데 key 는 승진을 시키게 됨.
- 좌우 key는 해당 노드에서 가장 크고 작은 값임.
- 좌우 key 를 각자 노드로 분할을 함.
- 이후, 가운데 key를 부모노드로 승진을 시킴.
- 만약 부모노드의 키 값의 공간이 있다면 그곳에 오름차순으로 정렬하며 삽입.
- 가득차 있는 경우에는 반복하며, 계속 좌우 분할 가운데 승진을함.
- 최종적으로 leaf 노드들은 같은 레벨에 균형을 맞출 수 있음.

• 노드가 넘치는 경우는 하나의 노드에서 M-1(각 노드의 최대 key 수)를 넘는 키값을 저장한 경우임.
• 즉, 3차 B tree 면 최대 2개의 key 를 저장 할 수 있는데 여기서 3개를 저장하려고 하는 순간이 넘치는 경우임.

(4) B 트리 - 데이터 삭제:잎 노드

출처: https://www.youtube.com/watch?v=H_u28u0usjA&t=761s

• "삭제 후 최소 key 수보다 적어졌다면 재조정한다" 쉽게말해, B tree 의 각 노드가 가지는 최소한의 key 수에 대한 조건을 만족시키지 못할 경우중에서 [M/2]-1 보다 작은 수가 되었다면 재조정을 한다는 의미이다.
• 즉, 3차 B tree 의 경우 최소 key 가 1이기 때문에, 1 미만인 경우 재조정이 필요해지게 된다.
• 재조정을 하는 방식은 위의 1, 2, 3 방식으로 진행이 됨. ( 재조정: B tree 의 조건에 맞게 노드를 재배치 하는 것임. )
• 1번에서 의미하는 형제는 빨간색 노드를 기준으로 왼쪽은 작은 값을 가지는 동생 오른쪽은 큰 값을 가지는 형이 된다.
• 즉, 위와 같이 빨간색 노드는 5가 삭제된 상태이고 B tree 의 규칙을 만족시키지 못했기 때문에 만족을 시키기 위해서 동생 노드 중 가장 큰 key 를 부모 노드의 가장 작은 key 위치로 올리고, 부모 노드의 가장 작은 key 는 5가 삭제 된 노드에 위치하게 된다.

[ 1번 - 형제 지원 ]

출처: https://www.youtube.com/watch?v=H_u28u0usjA&t=761s

• 1차적으로 삭제 후 최소 키 보다 적다면 동생한테 먼저 지원 받고 이후 여건이 안되면 형한테 받게 됨.

[ 2번 - 형제 지원 불가능 할 시 부모 지원 ]

출처: https://www.youtube.com/watch?v=H_u28u0usjA&t=761s

• 형제의 지원을 받지 못하는 경우, 부모의 지원을 받아서 부모의 키 값을 내려 받고 합치게 됨.
• 즉, 삭제 된 노드의 key 값이 B tree의 각 노드 최소 key 수를 만족하지 못하는 경우 해당 노드는 왼쪽 노드를 기준으로 부모로 부터 작은 key 값을 내려받고 동생 노드와 합쳐지게 됨.
• 만약 삭제 되는 노드의 key 값이 동생 노드인 경우 부모 노드한테 키값을 받고 형 노드와 합쳐지면 됨.

[ 3번 - 지원한 부모에 문제가 생긴 경우 ]

• 부모노드가 최소 key 수를 만족하지 못하는 경우 위에 1번,2번을 반복 수행하면서 다시 재조정을 함.
• 이후, root 노드가 비어있다면, root 노드를 삭제하고 해당 자식 노드가 root 가 된다.
• 앞선 내용은 모두 leaf 노드에서 데이터를 삭제하고 재조정을 하는 경우임.

(5) B 트리 - 데이터 삭제:내부 노드

• internal 노드에 있는 데이터를 삭제하려면 leaf 노드에 있는 데이터와 위치를 바꾼 후 삭제하지만, leaf 노드에 있는 데이터 중에 어떤 데이터와 위치를 바꿔줄 것인지가 이슈임.

• 이슈 해결은 삭제할 데이터의 선임자나 후임자와 위치를 바꿔주면 해결이 된다.
• 예를들어 root 15 를 삭제 할 경우 아래 leaf 노드의 8과 바꾼다고 가정하면 15의 왼쪽 서브 트리는 작은 값만 가져야 하므로, 아래 9 가 있어 불가능함. 이 경우 15 보다 작은 왼쪽 서브 트리 중 가장 큰 값 9(선임자)와 위치를 바꾼 후 삭제를 하면 됨.
• 반대로 오른쪽 서브트리 기준으로는 가장 작은 값인 20(후임자)와 위치를 바꾼 후 삭제를 하면 됨.
• 해당 선임자와 후임자가 leaf 노드에 있는가를 증명해야 한다?

(6) B 트리 - 데이터 삭제 정리

• 삭제되는 key 의 노드가 leaf & internal 인지에 따라 삭제되는 방식이 달라짐.
• 핵심은, 삭제되는 key 노드가 leaf 노드인지, internal 노드인지 파악을 먼저해줘야함.
• 만약 leaf 노드면 삭제 후 형제 또는 부모의 도움을 받아 재조정을 하면 됨.
• 만약 internal 노드면 삭제할 데이터의 선임자 또는 후임자와 위치를 바꾸고 삭제를 하면 됨.
• 이후, 기존 leaf 노드에서 삭제 한 연산과 동일하게 최소 key 조건을 만족하면서 균형을 유지하면 됨.
• ** 즉, 삭제는 항상 leaf 노드에서 발생함. **
• ** internal 노드의 경우 선임자(leaf)와 위치 바꾼 후 삭제 **
• ** 삭제 후 최소 key 수보다 적어졌다면 재조정 **
• ** 형제 지원 -> 부모 지원 받고 형제 합침 -> 부모 도움 후 부모도 문제 시 재차 조정 **

---

✅ 4. B*, B+ 트리

(1) B* 트리의 정의

• 노드의 약 2/3 이상이 채워지는 B 트리
• 노드가 꽉 차면 분리하지 않고, 키와 포인터를 재배치하여 다른 형제 노드로 옮김
• B 트리와 동일한 수의 노드를 갖는다면 높이가 낮고, 삽입 / 삭제 시 발생하는 노드 분리를 줄이려고 고안됨.
• 즉, B* 트리는 최소 4차 이상, 보통 100~1000 차수 같은 대형 노드에서 효율을 발휘하게 됨.
• 차수가 많을수록 노드의 key 값이 늘어나기 때문에 2/3 이상을 보장해주면 메모리 효율이 올라갈 수 있음.

(2) B+ 트리의 정의

• 탐색 트리로 구성하면 매우 빠르게 탐색할 수 있지만, 전체 데이터를 차례로 처리하기는 불편함.
• 매번 왼쪽인지 오른쪽인지 비교해가면서 다음 노드를 찾아가면서 처리해야 함.
• B+ 트리는 인덱스된 순차 파일을 구성하는데 사용이 됨.
• B 트리와 같이 각 노드의 키가 적어도 1/2이 채워져야 하는 점은 같음.
• 또한, B+ 트리의 잎 노드들은 위와 같이 연결 리스트 형태로 연결이 되어 있음.
• 모든 키 값이 잎 노드에 있고 그 키 값에 대응하는 실제 데이터(파일 내용)에 대한 주소를 잎 노드만이 가지고 있음.
• 모든 검색은 리프까지 가므로 검색 경로가 균일해 예측 가능하며, 현대 DB 인덱스와 파일시스템에서 표준으로 사용된다.