[DB] Oracle - B tree INDEX

오라클에서 사용하는 B tree 인덱스와 Bitmap 인덱스 중 B tree 인덱스에 대해서 먼저 알아보도록 하자.

여기서 B tree의 개념에 대해서 설명하기에는 제한사항이 있으므로 B tree의 대략적인 개념을 알고있다는 가정하에 오라클에서 지원하는

B tree 인덱스에 대해서 살펴보겠다.

B tree는 이름대로 나뭇가지와 같은 모양을 하고 있으며 B tree의 B는 Balanced를 의미한다. 여기서 말하는 Balanced는 우리가 찾고자 하는

어떤 대상값을 찾기위한 cost가 균일하다는 것을 의미하며, 이렇게 할 수 있는 이유는 상위 노드가 하위 노드값의 범위를 갖고 있기 때문이다.

위의 형태가 쉽게 생각할 수 있는 B tree의 구조이다. 가장 상위의 노드를 Root Block, 중간노드는 Branch Block,

마지막으로 가장 하위의 노드를 Leaf Block이라고 부른다.  밑에서 설명하겠지만 Branch Block은 Leaf Block의 확장에 의해

여러 단계를 가질 수 있다.


인덱스 로우의 구성 요소 중 실제로 데이터 저장공간과 관련이 있는 Rowid 부분을 살펴보자.

이렇게 Rowid에는 실제로 데이터가 저장된 공간의 위치를 확실하게 알 수 있는 정보를 포함하고 있다. 실제로는 10자리로 저장되며,

위와같은 형태는 SQL을 통해 추출했을 시 나타난다.


[인덱스 생성]
 
이번에는 인덱스가 생성되는 과정에 대해서 살펴보도록 하자.

왼쪽에 위치한 Temp Segment의 경우 색 구분을 통해 알 수 있듯이 이미 정렬과정을 거친 것이다.

이렇게 정렬된 데이터를 Leaf Block에 채우기 시작하는데 인덱스 생성시 PCTFREE에서 설정한 값만큼만

데이터를 채우고 저장공간이 부족할 경우 다른 Leaf Block을 생성한다

이때 Branch Block 또한 생성되고 기존 Leaf Block의 DBA(Data Block Address)를 블록 헤드에 기록하며,

Leaf Block에 관련된 정보 Row를 만든다.

이때 만들어진 Branch Block이 Root Block이기도 하다. 이런 과정을 지속적으로 거치면 나뭇가지 처럼 생성된 B tree 인덱스를 볼 수 있으며,

앞에서 잠깐 이야기 했지만 Branch Block의 depth가 더 많아질 수 있다.

인덱스의 생성이 다음과 같은 방식으로 이루어지기 때문에 Branch Block의 depth를 감소시키기 위해서는

하나의 인덱스 블록에 많은 인덱스 로우가 저장되어야 하며 이를 위한 방법으로 인덱스 컬럼의 수를 줄인다거나, 큰 블록 사이즈를 지정,

PCTFREE를 최소로 정의, 키 압축 등이 있다. 


[인덱스 분할]
 
다음은 인덱스 블록이 분할되는 과정에 대해서 살펴보자. 인덱스의 분할은 인덱스 row가 새로 추가될 때 발생한다.

위와 같이 새로운 row가 추가될때는 두가지 경우가 존재할 수 있다.

현재 존재하는 블록의 중간에 row가 추가될 경우와, 마지막에 추가되는 경우이다.

마지막에 row가 추가될 경우 새로운 블록을 생성하면 되기 때문에 별다른 제한사항이 없지만 문제는 중간에 row가 추가될 경우이다.

인덱스가 생성될 때 사용자가 지정한 PCTFREE를 제외한 만큼 row수를 채우기 때문에, 블록 중간에 row가 들어갈 수는 없다.

그렇기 때문에 중간에 row 추가요청이 발생할 경우 새로운 인덱스 블록을 생성하고 데이터를 나눠서 2/3까지만 채우도록 한다. 향후 또 다른

인덱스 row 변화에 대응하기 위한 조치이다. 하지만 이렇게 인덱스가 계속 늘어날 경우 쓸모없는 공간을 많이 차지할 수 있기 때문에

주기적인 인덱스 rebuild를 필요로 한다.


 
[인덱스 데이터 삭제 및 갱신] 

인덱스 데이터 삭제시에는 실제로 데이터의 삭제과정이 일어나는 것은 아니다. 다만 인덱스 로우에 삭제를 의미하는 표시가 추가될 뿐이며,

만약 Leaf Block의 모든 로우가 삭제될 경우 상위 Branch Block에도 해당 Leaf Block의 삭제 표시를 포함한다. 

인덱스 데이터의 수정은 삭제 과정 후 삽입의 형태로 발생한다. 인덱스 로우 정렬을 위한 필수적인 과정이고 이때문에 수정이 빈번하지 않은

컬럼을 인덱스로 사용하는 것이 좋다. 

삭제를 하더라도 실데이터 삭제가 아닌 삭제표시, 갱신의 경우 삭제 후 삽입 과정을 거치기 때문에 위에서도 언급한 인덱스의 주기적 rebuild를

필요로 한다.


[인덱스를 이용한 검색]

 인덱스의 생성, 삭제, 수정 등에 대해서 살펴보았다. 이번에는 실제로 검색시 어떻게 사용되는지 살펴보도록 하자.

가장 상위노드가 Root Block, 다음이 Branch Block, 마지막이 Leaf Block 되겠다. 쿼리를 보면 알 수 있듯이 col1의 B값과 col2의 ACC 값을 

찾고있다. 여기서 Term은 원래 컬럼값에서 일부가 잘린것을 의미한다. 

Root Block에서 검색해본 결과 dba가 21인 Block이 col1의 'B'와 같다. 21번의 Block에서 다시 검색해 본 결과 col1의 'B'는 일치하나

col2의 'ACC' 보다는 더 큰 값 'B'를 가지고 있다. 이럴 때는 lmc에 있는 Block을 찾아간다. 20번 Block에서 해당하는 값을 찾았다.

Rowid에 해당하는 테이블을 찾아가면 우리가 원하는 값을 row를 찾을 수 있다.

Like 문의 사용등을 통한 범위스캔을 할 경우(ex col1= 'b' col2 like 'ac%') ac와 같거나 큰것에서 스캔을 시작, ad보다 작으면

테이블에 액세스하고 그렇지 않을 경우 종료한다.



여기서 Block간의 주소를 찾아가는 규칙을 살펴보자.

주어진 값가 같거나 크지만 최소값인 것을 찾는다.
    - 블록이 갖고있는 row가 찾는값과 같을 경우 해당하는 주소를 찾아간다
    - 블록이 갖고있는 row가 찾고있는 값보다 클 경우 lmc에 해당하는 주소를 찾아간다
    - 블록이 갖고있는 row가 찾고있는 같은 값이 없는 경우 큰 것중 가장 작은값의 주소를 찾아간다
 



* 출처 : 새로쓴, 대용량 데이터베이스 솔루션 (이화식 저)