t-tree, r-tree, index

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-트리, 해시, 비트맵 인덱스 등을 사용.

종류 및 특징:

1. B-Tree Index:

   • 가장 일반적인 인덱스 구조.
   • 균형 잡힌 트리, 범위 검색에 유리.

2. Bitmap Index:

   • 컬럼 값이 중복이 적을 때 (low cardinality) 효과적.
   • 주로 데이터웨어하우스, OLAP 등에서 사용.

3. Hash Index:

   • 정확한 값 검색에 빠름 (등치 조건).
   • 범위 검색은 불가능.

정리 표: