인덱스 구조

DBMS는 일반적으로 B*Tree 인덱스를 사용한다.

이 B*Tree 인덱스는 Root node와 Branch node, Leaf node로 구성되어 있다. Root와 Branch 블록에 있는 각 레코드는 하위 블록에 대한 주소 값을 가진다.

리프 블록에 저장된 각 레코드는 키값 순으로 정렬돼 있고, 테이블 레코드를 가리키는 주소값(ROWID)를 갖는다.

ROWID의 구조는 아래와 같다.

ROWID = 오브젝트번호(6자리) + 데이터 파일 번호(3자리) + 블록 번호(6자리) + 데이터 번호(3자리)

EMP 테이블의 각 레코드의 오브젝트 번호는 AAAE5p 이다. 오브젝트별로 유일한 값이므로 EMP 테이블의 모든 오브젝트번호는 AAAE5p 이다.

데이터 파일 번호는 AAB이다. 테이블의 Extent가 다른 데이터 파일에 할당될 수 있기 때문에, 데이터 파일 번호는 다를 수 있다.

블록번호는 AAALCJ 이다. 블록 번호는 해당 데이터가 저장돼 있는 블록을 뜻한다. 참고로, 액세스하고자 하는 데이터들이 같은 블록 안에 저장돼 있으면 성능이 많이 향상된다.

그리고 각 레코드의 데이터 번호는 AAA->AAB->AAC 등으로 진행된다.

인덱스 탐색은 수직적 탐색과 수평적 탐색으로 나눌 수 있다.

인덱스 수직적 탐색 

정렬된 인덱스 레코드 중 조건을 만족하는 첫 번째 레코드를 찾는 과정이다., 즉 인덱스 스캔 시작지점을 찾는 과정이다. 인덱스 수직적 탐색은 루트 블록에서부터 시작한다. 루트를 포함해 브랜치 블록에 저장된 각 인덱스 레코드는 하위 블록에 대한 주소값을 갖는다. 루트에서 시작해 리프 블록까지 수직적 탐색이 가능한 이유다.^[각주:1]

인덱스 수평적 탐색

수직적 탐색을 통해 스캔 시작점을 찾았으면, 찾고자 하는 데이터가 더 안나타날 때까지, 인덱스 리프 블록을 수평적으로 스캔한다. 인덱스에서 본격적으로 데이터를 찾는 과정이다. 인덱스 리프 블록끼리는 서로 앞뒤 브록에 대한 주소값을 갖는다. 즉, 양방향 연결 리스트 구조다.^[각주:2]

1. 조시형, 친절한 SQL 튜닝, DBian, 2018, p77 [본문으로]
2. 조시형, 친절한 SQL 튜닝, DBian, 2018, p78 [본문으로]