7.8 접근방법 설계

7.8.1 스캔방식

• 1.테이블에 존재하는 데이타의 20%이상을 검색해야 하는 경우 테이블 스캔방식으로 데이타를 가져오는 것이 인덱스를 경유하는 것보다 더 효율적이다.
• 2.테이블 전체를 스캔하는 것을 풀스캔이라고 하고 정렬된 테이블에서 특정 부분만을 스캔하는 것을 범위스캔이라고 한다.
• 3.테이블 스캔의 경우 대부분 풀스캔이 발생하지만 DBMS의 종류에 따라 범위스캔을 지원하기도 한다. (?)

7.8.2 B트리 인덱스

B트리 인덱스의 기본구조

1.비트리 인덱스에는 루트,브랜치,리프블록이 존재한다.

1)리프블록

• 테이블의 인덱스에 대한 실질적인 정보가 담겨있는 블록이다.
• 테이블에서 입력,수정,삭제,조회가 발생하면 관련 인덱스가 리프블록내에서 입력,수정,삭제,조회를 발생시킨다.
• 블럭헤더:인덱스 칼럼의 구간값과 인덱스바의 물리적 위치 정보를 가지고 있다.
  -> (?) 320페이지 그림 7-58에 블럭헤더가 표시되어 있는가?
  -> (?) 칼럼의 구간값이란? : 만일 위 그림이 <부서> 테이블의 부서코드에 대한 인덱스이고 맨 왼쪽의 리프블럭에 10,20,30 부서코드 인덱스가 저장되어 있다면 10~30 값이 저장되어 있다는 의미?
  -> (?) 인덱스바의 물리적 위치정보:위 그림처럼 만일 맨 왼쪽블록에 3개의 인덱스바가 저장되어 있다면 블록헤더에 3개 각각에 대한 물리적(하드디스크) 위치 정보가 있다
• 인덱스바는 인덱스헤더,로우칼럼값,ROWID로 구성되어 있다.
  ->인덱스헤더:각 인덱스를 구분하는 값
  ->로우의 칼럼값:인덱스 대상이 되는 칼럼 값
  ->ROWID: 레코드의 물리적 저장위치

2)브랜치블록

• 리프블록과 루트블록의 중간에서 블록사이의 정보에 대한 다리 역할을 하는 블록이다.
• 블록헤더 : 인덱스 칼럼의 구간값과 인덱스바의 물리적 위치정보가 있다
  -> (?) 인덱스칼럼의 구간값 : 맨 왼쪽의 브랜치블록에는 맨 왼쪽 3개의 리프블록이 연결되어 있는 바, 10-90의 값이 저장됨
• 인덱스바 : 인덱스헤더,브랜치블록ID,브랜치블록 키값으로 구성되어 있다.
  ->인덱스 헤더:각 인덱스를 구분하는 값이다.
  ->브랜치블록ID:자신에게 연결된 하위 블록의 물리적 위치가 저장되어 있다.
  ->브랜치블록 키값:자신에게 연결된 하위 블록의 인덱스 칼럼의 구간값이 있다.

3)루트블록

• 트리의 최상위에 위치하며 조회,입력,수정,삭제시 제일 먼저 접근된다.
• 인덱스바는 자신에게 연결된 하위 블럭의 수를 의미한다 (3개면 3개 블록 연결,2개면 2개 블록 연결)
• 하나의 인덱스바는 인덱스헤더,브랜치블록ID,브랜치블록 키값으로 구성되어 있다.
  ->인덱스헤더:하나의 블록에는 보통 수백개의 인덱스바가 존재하는 바, 각 인덱스바를 구분하는 헤더값이 들어있다.
  ->브랜치블록ID:자신에게 연결된 하위블록의 물리적 위치가 담겨있다.
  ->브랜치블록 키값:자신에게 연결된 하위블록의 인덱스칼럼의 구간값이 들어있다.

B트리 인덱스의 검색원리

1.위 그림이 <부서> 테이블의 부서코드에 대한 인덱스라고 가정하고 아래 쿼리문이 실행되는 절차를 살펴보자.

