[SQL] B-Tree 인덱스

인덱스 종류 중에서 가장 흔히 쓰이는 B-Tree 인덱스 입니다.
프로그래밍 해보신분들 중에 자료구조 들으신분들은 조금 친숙하실텐데요.

 B-Tree(이하 비트리) 를 구성할 당시에는 각 데이터가 저장되어 있는 데이터 블록으로 부터 해당 컬럼을 이용해서 인덱스를 만듭니다.
그리고 위에 보시는 Root 블록으로 부터 Branch 블록, Leaf 블록으로 구성합니다. 
 데이터 블록에서 Leaf 블록을 구성할 때에는 해당 컬럼을 정렬해서 만들어 집니다.

 이중 Leaf 블록이 데이터 블록의 해당 로우(ROW)에 접근할 수 있는 ROW ID를 가지고 있구요.
그 상위 단계인 Branch와 Root 에서는 각 하위 단계에 접근 할 수 있는 키값 즉 블록의 주소를 가지고 있습니다.

 그리고 각 Branch 블록과 Root 블록에서는 각 하위 레벨이 가지고 있는 최소값(각 블록의 처음값)을 각각 가져옵니다.
검색시에는 Root 블록으로부터 가지고 있는 엔트리 값을 비교후 블록주소를 통해서 차례차례 찾아 값니다.

 예를 들면 이 인덱스를 이용해서 부서 번호가 30인 사원을 찾고자 한다면 Root 에서 가지고 있는 엔트리 값을 비교합니다.
30은 10과 130 사이에 있으므로 10 정보가 담겨있는 2000번 블록(Branch)으로 찾아갑니다.

 그리고 Root블록처럼 비교를 해서 Leaf블록으로 간다음. 해당 값의 ROW ID를 참조하여 데이터 블록으로 액세스 합니다. 

 수동 인덱스나 자동 인덱스로 만드는 것은 모두 B-tree 인덱스로, 비트리 인덱스는 가장 많이 사용되는 인덱스 구조입니다.
비트리 구조가 가지는 장점은 잘 구성이 되어 있다면 어느 ROW든 접근시 동일한 수만큼의 블록에 접근합니다.
즉, 동일한 성능의 퍼포먼스를 기대 가능하겠다라는 겁니다.

 하지만 반대로 생각한다면, 잦은 DML 작업 등으로 아래와 같이 비대칭형 비트리 구조로 흐뜨려져 있다면,
각 ROW에 대해서 동일한 성능을 기대할 수 없으므로 재구성 즉, Index Rebuild 작업이 필요합니다.
참고로 B-tree는 Balanced tree 로서 대칭형의 모양을 일컫습니다.

도움 되셨다면 밑의 추천(손가락 표시)과 댓글 부탁드립니다.