균형 트리, B Tree (Balanced Tree)
- DBMS에서 가장 일반적인 인덱스로, Leaf Block에 정렬된 데이터와 해당 데이터를 가진 행의 위치를 가리키는 레코드 식별자로 구성된 인덱스
II. Tree 인덱스 검색 절차
위 B Tree 인덱스 구조에서 37을 찾는 경우
| 절차 | 설명 |
|---|---|
| 1단계 | – 루트 블록에서 50보다 작으면 왼쪽 포인터로 이동 |
| 2단계 | – 37은 왼쪽 브랜치 블록의 11과 40 사이의 값이므로 가운데 포인터로 이동 |
| 3단계 | – 이동 결과 해당 블록이 리프 블록이므로 37이 블록 내에 존재하는 지 검사 |
위 B Tree 인덱스 구조에서 37과 50 사이 모든 값 검색
| 절차 | 설명 |
|---|---|
| 1단계 | – 위 Exact Match의 경우와 동일하기 37을 검색 |
| 2단계 | – Leaf Block은 양방향 링크(Double Link)를 가지고 있으므로 50을 만날 때까지 우측으로 이동 |
III. B Tree 인덱스와 Bitmap 인덱스의 비교
| 구분 | B Tree 인덱스 | Bitmap 인덱스 |
|---|---|---|
| 원리 | – Balanced Tree 이용 – Leaf Block 간 Double Link로 연속 데이터 조회 | – 적은 수의 카디널리티를 갖는 데이터에 대해 Bitmap을 구성하여 인덱스 생성 |
| 적합한 응용 | – OLTP – 저장 데이터가 수시로 생성/수정/삭제 경우 | – OLAP, DW, BigData – 자주 변하지 않으며 낮은 카디널리티 |
| 적용 데이터 특성 | – 다양성 유지 – 생성/수적/삭제 빈번 | – 소수의 경우의 수 – 변경이 거의 없음 |
| 인덱스 특성 | – 인덱스에 데이터를 보관하므로 용량 부담 – 다양한 액세스 패턴 수용 – 복잡한 조건 시 인덱스 성능 보장불가 | – DML 작업 시 지속적 Bitmap 크기 커짐 – 인덱스 리빌드 작업 필요 |