SELECT 부서코드,부서명
FROM 부서
WHERE 부서코드='200'

• 먼저 루트블록에서 부서코드 200이 속한 인덱스바가 무엇인지 찾는다. 세번째 인덱스바는 190~240의 값을 가지고 있기에 바로 이것임을 알 수 있으며 인덱바의 브랜치블록ID에 하위블록의 물리적 위치가 있으므로 이 위치를 근거로 브랜치 블록을 탐색한다.
• 하위 브랜치블록에는 두개의 인덱스바가 있는데 부서코드 200은 첫번째 인덱스바에 속함을 알 수 있다. 역시 이 인덱스바의 브랜치블록ID를 통해 리프블록의 물리적 위치를 알아내어 이를 근거로 리프블록을 탐색한다.
• 오른쪽에서 두번째 리프블록이 해당 리프블록인데 여기에 있는 세개의 인덱스바중 2번째가 바로 찾고자하는 인덱스이며 따라서 이 인덱스바에 있는 ROWID로 테이블에 엑세스하여 최종 탐색을 끝마친다.

B트리 인덱스의 입력,수정,삭제

1.입력 (각 블록은 최대 3개의 인덱스바를 갖는다고 가정한다)

• 1)위 그림과 같은 인덱스 구조에서 부서코드 235 추가된다고 가정하자.
• 2)새로 추가되는 인덱스는 자신이 저장될 수 있는 구간값을 가지는 리프블록을 찾는다. 여기서는 맨 왼쪽의 리프블록이 해당된다.
• 3)그런데 해당 리프블록은 이미 3개의 인덱스바를 가지고 있어 더 이상 추가될 수 없으므로 이 사실을 상위 브랜치블록에 통보한다.
• 4)브랜치블록은 인덱스바가 2개이므로 인덱스바를 하나 더 추가하고 인덱스바가 추가된 만큼 리프블록을 하나 더 만든다.
• 5)그리고 추가된 값을 포함하여 해당 인덱스 구간값을 가지는 리프블록의 인덱스바 수를 반으로 나누고 그 반을 새로은 리프블록으로 이동시켜 입력작업을 완료한다.
• 6)예로 든 것은 간단히 브랜치블록에 인덱스바가 추가되고 새로운 리프블록이 생성되는 것으로 해결되었지만 때로는 루트블록이 분할되어 브랜치블록으로 변경되고 새로운 루트블록이 생성되기도 한다. 이런 경우 인덱스의 깊이는 한단계 더 깊어지게 될 것이다.
• 7)현실적으로 하나의 블록에는 수백개의 인덱스바가 저장된다. 만일 100개씩만 저장된다 하더라도 3단깊이이면 100*100*100=1,000,000으로 백만개의 인덱스 관리가 가능하다.
• 8)그러므로 인덱스의 깊이가 4레벨 이상이거나 혹은 잦은 입력,수정,삭제로 인해 이빨빠짐 현상이 발생하는 경우 인덱스 리빌드를 통해 인덱스 선능을 보존해야 한다.

7.8.3 비트맵 인덱스

비트맵 인덱스 구조

• 1.컴퓨터에서 사용하는 최소 단위인 비트를 이용하여 칼럼값을 저장하고 이용하며 ROWID를 자동으로 생성하는 인덱스 기법이다.
• 2.비트로 관리하므로 저장공간이 크게 감소하고 비트별로 각종 연산을 수행함으로써 기존 인덱스가 해결할 수 없었던 많은 문제를 해결하였다.
• 3.대용량처리,복잡한 AND,OR 연산에 강력한 힘을 발휘한다.
• 4.그러나 아직 여러가지 제한이 있어 모든 분야에는 적용되지 못하고 있으며 주로 데이타웨어하우스에서 활용되고 있다.
• 5.비트맵도 비트리인덱스처럼 루트,브랜치,리프블록으로 구성되지만 리프블록에 칼럼값과 ROWID 대신 0과 1로 구성된 비트맵이 저장된다는 점이 다르다.
• 6.NULL값도 인덱스로 저장할 수 있다.

