인덱스 수직적 탐색, 수평적 탐색

인덱스

 

데이터베이스에서 인덱스 없이 검색하려면, 테이블을 처음부터 끝까지 모두 읽어야한다. 반면, 인덱스를 이용하면 일부만 읽고 멈출 수 있다. 범위 스캔(Range Scan)이 가능하며 가능한 이유는 인덱스는 정렬 돼있기 때문이다.

​

DBMS는 일반적으로 B-Tree 인덱스를 사용한다. 상단에 Root 블록, 중간에 Branch 블록, 맨 아래 Leaf 블록이 있다.

루트와 브랜치 블록에 있는 각 레코들은 하위 블록에 대한 주소값을 갖는다.

루트와 브랜치 블록엔 키값을 갖지 않는 특별한 레코드가 있다. 이를 'LMC'라고 하며 'Leftmost Child'의 줄임말이다. LMC는 자식 노드 중 가장 왼쪽 끝에 위치한 블록을 가리킨다. LMC가 가리키는 주소로 찾아간 블록에는 키 값을 가진 첫 번째 레코드보다 작거나 같은 레코드가 저장돼있다.

​

인덱스 수직적 탐색

인덱스 수직적 탐색이란?

정렬된 인덱스 레코드 중 만족하는 첫 번째 레코드를 찾는 과정, 즉 인덱스 스캔 시작지점을 찾는 과정이다

예시1)

'이재희'를 찾아라!

1. 루트 블록에 '이재희'보다 크거나 같은 값이 없다. 그렇기 때문에 마지막에 있는 '서' 레코드의 하위 블록으로 이동한다.

(루트와 브랜치 블록의 레코드는 하위 블록의 주소값이 있기 때문에 찾아갈 수 있다.)

2. 브랜치 블록에서 '이재희'보다 큰 '정재우' 레코드를 찾았다. 바로 직전 레코드인 '이재룡'이 가리키는 하위 블록으로 이동한다.

3. 이제 리프 블록에 도달했고 조건('이재희')을 만족하는 첫 번째 레코드를 찾았다.

​

예시2)

'강덕승'을 찾아라!

1. 루트 블록에 '강덕승'보다 큰 '서'레코드가 있기 때문에 바로 직전 레코드인 'LMC'이 가리키는 하위 블록으로 이동한다.

2. 브랜치 블록에 '강덕승'과 일치하는 레코드를 찾았다. 하지만 바로 '강덕승'이 가리키는 하위 블록으로 이동하면 안되고, 바로 직전 레코드인

'LMC' 가리키는 하위 블록으로 이동해야 첫 번째 리프블록 맨 마지막에 저장된 '강덕승' 레코드를 빠뜨리지 않는다.

(수직적 탐색은 조건을 만족하는 레코드가 아니라 조건을 만족하는 첫 번째 레코드를 찾는 과정임을 기억해야한다!)

​

인덱스 수평적 탐색

인덱스 수평적 탐색이란?

수직적 탐색으로 스캔 시작점을 찾았으면, 찾고자 하는 데이터가 더 안 나타날 때까지 인덱스 리프 블록을 수평적으로 스캔한다. 즉, 인덱스에서 본격적으로 데이터를 찾는 과정이다.

​

인덱스 리프 블록은 양방향 연결 리스트(double linked list)이기 때문에, 서로 앞뒤 블록에 대한 주소값을 갖는다. 그래서 리프 블록 좌, 우로 수평적 탐색이 가능하다.

​

수평적 탐색 이유?

1. 조건절을 만족하는 데이터를 모두 찾기 위해

2. ROWID를 얻기 위해

=> 필요한 컬럼을 인덱스가 모두 갖고 있어서 인덱스만 스캔하고 끝나는 경우도 있지만, 일반적으로 인덱스를 스캔하고 테이블도 액세스한다.

이때, ROWID가 필요하기 때문이다.

 

 

 

[출처] [Index] 인덱스 수직적 탐색, 수평적 탐색|작성자 hgstudy