[Data Structure] T Tree

T Tree

T 트리는 AVL 트리의 이진 탐색 특성 및 높이 균형과 B 트리의 업데이트와 저장 효율 장점을 모두 취한 MMDB(Main-Memory Database) 최적화 트리이다. 

Background

AVL 트리의 공간 낭비와 잦은 회전 연산을 개선하기 위해 만들어짐

AVL 트리가 하나의 노드에 데이터 한 개만을 가지는 대신 T 트리는 하나의 노드가 n개의 데이터를 가질 수 있도록 개선한 구조임

장점

B 트리의 엔트리가 해당 레코드를 포함하는 데이터 페이지를 가리키고 있는데 반해 T 트리의 각각의 엔트리가 해당 레코드의 메모리 주소를 직접 포인팅하고 있기 때문에 T 트리 인덱스는 논리적 주소를 물리적 주소로 변환하는 작업 없이 원하는 레코드를 빠르게 접근할 수 있음.

T 트리는 인덱스 노드에 키 값을 포함하지 않고 직접 메모리 내의 레코드를 포인팅하기 때문에 메모리 사용량을 줄일 수 있음.

인덱스 전체가 메인 메모리에 상주하므로 디스크 I/O를 하지 않는다.

알고리즘 자체가 매우 간단하여 코드 복잡성을 줄일 수 있음.

단점

1차원 데이터에만 적용 가능한 인덱스: 공간 데이터에 사용 불가

시간복잡도

O(log2 [N/M]), N=전체 키의 개수, M=노드당 키의 개수

Search(탐색)

 

X < 노드의 최소값 → 왼쪽 서브 트리 탐색

X > 노드의 최대값 → 오른쪽 서브 트리 탐색

X ≥ 노드의 최소값 and X ≤ 노드의 최대값 → 해당 노드 탐색

Insertion(삽입)

Leaf Node Overrflow

리프 노드가 2N+1개의 데이터를 가질 경우 노드를 분리해야 한다.

Move Left

현재 노드에 값이 큰 N+1개의 데이터를 유지하고 작은 N개의 데이터를 새로운 왼쪽 자식 노드로 옮긴다.

Move Right

현재 노드에 값이 작은 N+1개의 데이터를 유지하고 큰 N개의 데이터를 새로운 오른쪽 자식 노드로 옮긴다.

Inserting

1. 추가할 키 X의 위치를 확인하기 위해 루트 노드부터 X를 탐색한다.

2. 해당 노드에 들어갈 공간이 있으면, X를 추가한다.

3. 해당 노드에 들어갈 공간이 없으면, Move Left or Move Right를 한다.

  3-1. 현재 노드가 리프 노드일 경우, X를 추가하고 노드를 분리한다.

	Move Left
	Move Right

  3-2. 현재 노드가 리프 노드가 아닐 경우,

  현재 노드의 최소값을 왼쪽 자식 노드의 최대값(greatest lower bound)으로 옮기고 해당 노드에 X를 추가한다.

  현재 노드의 최대값을 오른쪽 자식 노드의 최소값(least upper bound)으로 옮기고 해당 노드에 X를 추가한다.

	Move Left
	Move Right

Deletion(삭제)

Leaf Node Underflow

리프 노드가 N-1개의 데이터를 가질 경우 부모 노드와 합병해야 한다.

Deleting

1. 루트 노드에서부터 삭제할 키 X를 탐색한다.

2. X를 찾으면 삭제한다.

  2-1. X가 리프 노드에 있을 경우 부모 노드와 합병한다.

  2-2. X가 내부 노드에 있을 경우 왼쪽 서브 트리의 최대값을 부모 노드로 옮기거나 오른쪽 서브 트리의 최소값을 부모 노드로 옮긴다.

  2-3. 트리 균형이 깨질 경우 회전을 통해 균형을 맞춘다.