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

2.1. B-tree 인덱스




2.1 B-Tree인덱스

  • 관계형 데이터베이스에서 가장 일반적으로 사용되는 인덱스

2.1.1 B-Tree인덱스의 구조

  • 나무구조(Tree)처럼 가지에 해당하는 브랜치 블럭과 잎사귀에 해당하는 리프 블럭이 있다.
  • Unique Scan일 경우
  • range Scan일 경우
    • 인덱스는 구성컬럼과 ROWID로 정렬되어 있다. ROWID에는 로우가 저장된 블록의 주소, 로우의 슬롯번호가 기록되어 있다.
    • 처리할 범위의 첫번째 인덱스로우를 브랜체블록을 통해 리프블록을 액세스한 다음 거기의 ROWID로 블록을 찾는다.
      SGA부터 찾아보고 없으면 디스크에 액세스해서 복사본을 SGA에 복사한다
    • 새롭게 액세스한 데이터블록정보를 PGA로 가져와서 해당 SQL의 처리버퍼에 넣는다 (일명 원 버퍼)
    • 인덱스블록을 액세스한 내용을 PGA버퍼에서 찾아 다른 조건까지 검증하여 성공한 로우만 운반단위로 보낸다 만약 클러스터링 팩터가 좋다면 여러건의 인덱스 스캔을 하나의 버퍼에서 처리할 수 있다.
    • PGA버퍼에서 찾을 수 없다면 다시 다른 블록을 SGA에 액세스하여 새로운 블럭을 담고 위의 처리를 반복수행한다.
    • 리프블록에서 액세스한 로우가 처리범위를 넘으면 처리를 종료한다.
  • ROWID의 구성
    • rowid라는 가상 컬럼에 저장된다.
    • Single row accescc를 위한 row 고유한 주소
    • 10자리로 구성

2.1.2 B-Tree 인덱스의 조작(Operation)

  1. 인덱스 생성(Creation)
  • 테이블을 액새스하여 정렬을 수행
  • 정렬된 결과를 인덱스 세그먼트의 리프 블록에 기록하기 시작
  • 리프블록이 PCTFREE에 도달하여 새로운 블록을 요구하게 되면 브랜치블록을 생성
  • 리프블록이 증가함에 따라 브랜치블록도 채워져 가다 블랜치블록이 PCTFREE에 도달하면 새로운 리프블록과 새로운 브랜치블록을 생성할때 루트블록이 생성된다
  • 새로운 브랜치블록이 만들어질 때마다 루트블록에 브랜치블록의 DBA정보를 기록한다.
  • 위와 같은 방법으로 인덱스가 저장되기 때문에 인덱스 블럭에 많은 로우를 담게 될 경우 리프 블럭 감소, 브랜치 블럭 증가 둔화(블럭의 깊이 감소)
    • 최대한 인덱스 컬럼의 수를 줄인다
    • 큰 블럭 사이즈(DB_BLOCK_SIZE)를 지정
    • PCTFREE를 최소로 정의
    • 압축을 활용하는 방법
        CREATE INDEX ord_customer_idx
        ON orders (customer_id, sales_id)
        COMPRESS 1;
      
  1. 인덱스 블럭의 분할(SPILT)
  • 인덱스 로우는 정렬이 되어 저장 되어야 하는 이유 때문에 이미 생성된 구조에 새로운 로우가 삽입되면 기존의 위치에 파고 들어가는 문제 발생
  • 마지막 값이 삽입되는 경우 : 그림처럼 PCTFREE에 도달한 블럭일 경우엔 새로운 블럭에 등록된다.
  • 중간 값이 삽입되는 경우 : PCTFREE가 초과하게 되므로 분할이 발생하는데 어차피 2개의 블럭으로 수정되므로 2/3만 채우도록 하면서 양쪽을 모두 재편하게 됨(또 다른 중간 값이 들어와 계속 분할 되는 것을 방지하기 위함)
  • 하지만 분할이 일어난 블럭에 새로운 값이 들어오지 않으면 저장공간 낭비를 초래하게 되고 이를 해결하기 위해선 인덱스를 재생성하는 방법뿐이다.
  1. 데이터의 삭제 및 갱신
  • 데이터를 삭제했을 경우 테이블의 로우는 제거되지만 인덱스의 로우는 삭제되었다는 표시(flag)만 추가된다.(저장공간낭비와 스캔시 액세스 블럭 증가)
  • 한 리프 블럭이 모두 삭제 되었을 경우 브랜치 블럭에 해당 리프 블럭을 가리키는 로우도 삭제 표시가 된다.
  • 갱신할 경우 삭제와 삽입이 발생.
  • 이러한 이유로 수정이 빈번하지 않는 컬럼을 인덱스로 사용권장
  • 데이터처리(DML)가 많이 수행되는 테이블은 정기적으로 재생성을할 필요가 있다.
  1. 인덱스를 경유한 검색
  • lmc는 브랜치 블럭의 첫 번째 로우의 값보다 적은 값을 갖는 하위의 블럭의 주소정보(dba:data block address)를 말한다.
    1. 루트 블록을 찾는다.
    2. 주어진 값보다 같거나 최소값을 찾는다.(찾는값 >= 인덱스값)
      -. 찾는 값 < 인덱스 값 (Lmc에 있는 dba로 이동)
      -. 찾는 값 = 인덱스 값 (해당 dba로 이동)
      -. 찾는 값 > 인덱스 값 (검색 후 찾는 값 = 인데스 값이면 해당 dba로 이동 그렇지 않으면, 찾는 값 < 인데스 값을 만족하는 인덱스 최소값)
    3. 리프 블록을 찾을 때까지 ② 의 단계를 반복해서 수행
    4. 리프 블록에서 주어진 값을 가진 키를 찾아 존재하면 ROWID를 이용해 테이블을 액세스하고, 그렇지 않으면 'No Data found'로 결과 반환 만약, col2의 조건을 'ACC'가 아닌 'AC%'로 바꾸면
    5. Col1 = 'B'이면서 Col2 = 'AC'보다 같거나 큰 것에서 스캔을 시작, 'AD' 보다 작으면 테이블을 액세스하고, 그렇지 않으면 종료한다.

2.1.3 리버스 키 인덱스

  • 어떤 컬럼값의 각 바이트의 위치를 역전시키는 것을 말한다.
  • 리버스키 인덱스에서는 정렬이 크게 달라지므로 클러스터링 팩터가 나빠진다는 것을 의미한다.
  • '='로만 액세스하는 경우에라면 크게 문제되것이 없다

문서에 대하여

  • 이 문서는 오라클클럽 [대용량 데이터베이스 스터디] 모임에서 작성하였습니다.
  • 이 문서의 내용은 이화식님의 새로쓴 대용량 데이터베이스 솔루션을 참고했습니다.
  • 이 문서를 다른 블로그나 홈페이지에 게재할 경우에는 출처를 꼭 밝혀 주시면 고맙겠습니다.~^^

문서정보

Enter labels to add to this page:
Please wait 
Looking for a label? Just start typing.