by-nc-sa     개발자, DBA가 함께 만들어가는 구루비 지식창고!

1. 인덱스 구조




01. 인덱스 원리와 활용

01. 인덱스 구조

(1) 범위 스캔

  • 범위(Range)스캔 : 인덱스는 키 컬럼 순으로 정렬돼 있기 때문에 특정 위치에서 스캔을 시작해 검색 조건에 일치하지 않는 값을
    만나는 순간 멈추는 것.
    (IOT(index-organized table)는 특정 컬럼 순으로 정렬 상태를 유지하며 값을 입력하므로 범위스캔가능)

(2) 인덱스 기본 구조

  • p.17 그림 1-1 참조
  • 루트(Root)를 포함한 브랜치(Branch)블록 각 엔트리에는 하위 노드 블록을 찾아가기 위한 DBA(Data Block Address) 정보를 저장.
  • lmc(LeftMost Child)는 키 값을 가진 첫 번째 엔트리보다 작은 값의 의미.
  • 다른 엔트리는 자신의 키 값과 같거나 큰 값을 담은 자식 노드 블록을 가르킨다.
  • 리프(Leaf)블록에는 인덱스 키 컬럼과 함께 해당 테이블 레코드를 찾아가기 위한 주소정보(rowed)를 저장. 항상 키 컬럼 순으로 정렬.
    키 값이 같을 때는 rowid순으로 정렬.
  • 인덱스 구성 컬럼이 모두 null인 레코드는 저장하지 않는다.
  • 인덱스와 테이블 레코드는 1:1 대응 관계
  • 클러스터 인덱스(Cluster Index)는 1:M 관계
  • 브랜치에 저장된 레코드 개수는 바로 하위 레벨 블록 개수와 일치(lmc 포함)
  • 테이블 레코드에 값이 갱신되면 리프 노드 인덱스 키 값도 같이 갱신(delete & insert)
  • 브랜치 노드는 인덱스 분할(Split)에 의해 새로운 블록이 추가 되거나 삭제 될 때만 갱신.
  • 브랜치 노드상의 키 값은 하위 노드가 갖는 값의 범위를 의미

(3) 인덱스 탐색

  • 수평적 탐색 : 범위 스캔, 리프블록을 인덱스 레코드 간 논리적 순서에 따라 스캔
  • 수직적 탐색 : 수평적 탐색을 위한 시작 지점을 찾는 과정. 루트에서 리프 블록까지 아래로 진행.
  • p.17 그림 1-1 에서 'CLARK'을 찾는 과정
    1. 루트 블록 스캔 (lmc는 'KI'보다 작은 모든 값을 의미, 'KI'는 'KI'보다 크거나 같은 모든 값을 의미) -> 왼쪽 브랜치 블록으로 이동
    2. 찾아간 브랜치 블록을 스캔하면서 그 다음 찾아갈 인덱스 블록을 탐색.
    ('CLARK'이 'BER' 보다 크고 'FO' 보다 작다) -> 두번째 레코드가 가리키는 블록 주소로 이동
    3. 리프 블록에서 찾으면 수평적 탐색과정, 못 찾으면 거기서 인덱스 탐색을 마친다.
    4. 인덱스 리프 블록을 스캔하면서 값이 'CLARK'인지 확인
    5. 'CLARK'이면 거기서 얻은 rowid를 이용해 해당 테이블 레코드를 찾아가 필요한 다른 컬럼 값을 읽는다.
    (쿼리에서 인덱스 컬럼만 필요로 한다면 이 과정은 생략)
    6. 4번과 5번을 반복하다가 검색조건을 만족하지 못하는 레코드를 만나는 순간 멈춘ㄴ다.

브랜치 블록 스캔

  • 브랜치 블록을 스캔할 때는 뒤에서부터 스캔하는 방식이 유리하다.
  • 뒤에서부터 스캔할 때는 검색하고자 하는 값보다 작은 첫 번째 레코드를 만나는 순간 바로 하위 블록으로 내려가면 되지만,
    앞에서부터 스캔시에는 검색하고자 하는 값보다 크거나 같은 첫번째 레코드를 만나는 순간 멈춰서 한 칸 뒤로 이동해야 하기 때문
  • 브랜치 블록을 따라 수직적 탐색을 진행할 때는 찾고자 하는 값보다 키 값이 작은 엔트리를 따라 내려간다.
  • p.20 그림 1-2 인덱스를 통해 값이 3인 레코드를 찾을 경우
    1. 1번 루트 블록에서 lmc가 가리키는 2번 브랜치 노드로 따라 내려가야 한다.
    (같은 값인 3을 따라 3번 브랜치로 내려가면 2번 브랜치 끝에 놓인 3을 놓치게 된다)
    2. 2번 브랜치에서 맨 뒤쪽 3부터 거꾸로 스캔하다가 2를 만나는 순간 리프 블록으로 내려간다.
    3. 키 값이 3인 첫 번째 레코드를 찾아 오른쪽으로 리프 블록을 스캔해 나간다.

