T Tree구조

1. AVL-Tree와 B-Tree의 개선된 형태 T-Tree의 개요

  가. T-Tree의 정의

    -AVL-Tree의 이진 탐색 특성 및 높이 균형과 B-Tree의 업데이트와 저장 효율(한 노드는 여러 개 데이터 가짐)을 물려 받은 메모리 기반 DBMS에서 선호되는 인덱스 알고리즘

  나. T-Tree의 특징

    -AVL-Tree와 B-Tree로부터의 변형

    -기존의 B-Tree와 AVL-Tree로부터 진화

    -이진 검색과 높이 균형을 가지는 AVL-Tree의 성질을 가짐

    -한 노드 안에 여러 개의 데이터를 가지는 B-Tree의 성질을 가짐

  다. T-Tree의 등장 배경

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

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

  라. T-tree의 장단점

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

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

    -인덱스 전체가 메인 메모리에 상주하므로 디스크 I/O를 하지 않는다. 그리고 알고리즘 자체가 매우 간단하여 코드 복잡성과 코드 경로를 줄일 수 있음.

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

 

2. T-Tree의 개념도 및 설명

  가. T-Tree의 개념도

두개의 서브트리를 가지는 내부노드(Internal node)의 T-Tree의 GLB(Greatest Lower Band)와 LUB(Lowest Upper Band)

 

  나. T-Tree의 설명

    1)T-Tree의 노드

- 내부 노드(Internal Node)

ㆍ 오른쪽, 왼쪽 서브 트리를 가짐. 내부 노드에 포함될 수 있는 데이터의 개수는 T트리 생성할 때 결정

- 하프리프 노드(Half-leaf Node)

ㆍ 방향과 상관 없이 한쪽 서브 트리만을 가지며 하나의 자식 포인터만 가짐

- 리프 노드(Leaf Node)

ㆍ 자식포인터가 하나도 없음

       

    2)각 내부노드 A(개념도 참조)에 대해, 그 노드의 최소값보다 작은 값을 가지는 서브트리는 트리의 좌측 서브트리가 되고, 반대로 그 노드의 최대값보다 큰 값을 가지는 서브트리는 우측 서브트리가 됨

   

    3)GLB(Greatest Lower Bound)

-내부 노드A의 좌측 서브트리 값 중에서 A의 최소값과 가장 근접한 값

 

    4)LUB(Lowest Upper Bound)

-A의 우측 서브트리 값 중에서 A의 최대값과 가장 근접한 값

   

    5)모든 노드의 삽입과 삭제는 단말 노드에서만 이루어지며 이때 불균형 상태가 되면 AVL-Tree처럼 로테이션 연산을 수행해 균형 상태로 만듦

 

3. T-Tree 알고리즘

  가. 검색 알고리즘

T-Tree에서의 검색은 이진 트리에서의 검색과 유사하나 이진 트리에서는 한 개의 값만을 비교하고, T-Tree에서는 그 노드의 가장 작은 값과 가장 큰 값을 비교

-검색은 항상 트리의 루트부터 시작

-만약 검색하려는 값이 그 노드의 가장 작은 값보다 작으면 왼쪽 서브 트리로 이동하여 계속해서 검색함.

-그렇지 않고 만약 검색 값이 그 노드의 가장 큰 값보다 크면 오른쪽 트리로 이동하여 계속 검색함.

-그렇지 않으면 현재 노드에서 찾음.

 

  나. 삽입 알고리즘

새로운 값이 삽입되고 나면 균형(Balance)인지를 검사하여 만약 삽입 후 unbalance하면 적당한 rebalance연산 수행

-삽입할 위치 검색

-만약 삽입할 노드가 발견되면 삽입할 수 있는 여분의 방이 있는지를 검사하여 적당한 여분의 방이 있으면 삽입하고 종료.

-그렇지 않으면 가장 작은 아이템을 제거하고 삽입하여는 값을 삽입한 후 그 노드 단말 노드에 제거한 값을 삽입

