CH01.인덱스 원리와 활용 - 01. 인덱스 구조

(1) 범위 스캔
테이블은 처음부터 끝까지 모든 레코드를 읽어야 완전한 결과집합을 얻을 수 있지만 인덱스는 키 컬럼 순으로 정렬돼 있기 때문에 특정 위치에서 스캔을 시작해 검색 조건에 일치하지 않는 값을 만나는 순간 멈출 수 있습니다.
이것이 범위 스캔(Range Scan)입니다.
테이블도 인덱스가 결합된 테이블인 IOT(index - organized table)는 특정 컬럼 순으로 정렬 상태를 유지하며 값을 입력하므로 범위 스캔이 가능합니다. 이를 제외한다면 일반적인 힙 구조 테이블(heap - organized table)에서 범위 스캔은 있을 수 없습니다.
아무리 정렬 상태가 유지되게 테이블의 데이터를 입력하더라도 옵티마이저는 그것을 신뢰하지 않고, Table Range Scan같은 실행계획을 수립하지 않습니다.

(2) 인덱스 기본 구조
여러 종류의 인덱스 중 가장 일반적으로 사용되는 B*Tree 인덱스 구조는 아래의 모습입니다.

Root를 포함한 Branch 블록에 저장된 엔트리에는 하위 노드 블록을 찾아가기 위한 DBA(Data Block Address)정보를 갖고, Leaf블록에는 인덱스 키 컬럼과 함께 해당 테이블 레코드를 찾아가기 위한 주소정보(rowid)를 갖습니다. 리프 블록은 항상 키 컬럼 순으로 정렬돼 있기 때문에 ‘범위 스캔’이 가능합니다. 키 값이 같을 때는 rowid순으로 정렬됩니다.

브랜치 노드와 각 엔트리에는 키 값과 하위 노드를 가리키는 블록 주소를 갖습니다. 그런데 키 값을 갖지 않는 특별한 엔트리가 있는데, 각 브랜치 노드의 첫 번째 엔트리가 그렇습니다. 이를 lmc(LeftMostChild)라고 부릅니다. 다른 엔트리는 자신의 키값과 같거나 큰 값을 담은 리프 노드 블록을 가리키는 반면 lmc는 명시적인 키 값을 갖지 않더라도, ‘키 값을 가진 첫번째 엔트리보다 작은 값’의 의미를 갖는다. 따라서 그 브랜치 블록의 자식 노드 중 가장 왼쪽 끝에 위치한 블록을 가리킵니다.

오라클은 인덱스 구성 컬럼이 모두 null인 레코드는 저장하지 않습니다. 그리고 (인덱스 구성 컬럼이 모두 null인 경우를 제외하면) 인덱스와 테이블 레코드 간에는 서로 1:1 대응 관계를 갖습니다. 참고로 클러스터 인덱스(Cluster Index)는 1:M 관계를 갖습니다.
브랜치에 저장된 레코드 개수는 바로 하위 레벨 블록 개수와 일치한다는 점도 기억할 필요가 있습니다. 위의 그림에서 루트 블록의 레코드가 2개이므로 브랜치 블록도 2개인것을 확인할 수 있고 브랜치 블록이 8개이므로 리프블록도 8개일 것입니다.

인덱스 리프 노드상의 레코드와 테이블 레코드 간에는 1:1관계라 값도 서로 일치합니다. 따라서 테이블 레코드에서 값이 갱신되면 리프 노드 인덱스 키 값도 같이 갱신(delete&insert)됩니다.
반면, 리프 노드상의 엔트리 키 값이 갱신되더라도 브랜치 노드까지 값이 바뀌지는 않습니다. 브랜치 블록에 놓인 엔트리는 자신의 키 값과 같거나 큰 값을 담는 하위 노드 블록을 포인팅하는 것으로, 그 키값은 자식 노드가 갖는 값의 범위를 나타내기 때문입니다. 따라서 키 값이 하위 노드의 첫 번째 레코드와 정확히 일치하지 않습니다.
참고로, 브랜치 노드는 인덱스 분할(split)에 의해 새로운 블록이 추가되거나 삭제(다른 브랜치의 자신 노드로 이동)될 때만 갱신됩니다.

아래는 요약입니다.
- 리프 노드상의 인덱스 레코드와 테이블 레코드 간에는 1:1 관계
- 리프 노드상의 키 값과 테이블 레코드 키 값은 서로 일치
- 브랜치 노드상의 레코드 개수는 하위 레벨 블록 개수와 일치
- 브랜치 노드상의 키 값은 하위 노드가 갖는 값의 범위를 의미

(3) 인덱스 탐색
수직적 탐색과 수평적 탐색으로 구분해 설명할 수 있습니다. 수평적 탐색은 범위 검색(Range Scan)을 말하는 것이며, 리프 블록을 인덱스 레코드 간 논리적 수서에 따라 좌에서 우로, 우에서 좌로 스캔하기 때문에 수평적 탐색이라고 표현합니다.
수직적 탐색은 수평적 탐색을 위한 시작 지점을 찾는 과정이라고 할 수 있으며, 루트에서 리프블록까지 아래쪽으로 진행하기 때문에 수직적입니다.

