[자료구조/DB] T-Tree structure (T-Tree 구조)

2020. 3. 31. 22:04

AVL 트리의 이진 탐색 특성 및 높이 균형과, B트리의 업데이트와 저장효율 장점을 모두 취한 MMDB 최적 트리
물리주소를 직접 포인팅 → B-Tree에서 진화된 형태로 물리적인 주소의 논리적인 변환 없이 빠르게 접근 가능한 자료구조
T- 트리에서 'T'는 노드 데이터 구조 모양을 나타낸다
기존의 B-Tree의 Data Page의 다단계 검색의 복잡성 극복
한 노드의 가장 작은 값과 가장 큰 값의 비교
Datablitz, EXtremeDB, MySQL Cluster, Oracle TimesTen 및 MobileLite와 같은 주 메모리 데이터베이스에서 사용
균형이 유지되는(balanced) 데이터 구조로, 인덱스와 실제 데이터가 모두 메모리에 모두 저장되는 경우에 최적화된 구조 (디스크 I/O가 없음)
하드디스크와 블록지향 보조 저장장치의 저장에 최적화 된 인덱스 구조
T- 트리는 인덱스 트리 노드 자체 내에 인덱스 된 데이터 필드의 사본(copy)을 유지하지 않으며, 실제 데이터가 항상 주 메모리에 인덱스와 함께 저장되어 실제 데이터 필드에 대한 포인터 만 포함한다는 이점을 가짐
단점 : 1차원 데이터에만 적용이 가능하며, 최근 매모리 기술 발전으로 B트리에 비해 성능 우위가 낮아짐

해당 노드의 값보다 작은 값은 왼쪽 서브트리에 위치
해당 노드의 값보다 큰 값은 오른쪽 서브트리에 위치
노드의 구성
1. 부모 노드에 대한 포인터
2. 왼쪽 자식 노드
3. 오른쪽 자식 노드
4. 정렬 된 데이터 포인터 배열
5. 일부 추가 제어 데이터
노드의 종류
1. 내부 노드 (internal node) : 두개의 하위 트리가 있는 노드
2. 리프 노드 (leaf node) : 두개의 하위 트리가 없는 노드
3. 반엽 노드 (half-leaf node) : 하나의 하위 트리 만있는 노드
4. 값의 경계 노드 (bounding node) : 값이 노드의 현재 최소값과 최대 값 사이에있는 경우 노드
경계 값 (Bound values) : 각 내부 노드는 리프 노드 또는 반엽 노드를 가진다. 리프노드와 반엽노드는 가장 작은 데이터 값(최대 하한 이라고 함, greatest lower bound) 보다 크고, 가장 큰 데이터 값(최소 상한 이라고 함, least upper bound) 보다 작은 값을 가진다.
리프 및 반엽 노드에는 데이터 배열의 최대 크기부터 최대 크기까지 다양한 수의 데이터 요소가 포함될 수 있다
내부 노드의 점유율(채워진 양)은 미리 정의 된 최소 및 최대 요소 수 사이에서 유지

성능의 이점

업데이트와 저장의 효율 : 분리, 병합을 통한 재균형 과정이 자가 균형 이진 탐색 트리 만큼 자주 일어나지 않는다. (B 트리, 데이터의 갯수가 일정 갯수 사이라면 분리, 병합이 일어나지 않는다)
한 노드안에 여러개의 데이터를 가짐 (B트리 성질)
이진 검색, 높이 균형, 인메모리(in-memory) 트리 구조의 성능 이점을 갖음 (AVL트리)
저장공간의 오버해드를 피함

B-트리	T-트리	AVL
분리 및 병합을 통해 재균형 과정은 다른 자가균형 이진 탐색 트리(AVL) 만큼 자주 일어나지 않음
	이진 탐색
	높이 균형을 가짐
	저장공간 오버헤드를 피함
한 노드안에 여러개의 데이터를 가짐
	물리적인 주소의 논리적인 변환 없이 빠르게 접근 가능
	Data Page의 다단계 검색의 복잡성 극복