-만약 트리가 비어 있고 삽입할 값의 경계가 없으면 가장 나중에 삽입.  만약 이 삽입된 값이 적당하면 그 값이 새로운 가장 작은 값이 되든지 아니면 가장 큰 값이 될 수 있음.

-그렇지 많으면 새로운 노드를 생성

-만약 새로운 노드가 첨가되면 단말 노드부터 루트까지의 경로에 대한 balancing검사

 

4. T-Tree의 현황

  가. 실시간 처리를 하기 위하여 일반적으로 Main Memory DBMS에서 많이 사용하는 추세임

 

  나. 다양한 인덱스 유형 중에 현재 구축중인 어플리케이션이 조회 위주의 성격인지, 수정 위주인지를 판단하여 인덱싱 알고리즘 선택

 

  다. T-Tree와 B* Tree의 비교

구분	T-Tree	B*-Tree
활용 DBMS	MMDBMS	RDBMS
논리주소 변환	메모리 주소 직접	논리주소->물리주소
엔트리 크기	메모리 주소 사용 경제적	해당 레코드 포함 데이터 페이지 포인팅
설계초점	CPU사용 시간 절감	디스크 I/O최소화
메모리 공간 사용	경제적	비 경제적
접근속도	빠름	보통

 

라. 그간 T-Tree가 MMDB에서 가장 우수한 성능을 보여 가장 적합한 인덱스 구조인 것으로 알려졌으나, 최근 메인 메모리 성능 대비 CPU클럭 스피드가 급격히 빨라져 B-Tree가 더욱 나은 성능을 보이는 추세. 따라서 기존 CPU-메모리-디스크 사이에서 발생했던 디스크I/O 병목현상이 CPU-캐시-메모리 사이의 메모리 엑세스 병목현상을 보임.

마. 임의 접근(Random Access)과 포인터를 가정하고 디자인된 T-Tree보다 디스크I/O를 최대한 줄이기 위해 고안된 B-Tree가 메인 메모리에서도 엑세스 수가 적어 CPU와 메모리 사이 성능 격차가 커짐에 따라 두 방법의 인덱스 구조 사이에 성능 역전 현상이 일어나게 됨.     “끝”

 

[참고]

 1) 인덱스의 정의

- 어떤 종류의 검색 연산을 취적화 하기 위해 디스크상에 데이터 레코드를 구성하는 데이터 구조

 

2) 인덱스의 유형

유형	설명	비고
순서 인덱스	탐색 키 필드의 값을 정렬된 순서로 유지	기본/클러스터링/보조
해시 인덱스	해시함수 이용	주소값 직접 접근
다단계 인덱스	트리를 기반으로 함	희소인덱스로 부족 시

 

3) 다단계 인덱스의 종류 및

종류	설명	활용
B-Tree	모든 노드의 차수가 2이하로 구성	DB INDEX
T-Tree	쓰레드라는 포인터로 순서를 연결한 이진 트리	MMDB
R-Tree	다차원의 특징을 갖는 데이터를 색인	공간 데이터 베이스

 

4) B-Tree와 T-Tree의 비교

구분	B-Tree	T-Tree
구성요소	루트 노드, 왼쪽/오른쪽 서브 트리	전위, 중위, 후위 운행
특징	공집합 허용, 왼쪽-오른쪽 방향제한	운행법에 따라 노드 방문순서 다름
장점	연결리스트로 기억 공간 낭비 해결	순회 유용 포인터(스레드)로 순서를 해결
단점	거의 완전 트리가 아닌 경우 기억 공간 낭비가 심함
활용	컴퓨터 응용	메인 메모리 데이터베이스

 

5) AVL Tree(Adelson-Velskii and Landis Tree)

- 한 노드를 중심으로 좌우 종속 트리의 높이 차가 1 이하인 균형 잡힌 트리. 이진 트리의 삽입, 삭제를 계속할 때 어느 한 방향으로 치우치거나, 높이 차이로 인해서 수행 시간이 증가되는 것을 막기 위해 균형을 유지하도록 한 것이다. B 트리 등과 함께 균형잡힌 트리(height-balanced tree)라고도 한다.