1. T-Tree (트리 트리)
개요:
- In-memory DBMS에서 주로 사용되는 트리 구조.
- AVL 트리와 B-트리의 장점을 절충하여 만든 자료구조.
- 메모리 기반 환경에서 성능 최적화를 위해 고안됨.
특징:
- 노드는 정렬된 key들의 배열을 포함.
- 노드마다 최소/최대 key, 자식 포인터, 부모 포인터 존재.
- 균형 이진 트리의 성격을 가지며, 높이 균형을 유지.
- 메모리 접근이 빠른 환경에서 적합 (디스크 접근 없음).
장점:
- 메모리 내에서 검색/삽입/삭제가 빠름.
- 탐색 시간이 로그(log N) 수준.
2. R-Tree (사각형 트리 / 영역 트리)
개요:
- 공간 데이터 (spatial data) 처리를 위한 인덱스 구조.
- GIS, CAD, 이미지, 지도 등에서 사용.
- 사각형 영역 (bounding rectangle) 기반으로 인덱스를 구성.
특징:
- 노드는 MBR (Minimum Bounding Rectangle) 로 구성됨.
- 중복되는 영역이 있을 수 있음 (B-트리와 달리 분리 불가).
- 자식 노드의 MBR들을 포함하는 상위 MBR을 구성.
장점:
- 다차원 공간 검색에 유리 (범위, 근접, 포함 질의).
- 2차원 이상의 데이터 검색에 적합.
3. 인덱스 (Index)
개요:
- 데이터 검색 성능을 향상시키기 위한 데이터 구조.
- 일반적으로 B-트리, 해시, 비트맵 인덱스 등을 사용.
종류 및 특징:
-
B-Tree Index:
- 가장 일반적인 인덱스 구조.
- 균형 잡힌 트리, 범위 검색에 유리.
-
Bitmap Index:
- 컬럼 값이 중복이 적을 때 (low cardinality) 효과적.
- 주로 데이터웨어하우스, OLAP 등에서 사용.
-
Hash Index:
- 정확한 값 검색에 빠름 (등치 조건).
- 범위 검색은 불가능.
정리 표:
| 항목 | T-Tree | R-Tree | 일반 Index |
|---|---|---|---|
| 목적 | 메모리 기반 인덱스 | 공간 데이터 인덱스 | 일반 검색 성능 향상 |
| 구조 | 이진 균형 트리 | 계층적 MBR 구조 | B-Tree, 해시, 비트맵 등 |
| 사용처 | In-memory DB | GIS, CAD, 공간 정보 | 대부분의 DBMS |
| 특징 | 빠른 메모리 검색 | 중첩 영역 허용, 다차원 지원 | 용도에 따라 다양한 구조 선택 |
DevSecOps Pentest🚩