B Tree (Balanced Tree)

균형 트리, 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 크기 커짐

– 인덱스 리빌드 작업 필요

콘텐츠 사용 시 출처 표기 부탁 드리고, 댓글은 큰 힘이 됩니다^^