B-Tree 인덱스

 

B-Tree 인덱스의 구조는 다음과 같다.

• 테이블에서 순차적으로 데이터를 찾는 것보다 Tree 구조의 인덱스에서 데이터를 더 빠르게 찾을 수 있기 때문에 빠른 조회 성능을 제공한다.

  그런데 B-Tree 인덱스는 우편번호, 상품번호, 고객번호와 같이 고유한 데이터 값의 종류가 많은 경우에는 효율적이지만 성별, 여부와 같이 고유한 데이터 값의 종류가 몇개 없을 때 B-Tree 인덱스를 지정하면 오히려 속도가 늦어질 수 도 있는 경우가 생기기 때문에 고유 데이터 값의 종류가 많은 경우에만 사용해야 한다.

 

 그런데 DW에서 사용하는 SQL 조건절에는 성별이나 여부 등 B-Tree 인덱스 대상이 될 수 없는 컬럼들만이 사용될 수 도 있는데 이런 경우에는 인덱스를 이용한 속도 향상이 이루어 질 수 없다.  

 

 

오라클 인덱스는 B-tree (binary search tree)를 기반으로 하며, 인덱스의 물리적 구조가 좌우 대칭 구조를 이루고 있어 Balance-tree라 한다.

B-tree 인덱스는 컬럼안에 독특한 데이터가 많을 때 효과적이다.

.

B-tree 인덱스는 먼저 주어진 값을 리스트의 중간점에 있는 값과 비교하여 그 값이 크면 작은 쪽 리스트의 절반을 버리고, 그 값이 작으면 큰 쪽 리스트의 절반을 버린다.

하나의 값이 발견될때까지 또는 리스트가 끝날 때까지 그와 같은 작업을 다른 반쪽에도 반복하여 검색이 이루어진다.

위 그림에서 EMP 테이블은 ROWID와 함께 함께 empno 컬럼 값이 1101에서 1700까지 순차적으로 입력되어 있다.

인덱스를 생성하기 위해 CREATE INDEX emp_index ON emp(empno) 문을 실행하면 먼저 EMP 테이블의 empno 컬럼을 분석하고, 가장 중간인 값을 Root-Level 의 블록에 저장한다.

그 다음 중간 값을 기준으로 작은 값과 큰 값에 대한 정보를 각각 branch level의 좌-우 블록에 저장한다.

물론 root level에는 branch level 블록에 대한 정보를 함께 저장하게 도니다.

마지막으로 leaf-level 블록에는 EMP 테이블의 empno 컬럼에 대한 정보를 함께 저장하게 된다.

마지막으로 leaf-level 블록에는 EMP 테이블의 empno 컬럼에 대한 컬럼 정보와 ROWID에 대한 정보가 함께 저장됨으로써 B-Tree가 완성된다.

이제 생성도니 인덱스를 통해 테이블의 데이터가 어떻게 검색되는지 알아 보기 위하여 다음과 같은 SQL문을 실행한다.

 

1. SQL> SELECT * FROM emp
2.  WHERE empno = 1102;

 

사용자가 검색하고자 하는 값(1102)이 root level 보다 작으므로 root-level의 왼쪽에 있는블록을 검색하고, branch level로부터 원하는 컬럼의 인덱스가 어떤 leaf level 블록에 저장되어 있는지 분석한 다음 해당 leaf level블록에서 원하는 컬럼의 인덱스 정보를 찾게 된다.

leaf level 블록으로부터 원하는 인덱스 정보를 찾으면 그 인덱스가 가지고 있는 ROWID와 같은 값을 가진 ROWID를 테이블로 부터 찾게 된다.

 

 

이 글은 스프링노트에서 작성되었습니다.