[데이터 베이스] 인덱스 동작과정

인덱스 동작과정에 대해서 알아보자

 

RDBMS에서 대용량으로 데이터가 있을때, 해당 데이터를 full scan하는 것이아니라

특정 컬럼들을 키로, 해당 데이터들을 가지고있어서, 필요할때 range scan을 하면서 검색 효율을 높이는 것이다.

range Scan이란, 특정 위치에서 검색을 시작해, 일치 하지 않는 범위를 만나면 멈추는 것을 의미한다.

 

가장 일반적인 인덱스 는 비트리 형태로 이루어져 있다.

 

비트리(B-tree)란?

* 모든 리프 노드들이 같은 레벨을 가질수 있도록 관리되는 이진 트리이다.

비트리에서의 탐색과정은, 검색 대상을 key와 비교하고, 해당 key보다 크면, 더 큰 key값으로 이동하여, 범위에 맞는

예를 들면, 10,20이 키면, 18검색시에, 10과 20사이의 key값에 해당하는 자식 노드를 검사한다.

이런식으로 자식 노드에 대한 검사를 진행하면서, 원하는 결과를 찾는다.

비트리에 대한건 추후 별도 포스팅 예정이다.

 

 

 

비트리에서는, 3가지의. Block이 있다.

최상위 Root Block과, 마지막 leaf Block 그리고 둘다 해당안되는 가운데의 노드를 BranchBlock으로 표현한다.

 

위 표에서 49를 찾고자 한다면,

1) Root Block에서, 49의 범위를 찾는다. 60보다 작으므로, 해당 11,40이있는 브랜치로 내려온다

2) 해당 자식 노드에서는 40보다 크므로, 45~ 되어있는 Block으로 내려온다.

 

모든 블록 공통

-인덱스 데이터는 순서대로 정렬 되어있다.

 

브랜치 블록

-가장 상위의 블록을 루트 블록이라고한다.

-분기를 목적으로 하는 블록이며, 다음 블록에 대한 포인터를 가진다.

 

리프 블록

- 인덱스를 구성하는 컬럼의 데이터 

- 해당 데이터를 가지는 행의 식별자

-양방향 링크를 가져, 오름차순 내림 차순 검색이 가능하다.

 

따라서 인덱스에 대한 구조는, between =,>.< 등등 범위검색이 가능하다.