T-Tree MMDB 강원대학교 컴퓨터 과학과 양 기 운

Presentation on theme: "T-Tree MMDB 강원대학교 컴퓨터 과학과 양 기 운"— Presentation transcript:

1 T-Tree MMDB 강원대학교 컴퓨터 과학과 양 기 운

2 0. 목 차 1. T-Tree란? 2. T-Tree의 구조 3. T-Tree의 연산 4. T-Tree의 장/단점
0. 목 차 1. T-Tree란? 2. T-Tree의 구조 3. T-Tree의 연산 - 검색/삽입/삭제/재균형 연산 4. T-Tree의 장/단점 5. T-Tree와 B-Tree의 비교 6. 디스크 / 메모리 기반 DB 비교 7. 참고자료 T-Tree & MMDB

3 1. T-Tree란? AVL-Tree와 B-Tree로 부터의 변형 메인 메모리 엑세스에 최적화 됨
새로운 인덱스 노드 포인터 -> 검색 영역 절반으로 감소 T-Tree & MMDB

4 2. T-Tree의 구조 T-Tree의 구조 T-Tree & MMDB

5 2. T-Tree의 구조 T-Tree의 노드 구조 : 포인터가 메모리 블록을 지정 T-Tree & MMDB

6 2. T-Tree의 구조 2개의 서브 트리를 가짐 노드 A의 가장 작은 아이템은 왼쪽 서브 트리에서 작은 값들 중에서 가장 큰 값(greatest lower bound) 노드 A의 가장 큰 아이템은 오른쪽 서브 트리에서 큰 값들 중에 가장 작은 값(least upper bound) 노드 A의 아이템들은 정렬되어 있음 T-Tree & MMDB

7 2. T-Tree의 구조 T-Tree의 서브트리 구조 T-Tree & MMDB

8 3. T-Tree의 연산(검색) T-Tree의 검색 : 이진 트리 검색과 유사 검색 알고리즘
이진 트리 : 한 개의 값만을 비교 T-트리 : 노드의 가장 작은 값과 가장 큰 값을 비교 검색 알고리즘 검색 : 항상 트리의 루트(root)부터 시작 노드의 가장 작은 값과 검색 값 비교 작으면 왼쪽 서브 트리로 이동하여 계속해서 검색. 노드의 가장 큰 값과 검색 값 비교 크면 오른쪽 서브 트리로 이동하여 계속하여 검색. 그렇지 않으면 현재 노드에서 찾는다. T-Tree & MMDB

9 3. T-Tree의 연산(삽입) T-Tree의 삽입 : 새로운 값이 삽입후 균형(balance)검사 삽입 알고리즘
만약 삽입 후에 불균형(unbalance)->적당한 재균형(rebalance) 연산 삽입 알고리즘 삽입할 위치를 찾는다. 만약 삽입할 노드가 발견되면, 삽입할 수 있는 여분의 방이 있는지를 검사하여 적당한 여분의 방이 있으면 삽입하고 종료한다. 그렇지 않으면, 가장 작은 아이템을 제거하고 삽입하려는 값을 삽입한 후 그 노드 단말 노드(leaf)에 제거한 값을 삽입한다. 만약 트리가 비어 있고 삽입할 값의 경계가 없으면 가장 나중에 삽입한다. 만약 이 삽입된 값이 적당하면 그 값이 새로운 가장 작은 값이 되던지 아니면 가장 큰 값이 될 수도 있다. 그렇지 않으면 새로운 노드를 생성한다. 만약 새로운 단말 노드가 첨가되면 단말 노드부터 루트까지의 경로에 대한 균형을 검사한다. T-Tree & MMDB

10 3. T-Tree의 연산(삭제) T-Tree의 삭제 : 삽입 알고리즘과 유사 삭제 알고리즘
삭제할 아이템을 찾아서 삭제한 후, 필요하다면 재균형을 실행 삭제 알고리즘 삭제할 값을 가지고 있는 노드를 찾는다. 만약 삭제 연산이 언더플로우를 야기 시키지 않는다면 단순히 그 값을 삭제하고 종료한다. 그렇지 않고 만약 중간 노드(internal node)라면, 그 값을 삭제하고 단말 노드 또는 한쪽 단말 노드로부터 작은 값들 중에서 가장 큰 값을 가지고 온다. 만약 단말 노드 또는 한쪽 단말 노드가 있으면 아이템을 삭제한다. 만약 노드가 한쪽 단말 노드이고 한 단말 노드와 병합시킬 수 있다면, 두 개의 노드를 한 개의 노드로 병합하고 다른 한 노드는 버리고 마지막 단계를 처리한다. 그렇지 않으면 노드를 풀어주고 트리를 재균형하기 위해서 마지막 단계를 처리한다. 단말 노드로부터 루트로 모든 노드에 대해서 높이가 1 보다 크면 로테이션 연산을 실행한다. 균형 검사는 모든 노드들에 대해서 균형을 검사한다. T-Tree & MMDB

11 3. T-Tree의 연산(재균형) T-tree의 재균형 연산 : AVL-tree와 유사 LL , LR 로테이션
단말 노드가 첨가 또는 삭제 되면 항상 검사 삽입시, 트리의 재균형은 대부분 한번의 로테이션이 요구 삭제시, 다른 노드에도 영향을 주기 때문에 균형이 될 때까지 로테이션을 수행 T-Tree & MMDB

12 4. T-Tree의 장/단점 장점 단점 메모리의 효율성과 삽입/삭제 시간의 융통성을 가짐 1차원 데이터에만 적용 가능한 색인
삽입시 발생할 수 있는 오버플로우(overflow) 감소 삭제시 발생할 수 있는 언더플로우(underflow) 감소 단점 1차원 데이터에만 적용 가능한 색인 최근들어 CPU/캐쉬의 성능향상으로 T-Tree보다 B-Tree가 성능이 더 나은것으로 밝혀짐 T-Tree & MMDB

13 5. T-Tree와 B-Tree의 비교 구조 비교 <B-Tree구조> T-Tree & MMDB

14 5. T-Tree와 B-Tree의 비교 B-Tree 인덱스 사용처 : DRDBMS(디스크 기반 데이터베이스)
목 적 : 디스크의 I/O감소 인덱스는 디스크에 저장된다고 가정 노드의 엔트리는 키값을 가짐 노드의 엔트리는 데이터 페이지 포인터(RID)를 가짐 해당 레코드가 포함되어 있는 데이터 페이지를 포인팅함. T-Tree & MMDB

15 5. T-Tree와 B-Tree의 비교 T-Tree 인덱스 사용처 : MMDBMS(메인메모리 기반 데이터베이스)
목 적 : 메모리 사용량 절약 / 간단한 알고리즘 인덱스/DB 데이터는 메인 메모리에 상주된다고 가정 디스크 I/O가 발생하지 않음 노드의 엔트리는 키값을 가지지 않음 메모리 사용량 절약 노드의 엔트리는 메모리의 레코드 주소를 가짐 간단해진 알고리즘(논리적 주소->물리적 주소변환 필요없음) T-Tree & MMDB

16 6. 디스크 / 메모리 기반 DB 비교 T-Tree & MMDB

17 6. 디스크 / 메모리 기반 DB 비교 T-Tree & MMDB

18 6. 디스크 / 메모리 기반 DB 비교 T-Tree & MMDB

19 7. 참고자료 건국 대학교 DB연구실 PPT 자료 데이터 베이스 사랑 넷 MMDB 자료실
삼성 SDS IT Review중 MMDB에 관한 글(한현식님) T-Tree & MMDB