브랜치 블록 스캔
인덱스 탐색과정 중 브랜치 블록을 스캔할 때는 뒤에서부터 스캔하는 방식이 유리합니다. ‘CLARK’를 찾는 예로 들면 뒤에서부터 스캔할 때는 clark보다 작은 첫 번째 레코드를 만나는 순간 바로 하위 블록으로 내려가면 되지만, 앞에서부터 스캔할 때는 clark보다 크거나 같은 첫 번째 레코드를 만나는 순간 멈취서 한 칸 뒤로 이동해야 하기 때문입니다.
하지만 실제로 오라클이 뒤쪽부터 스캔하는지는 알 수 없습니다.
브랜치 블록을 따라 수직적 탐색을 진행할 때는 찾고자 하는 값보다 키 값이 작은 엔트리를 따라 내려간다는 사실도 기억할 필요가 있습니다. 아래 그림처럼 중복 값이 많은 인덱스를 탐색해 내려가다 보면 그 이유를 자연스럽게 이해할 수 있습니다.

만약 3인 레코드를 찾는다고 했을 때, 1번 루트 블록에서 lmc가 가리키는 2번 브랜치 블록으로 내려가야 합니다. 만약 같은 값인 3을 따라 두번째 브랜치 블록으로 내려가면 2번 브랜치 블록 끝에 놓은 3을 놓치게 되기 때문입니다.
이제 도착한 2번 브랜치에서 맨 뒤쪽 3부터 거꾸로 스캔하다가(오라클은 뒤부터 스캔한다고 가정) 2를 만나는 순간 리프 블록으로 내려갑니다. 거기서 키 값이 3인 첫 번째 레코드를 찾아 오른쪽으로 리프 블록을 스캔해 나가면 조회 조건을 만족하는 값을 모두 찾을 수 있습니다.

결합 인덱스 구조와 탐색

위의 그림은 emp테이블에 deptno + sal 컬럼 순으로 생성한 결합 인덱스를 도식화한 것입니다.
deptno = 20 and sal >= 2000 조건으로 쿼리할 때 두 번째 리프 블록 그 중에서도 두 번째 레코드로부터 스캔이 시작됩니다.
이는 수직적 탐색 과정에서 deptno 뿐만 아니라 sal 값에 대한 필터링도 같이 이루어지기 때문입니다. 그리고 마지막 블록 첫 번째 레코드에서 스캔을 멈추게 될 것입니다.(마지막 블록은 deptno = 30이기 때문입니다.)

(4) ROWID 포맷
rowid에는 데이터파일번호, 블록 번호, 로우 번호 같은 테이블 레코드의 물리적 위치정보를 포함합니다. 테이블 레코드를 찾아가는 데 필요한 주소 정보이므로 테이블 자체에 저장되는 것이 아니라 인덱스에 저장됩니다. 필요하면 rowid를 출력해 볼 수 있지만 그 값이 테이블에 실제 저장돼 있지는 않습니다. pseudo 컬럼입니다.
인덱스를 거치지 않는 쿼리에서 rowid를 요구할 때면 어떻게 그 값을 출력할깡? 오브젝트 및 데이터파일 번호 그리고 그 파일 내에서의 상대적인 블록 번호가 데이터블록 헤더에 저장돼 있기 때문에 어렵지 않습니다. 레코드를 읽는 시점에 현재 도달한 블록 헤더와 각 레코드에 할당된 슬롯 번호를 이용해 충분히 가공할 수 있는 것입니다.
그러면 인덱스에 저장된 rowid는 얼마만큼의 공간을 차지할까요? 오라클 7버전까지 rowid는 내부적으로 6bytes의 크기를 차지하며 파일번호, 블록번호, 로우 번호로 구성됩니다.
오라클 8i부터는 10bytes로 증가되었고, 파티션 같은 기능을 지원하기 위해 오브젝트 번호까지 저장할 필요가 생겼기 때문입니다. rowid를 10bytes로 늘림으로써 오라클은 tera를 넘어 peta단위의 데이터를 저장할 수 있게 되었습니다.
하지만 무조건 10bytes를 저장하는 것은 아니고 테이블과 인덱스 유형에 따라 6bytes를 사용하기도 합니다. 아래는 6bytes를 사용하는 경우입니다.
- 파티션되지 않은 일반 테이블에 생성한 인덱스
- 파티션된 테이블에 생성한 로컬 파티션(Local Partitioned) 인덱스

아래 경우는 10bytes를 차지합니다.
- 파티션 테이블에 생성한 글로벌 파티션 인덱스
- 파티션 테이블에 생성한 비파티션 인덱스

rowid 사이즈가 달라지면서 외부로 출력되는 rowid포맷도 달라졌고, 새로운 포맷을 확장(extended)rowid 포맷, 이전에 사용되던 포맷을 제한(restricted) rowid 포맷이라고 부르게 되었습니다.