결함 인덱스 구조와 탐색

  • p.21 그림 1-3 'deptno = 20 and sal >= 2000' 조건 검색
  • deptno가 20인 첫 번째 레코드가 스캔 시작점이라고 생각하기 쉽다. 하지만 두 번째 리프 블록, 그 중에서도
    두 번째 레코드부터 스캔이 시작된다.
  • 수직적 탐색 과정에서 deptno 뿐만 아니라 sal 값에 대한 필터링도 같이 이루어지기 때문.
    (개인 의견 : 랜덤엑세스가 필요한 경우는 해당되는 리프 블록의 처음부터 스캔하지만 랜덤엑세스는 두번째 레코드 부터 시작된다.
    인덱스만을 읽는다면 리프 블록 처음부터 조건이 해당되지 않는 레코드까지 스켄이 이루어 진다)

(4) ROWID 포맷

  • 테이블자체에 저장되는 것이 아니라 인덱스에 저장
  • 오라클 7 이하 버전 6 byte
  • 오라클 8 이후 버전 중 파티션되지 않은 일반 테이블에 생성한 인덱스, 파티션된 테이블에 생성한 로컬 파티션 인덱스 6 byte
  • 오라클 8 이후 버전 중 파티션 테이블에 생성한 글로벌 파티션 인덱스, 파티션 테이블에 생성한 비파티션 인덱스. 10 byte

제한 rowed 포맷

  • 오라클 7 이하 버전
  • 데이터파일 번호(4자리) : 로우가 속한 데이터파일 번호, 데이터베이스내에서 유일 값.
  • 블록번호(8자리) : 로우가 저장된 데이터 블록 번호, 데이터파일 내에서의 상대적 번호
  • 로우번호(4자리) : 블록 내에서 각 로우에 붙여진 일련번호, 0부터 시작
  • 구분자 '.(dot)' 기호를 포함해 18자리 문자열.
  • 순서는 블록, 로우, 데이터파일 (00000DD5.0000.0001)

확장 rowed 포맷

  • 오라클 8 이후 버전
  • 데이터 오브젝트 번호(6자리) : 세그먼트를 식별하기 위해 사용되는 데이터 오브젝트 번호
  • 데이터파일 번호(3자리) : 로우가 속한 데이터파일 번호, 테이블스페이스 내에서의 상대적인 파일 번호
  • 블록번호(6자리) : 로우가 저장된 데이터 블록 번호, 데이터파일 내에서의 상대적 번호
  • 로우번호(3자리) : 블록 내에서 각 로우에 붙여진 일련번호, 0부터 시작
  • 6 바이트든 10 바이트든 출력되는 포맷은 별도 구분 없이 연속된 18자리 문자열(AAAM6PAAEAAAE2cAAA)
  • 순서는 데이터 오브젝트, 데이터파일, 블록, 로우
  • rowid를 자릿수만큼 잘라서 디코딩(Decoding)하면 각 구성요소에 대한 정보 출력.
  • dbms_rowid 패키지 사용
    select rowid extended_format
           , dbms_rowid.rowid_to_restricted(rowid, 0) restricted_format
           , dbms_rowid.rowid_object(rowid) object
           , dbms_rowid.rowid_relative_fno(rowid) file_no
           , dbms_rowid.rowid_block_number(rowid) block_no
           , dbms_rowid.rowid_row_number(rowid) row_number
      from   emp e
      where  empno = 7369;
    
    EXTENDED_FORMAT    RESTRICTED_FORMAT      OBJECT    FILE_NO   BLOCK_NO ROW_NUMBER
    ------------------ ------------------ ---------- ---------- ---------- ----------
    AAAMgzAAEAAAAAgAAA 00000020.0000.0004      51251          4         32          0
    
    select dbms_rowid.rowid_type('AAAM6PAAEAAAE2cAAA') extended_format
           , dbms_rowid.rowid_type('00004D9C.0000.0004') restricted_format
      from   dual;
    
    EXTENDED_FORMAT RESTRICTED_FORMAT
    --------------- -----------------
                  1                 0
    
- 브랜치 블록의 엔트리에 키 값을 저장시에는 압축 알고리즘 적용
- 모든 키값이 다 같을 경우는 하위 노드에 저장된 rowid 값까지 저장

begin
for i in 1..1000
loop
insert into t values (i, i);
end loop ;
commit;
end ;

Branch block dump
=================
header address 116152908=0x6ec5a4c
kdxcolev 1
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 3
kdxcosdc 1
kdxconro 66
kdxcofbo 160=0xa0
kdxcofeo 7472=0x1d30
kdxcoavs 7312
kdxbrlmc 25165847=0x1800017
kdxbrsno 65
kdxbrbksz 8060 
kdxbr2urrc 0
row#0[8052] dba: 25165848=0x1800018
col 0; len 2; (2):  c1 11
col 1; TERM
row#1[8044] dba: 25165845=0x1800015
col 0; len 2; (2):  c1 20
col 1; TERM
...

==============================================

begin
for i in 1..1000
loop
insert into t values (1, i);
end loop ;
commit;
end ;

