T 트리 (T tree)

T 트리란 무엇일까?

T 트리는 한 노드가 여러개의 데이터를 가질 수 있고 회전을 통해 균형을 유지하는 균형 이진 탐색 트리이다.

한 노드가 여러개의 데이터를 가짐으로써 AVL 트리의 문제점인 잦은 회전 연산이 개선되었다.

 

왜 T 트리를 배울까?

T 트리는 적절한 N을 설정함으로써 Disk I/O를 최소화 할 수 있고 이진 검색을 통해 빠르게 데이터에 접근할 수 있다.

그리고 구현이 비교적 간단하다.

따라서 Main-Memory에서 모든 데이터를 상주시켜 사용하는 Main-Memory Database에서 자주 사용되었다.

T 트리의 조건

0. AVL 트리의 조건을 상속 받는다.

1. 한 노드는 N개의 데이터를 가질 수 있다.

---

T 트리에서 사용되는 용어

용어	설명
반엽 노드 (half-leaf node)	자식이 하나인 노드
Overflow	노드가 수용할 수 있는 데이터의 개수를 초과한 경우
Underflow	노드에 존재하는 데이터가 수용 가능한 데이터의 수의 절반 미만인 경우

 

T 트리가 균형을 유지하는 방법

T 트리는 Overflow, Underflow 발생 시 트리의 깊이가 증가, 감소하며 이 과정에서 양 서브트리의 높이 차가 1을 초과한다면 AVL 트리와 마찬가지로 회전을 통해 균형을 유지한다.

 

Overflow 발생 시 N/2 만큼의 데이터를 분할하여 분할된 노드를 자식 노드로 연결한다.

Underflow 발생 시 현재 노드를 부모 노드와 병합한다. 병합 시 부모 노드에서 Overflow가 발생했다면, 다시 분할한다.

노드를 분할하는 두 가지 방법

Move Left

왼쪽 데이터부터 N/2 개의 데이터를 왼쪽 자식 노드로 추가한다.

Shift 연산이 필요하다.

 

Move Right

오른쪽 데이터부터 N/2 개의 데이터를 오른쪽 자식 노드로 추가한다.

Shift 연산이 필요없다.

---

T 트리의 구현

노드

키 값의 자료구조를 제외하고 AVL 트리와 동일한 구조를 가진다.

typedef struct Node
{
    int key[N];
    struct Node *left, *right;
    int ht;
} Node;

 

삽입 (Insert)

데이터를 삽입할 노드를 찾고, 해당 노드에 공간이 있으면 데이터를 삽입한다.

공간이 없는 경우, 현재 노드가 내부 노드라면 공간이 있는 자식 노드까지 데이터를 밀어낸다.

데이터를 밀어낸 후 말단 노드에서 Overflow가 발생했다면 노드를 분할하고 Balance Factor에 따라 트리를 회전한다. 

구현 예정

---

삭제 (Delete)

삭제할 데이터가 존재하는 노드까지 이동하고 Underflow가 발생하지 않으면 그냥 삭제한다.

내부 노드에서 Underflow가 발생한 경우 Successor를 찾아 채우고, 내부 노드에서 Underflow가 발생하지 않을 때까지 재귀적으로 반복한다.

말단 노드에서 Underflow가 발생한 경우 부모 노드와 병합하고, 부모 노드에서 Overflow가 발생한 경우 다시 부모 노드를 분할한다. 그리고 Balance Factor에 따라 트리를 회전한다.

구현 예정

---

검색 (Search)

찾고자 하는 키가 현재 노드의 min key보다 작거나 max key 보다 크다면 자식 노드로 이동하고, 그 사잇값인 경우 배열을 탐색하여 찾는다.

구현 예정

---

범위 검색 (Range Search)

이진 탐색 트리와 유사한 로직을 가진다.

구현 예정

---

시간 복잡도

T 트리는 균형 이진 트리이며 시간 복잡도는 log2(데이터 수 / 노드 당 데이터 수) 이다.

연산	평균	최악
삽입	O(logN)	O(logN)
삭제	O(logN)	O(logN)
검색	O(logN)	O(logN)

---

문제점

1. T 트리는 1차원 데이터 밖에 수용할 수 없다.
2. T 트리는 개발 당시 여러 사용자가 동시에 데이터에 접근하는 경우를 고려하지 않았기 때문에 사용자의 동시 접근을 막아야 하는 실제 데이터베이스 환경에는 B 트리보다 떨어지는 성능을 보여준다.

LU, Hongjun; NG, Yuet Yeung; TIAN, Zengping. T-tree or b-tree: Main memory database index structure revisited. In: 
Proceedings 11th Australasian Database Conference. ADC 2000 (Cat. No. PR00528)
. IEEE, 2000. p. 65-73.

 

 

---

T tree Complete Code

추후 추가 예정