B- 트리 (또는 B+트리)는 디스크 기반 관계형 데이터베이스 시스템에서 가장 널리 사용되는 인덱스 구조인 것과 비교할 때, T- 트리는 메인 메모리의 인덱스 구조로 널리 받아 들여졌습니다. 이는 모든 데이터 베이스(또는 대부분)가 메인 메모리에 상주하고 있기 때문이다
T- 트리는 주 메모리 데이터베이스에 널리 사용되는 것처럼 보이지만 최근 연구에 따르면 최신 하드웨어에서는 실제로 B- 트리보다 성능이 좋지 않다. 주된 이유는 현재의 캐시 접근과 메인메모리 접근 사이의 속도 차이을 고려할때, 메모리 참조가 균일한 비용을 가진다는 전통적인 가정이 더이상 유효하지 않기 때문이다.
문헌에 보고된 T 트리 관련 작업은 대부분 동시통제를 고려하지 않았다. T- 트리에 대한 두 가지 동시성 제어 접근 방식이 제시된다. 시뮬레이션 연구 결과에 따르면 동시성 제어가 시행되는 경우 널리 사용되는 B- 트리 인덱스의 변형 인 B- 링크 트리가 T- 트리보다 성능이 우수하다. 이는 T- 트리에 대한 동시성 제어가 B- 링크 트리보다 많은 잠금 작업을 필요로하고 잠금 및 잠금 해제의 오버 헤드가 높기 때문이다.

<참고>

AVL 트리

균형잡힌(balanced) 이진 탐색 트리
1962년 G.M. Adelson-Belskii와 E.M.Landis의 논문을 통해 발표되었으므로, 이들의 이름을 따서 이름이 지어졌다
각각의 노드(node, 분기점)마다 왼쪽과 오른쪽 부분 트리(sub-tree)의 높이 차이에 대한 정보를 가지며 부분 트리의 높이 차이가 1보다 크지 않은 성질을 가진다.
균형 잡힌 AVL 트리는 n개의 원소가 있을 때 O(log n) 의 시간복잡도로 검색, 삽입, 삭제를 할 수 있다.
삽입과 삭제를 할 때에는 원하는 노드를 찾기 위해 2개의 경로가 필요하기 때문에 레드-블랙 트리만큼 효율이 좋지 않아 자주 쓰이지는 않는다.

B 트리 (Balanced, Binary, Boeing Tree)

트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질수 잇는 자식 노드의 최대 숫자가 2보다 큰 트리구조
내부 노드의 자식 수가 미리 정해진 범위 내에서 변경가능 하기 때문에 항목이 삽입되거나 삭제될 때, 내부 노드는 해당 범위의 자식 노드의 수를 만족시키기 위해 분리되거나, 병합 된다.
자식 노드의 수가 일정 범위 내에서만 유지되면 되므로 분리 및 병합을 통해 재균형 과정은 다른 자가균형 이진 탐색 트리(AVL) 만큼 자주 일어나지 않지만, 저장 공간에서 손실은 있게 된다.
노드 접근시간이 노드에서의 연산시간에 비해 훨씨 길 경우 (접근시간 > 연산시간, 예를 들면 하드디스크나 2차 저장장치), 다른 구현방식에 비해 상당한 이점을 가지고 있다.
각 내부 노드에 있는 자식 노드의 수를 최대화함으로써, 트리의 높이는 감소하며, 균형 맞춤은 덜 일어나고, 효율은 증가하게 된다. 대개 이 값은 각 노드가 완전한 하나의 디스크 블로 혹은 2차 저장장치에서의 유사한 크기를 차지하도록 정해진다.
즉, 자식 노드의 수 증가 → 트리의 높이 감소 (노드 내 데이터 증가) → 탐색시간 감소 (연산시간 증가)

MMDB (MainMemoryDB, 메인메모리 DB) : 데이터베이스 전체를 주기억장치에 상주시킨 데이터 베이스

B-Tree의 Data Page의 다단계 검색 :

BEST WISH