특정 테이블의 성별 컬럼에 비트맵 인덱스를 생성했다고 가정하자. 
성별 컬럼에는 '남성' 아니면 '여성'이라는 값이 저장된다는 것은 누구나 아는 사실이다. 
예를 들어, 테이블에 4개의 데이터가 저장되어 있으며 저장된 데이터의 순서는'여성', '남성', '남성', '여성'이다. 
성별 컬럼에 비트맵 인덱스를 생성하게 되면 비트맵 인덱스의 리프 블록에는 두개의 비트맵이 생성된다. 
생성되는 두개의 비트맵이 바로 '남성' 비트맵과 '여성' 비트맵이다. 
테이블에 데이터가 '여성', '남성', '남성', '여성' 순으로 저장되어 있기 때문에 
'남성' 비트맵에는 '0110'이라는 비트맵으로, 
'여성' 비트맵은 반대의 '1001'의 비트맵을 구성하게 된다. 
그럼 '남성' 비트맵에서 '0110'은 무엇을 의미할까? 
저장된 데이터의 순서에 의해 '1'이면 '남성'을, '0'이면 '남성'이 아님을 말한다. 
따라서, 비트맵 인덱스의 남성 비트맵이 '0110'이면 해당 테이블의 성별 컬럼의 두 번째 데이터와 세 번째 데이터는 
'남성'이라는 값이 저장된다. 
또한, 성별 컬럼의 첫 번째 데이터와 네 번째 데이터는 '남성'이 아닌 데이터라는 것을 표시한다. 
'여성' 비트맵의 경우는 '1001'이므로 첫 번째와 네 번째 데이터는 '여성' 데이터가 저장되며 
두 번째와 세 번째의 데이터는 '여성'이 아닌 데이터라는 것을 의미한다. 
결국, '남성' 비트맵과 '여성' 비트맵을 모두 합치면 해당 테이블에는 
'여성', '남성', '남성', '여성' 순으로 데이터가 저장되는 셈이다.

(?) 테이블의 총 로우수가 4개여서 비트자리수가 4자리인가? 그렇다면 만일 로우수가 100개라면 비트자리수는 100자리가 되는 것인가?

비트맵 인덱스 검색원리

• 1.<부품> 테이블의 SIZE칼럼에는 SAMLL,MED,LARGE 세개의 값이 있고,COLOR 칼럼에는 BLUE,RED,GREEN 세개의 값만이 나타난다고 가정하자.
• 2.이 두개의 칼럼에 대해 비트맵인덱스를 만든다면 하단처럼 나타날 것이다.
• 3.만일 상단왼쪽 쿼리문을 실행한다면 다음과 같은 플랜이 나타날 것이다.

Execution Plan
-------------------------------------------------------
SELECT STATEMENT
  SORT (AGREGATE)
    TABLE ACCESS (BY INDEX ROWID) OF 'PARTS'
      BITMAP CONVERSION (TO ROWIDS)
        BITMAP AND
          BITMAP INDEX (SINGLE VALUE) OF 'COLOR_BIX'
          BITMAP INDEX (SINGLE VALUE) OF 'SIZE_BIX'

• 'COLOR_BIX'와 'SIZE_BIX' 인덱스를 엑세스하여 AND 연산을 하여 조건을 만족하는 로우만 추출한다. 이 예제에서는 010010이 취할 예제이다
  -> color=red 인덱스의 비트맵 : 011010
  -> size=med 인덱스 비트맵 : 110010
  -> and 연산

011010
110010

• 그 결과를 BITMAP CONVERSION 를 통해 ROWID를 추출하여 PARTS 테이블에 엑세스한다.

<위 그림처럼 흰색의 비트맵 인덱스에서 ROWID를 계산하여 실제 테이블에 엑세스 하는 과정>