Branch block dump
=================
header address 116152908=0x6ec5a4c
kdxcolev 1
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 3
kdxcosdc 1
kdxconro 89
kdxcofbo 206=0xce
kdxcofeo 7055=0x1b8f
kdxcoavs 6849
kdxbrlmc 25165847=0x1800017
kdxbrsno 88
kdxbrbksz 8060 
kdxbr2urrc 0
row#0[7956] dba: 25165849=0x1800019
col 0; len 2; (2):  c1 02
col 1; len 3; (3):  31 30 39
col 2; TERM
row#1[7944] dba: 25165850=0x180001a
col 0; len 2; (2):  c1 02
col 1; len 3; (3):  31 31 39
col 2; TERM
...

==============================================

begin
for i in 1..1000
loop
insert into t values (1, 1);
end loop ;
commit;
end ;

Branch block dump
=================
header address 116152908=0x6ec5a4c
kdxcolev 1
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 3
kdxcosdc 1
kdxconro 10
kdxcofbo 48=0x30
kdxcofeo 2902=0xb56
kdxcoavs 2854
kdxbrlmc 25165847=0x1800017
kdxbrsno 7070
kdxbrbksz 8060 
kdxbr2urrc 7
row#0[2902] dba: 25165852=0x180001c
col 0; len 2; (2):  c1 02
col 1; len 500; (500): 
 31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
col 2; len 6; (6):  01 80 00 0c 00 0b
row#1[3418] dba: 25165853=0x180001d
col 0; len 2; (2):  c1 02
col 1; len 500; (500): 
 31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
col 2; len 6; (6):  01 80 00 0d 00 08
...

문서에 대하여

  • 최초작성자 : [김종원]
  • 최초작성일 : 2010년 03월 04일
  • 이 문서는 오라클클럽 코어 오라클 데이터베이스 스터디 모임에서 작성하였습니다.
  • 이 문서의 내용은 (주)비투엔컬설팅에서 출간한 '오라클 성능 고도화 원리와 해법II'를 참고하였습니다.

문서정보

Enter labels to add to this page:
Please wait 
Looking for a label? Just start typing.
  1. 3월 21, 2010

    이승필 says:

    안녕하세요. 오라클위키 계정을 얻게 되었습니다. 좋은 정보 감사합니다. 인덱스 관련해서 궁금한점이 있습니다. 인덱스 범위검색시 인덱스는 스캔방식...

    안녕하세요.
    오라클위키 계정을 얻게 되었습니다. 좋은 정보 감사합니다.
    인덱스 관련해서 궁금한점이 있습니다.
    인덱스 범위검색시
    인덱스는 스캔방식으로 테이블은 랜덤으로 접속한다.
    인덱스의 스캔방식이라는 것이 어떤건가요?
    인덱스나 테이블이 다 데이터에 접근하는 방법은 동일한거 아닌가요?
    하나의 레코드를 읽기위해 블럭을 버퍼에 오리고, 해당 레코드를 읽고, 다음 레코드를 읽을때 래치, buerr pinning으로
    논리적/물리적 회수를 줄일수 있다.
    인덱스 스캔방식이라는것이 최초에 루프에서 리프까지 조회하고 이후 스캔을한다고 하는데..
    그럼 스캔을 할때 buffer pinning, prefech 을 사용하는것이 아니고,
    리프블럭이 이중링크드리스트로 연결이 되어있어 루트,브랜치는 조회할 필요가 없는것가요???

    스캔이라는것이 다른 데이터 조회방법인지, 아니면 buffering,prefetch등등의 오라클이 제공하는 기능을 통칭하는건가요?

    1. 3월 23, 2010

      김종원 says:

      안녕하세요... 인덱스로 범위검색을 하게 되면 해당 데이터가 등록되어 있는 최초 인덱스 리프블록이 어느 블록에 있는지를 검색하기 위해 최초 루...

      안녕하세요...
      인덱스로 범위검색을 하게 되면
      해당 데이터가 등록되어 있는 최초 인덱스 리프블록이 어느 블록에 있는지를 검색하기 위해
      최초 루트블록에서 브랜치 블록을 통해 리프 블록까지 탐색을 하게 됩니다.
      리프블록까지 가면 레코드를 처음부터 읽으면서 검색하고자 하는 값이 어느 레코드 부터 시작인지를 찾게 됩니다.
      여기까지가 수직적 탐색입니다.
      수직적 탐색이 끝나면 수평적 탐색(스캔)을 시작합니다.
      리프블록끼리는 이전, 다음 리프블록 주소를 가지고 있기 때문에
      해당 레코드부터 리프블록 레코드를 쭈욱 읽어 내려갑니다.
      그리고 해당하지 않는 데이터르 만나면 스캔을 멈추게 됩니다.

      FULL TABLE SCAN, INDEX RANGE SCAN 등
      스캔은 데이터 블록을 물리적(혹은 논리적)으로 저장된 순으로 쭈욱 읽어 가는 방식이라고 이해 하시면 될 듯합니다.