• ROWID 계산법=시작ROWID+상대거리
• 시작로우ID(5.2.11) : FILE11의 5번째 블럭에서 시작한다는 의미이다. (?) 2의 의미는?
• 종료로우ID(15.3.11) : FILE11의 15번째 블럭에서 종료한다는 의미이다. (?) 3의 의미는?
• 위 그림에서 보면 0이 아닌 1의 값을 가진 경우가 바로 흰색이라는 의미이며 1,4,7번째가 해당된다.
• 첫번째 1의 경우 무조건 시작블럭이 5블럭의 첫번째 로우를 읽으면 된다.
• 두번째 4의 경우 첫블록의 로우수가 3이므로 다음 블록의 첫번째 로우를 읽으면 된다.
• 세변째 7의 경우 첫번째 블럭의 로우수 3에 현재블록인 블럭6의 로우수 4를 합하면 7로써 자신의 순번인 7에 해당되므로 6블럭 4번째 로우를 읽으면 된다.
• 주의: 블록의 수는 데이타사전에서 관리하므로 해당 로우가 나올 때까지 이전 블록의 모든 로우를 읽을 필요는 없다

• SELECT된 결과를 SUM()하여 최종 결과를 추출한다

비트맵 인덱스 입력,수정,삭제

• 1.비트맵 인덱스의 입력,수정,삭제는 비트리 인덱스에 비해 상대적으로 처리속도가 매우 느리다.
• 2.총 20만건의 레코드가 있는 테이블에서 물리적인 위치가 10만번 째가 되는 새로운 인덱스를 삽입한다고 하자. 먼저 추가할 인덱스를 삽입하고 100,001부터 이후 모든 인덱스 값을 한 칸씩 뒤로 미루는 작업을 해 주어야 한다.
• 3.한건이 추가된다는 것은 인덱스 전체구조를 바꾼다는 것과 같다. 따라서 입력,수정,삭제가 빈번한 테이블에 대해서는 비트맵 인덱스가 적절하지 않다.

7.8.5 해싱기법

1.해시 인덱스의 특징

• 1)6블록 이상의 물리적인 블록의 크기를 갖는 테이블에 적용한다.
• 2)정렬순서에 따른 접근방식이 아닌 임의접근방식이 많이 발생하는 경우에 적합하다.
• 3)자주 변경되지 않는 칼럼값에 해시키를 적용한다.
• 4)클러스터키를 사용하는 비슷한 검색조건으로 부터 해시클러스터 인덱스는 인덱스 클러스터보다 빠른 성능을 제공한다.
• 5)하나의 테이블에는 하나의 해시키만 가지 수 있으므로 가장 많이 조회하거나 중요한 칼럼에 해시키를 지정한다.
• 6)해시 알고리즘은 범위검색에는 적용되지 않는다 ex) ORDDATE > '20081010'
• 7)정렬되어 있는 테이블를 조회할 때는 해시 알고리즘이 적용되지 않는다.
• 8)여러개의 칼럼을 하나의 해시키로 구성하였을 때 일부에 대해서만 비교한다면 해시 알고리즘은 이용되지 않는다.

7.8.6 클러스터링

1.동일한 성격의 데이타를 동일한 블럭에 저장하여 검색의 속도를 높이는 기법이다.

2.보통 인덱스의 경우 칼럼값이 NULL이면 인덱스에 저장이 안되나 클러스터 인덱스는 NULL키를 저장한다.

3.클러스터링의 특징

• 1)6블록 이상의 테이블에 적용한다.
• 2)칼럼 값의 분포도가 좋지 않을 수록,즉 동일한 값이 많을 수록 유리하다.
• 3)일정한 순서로 조회되는 경우 적용한다.
• 4)입력,수정,삭제가 자주 발생되지 않은 칼럼에 적용한다.
• 5)클러스터링을 생성한 기준값은 수정되지 않아야 한다.
• 6)테이블이 분할되어 있지만 거의 동시에 조인하여 조회하는 경우 적용한다.
• 7)일반 테이블보다 저장 공간을 많이 차지하므로 전체스킨을 할 경우 검색속도가 느리다.

4.클러스터링이 적용안되는 경우

• 1)테이블에 전체스캔이 종종 발생한다면 클러스터링을 적용하지 않는다
• 2)파티셔닝을 적용하면 클러스터링 기능을 사용할 수 없다. (?)
• 3)동일한 클러스터 키를 가진 클러스터링된 데이타의 크기가 하나의 블럭을 초과하는 경우 클러스터링을 적용하지 않는다.