2.1 B-tree 인덱스 * B-tree 인덱스에 대한 개괄
- 데이터베이스에서 가장 많이 쓰이는 인덱스이다. - 오라클의 경우 CREATE INDEX 명령어를 사용하여
생성된다. - B-tree의 B는 Balanced의 약자로 트리의 맆노드의 깊이가 같다는 균형을 의미한다. -
검색시 걸리는 시간은 모든 데이터가 트리의 깊이 만큼 시간이 걸린다. [참고] CREATE INDEX 문에 의하여
생성되는 인덱스
- Default - B-tree 인덱스
- 비트맵 인덱스
- Partitioned 인덱스
- 함수-기반 인덱스
- 도메인 인덱스
* B-tree의 성능
- B-tree의 검색 속도는 트리의
깊이 d에 의하여 좌우된다.
- 트리의 깊이 d는 데이터가 많아지면 깊어지지만 값이 크지 않아 큰 영향을 주지 않는다.
-
트리의 깊이 d를 줄이려면 브랜치블록 노드에 저장하는 key 값의 수 k를 늘린다.
- 키의값개수 k를 결정은
블록노드의 크기에 관계있으나 블록노드의 크기는 시스템의 디스크 블록의 크기와 관계가 있다.
(즉 무한정 많이 저장할수는 없다)
- 깊이가 d인 B-tree에 저장되는 데이터 키 값의 전체
개수는 약 kd-1이다.
- 예를 들어 브랜치블록이 200개이고
깊이가 3인 B-tree에 저장할 수 있는 키값은 800만개이다.
(무척 많이 저장할
수 있다. 실제 오라클에서 어느 정도 저장하는지?)
- 오라클의 경우 B-tree인덱스는 CREATE INDEX 명령어를
사용하여 생성된다.
- B-tree의 B는 Balanced의 약자로 트리의 맆노드의 깊이가 같다는 균형을 의미한다.
-
검색시 걸리는 시간은 모든 데이터가 트리의 깊이만큼 시간이 걸린다.
2.1.1 B-tree 인덱스의 구조
- B-tree는 루트(root)블록, 브랜치(branch)블록, 리프(leaf)블록으로 구성된다.
- 인덱스 부분은 루트블록과 브랜치블록으로 같은 구조이다.
-
브랜치블록(이하 루트블록 포함)은 k개 이하의 키값을 저장한다.
- 브랜치블록은
k+1개의 자식 노드를 갖는다.
- 유일스캔 데이터검색은 루트노드부터 시작하여 검색키값과
브랜치블록 노드에 저장된 킷값을 비교하여 분기를하여 리프블록을 찾을 때까지 계속 내려간다.
- 범위검색은 먼저 시작하는 값을 유일스캔하여 해당 리프블록을 찾은 다음 리프블록만을 따라가며 검색한다.
* 튜플의 ROWID 길이 : 실험결과 책과달리 18자리임?, 예) AAAM3lAABAAAPCiAAA
<!--StartFragment-->
2.1.2
B-tree 인덱스의 조작
- B-tree 인덱스의 가장 큰 당면
문제는 데이터 삽입, 삭제 관리이다.
가) 인덱스 생성
- 비어있는 테이블에서 인덱스 생성은 간단히 루트블록만 생성하면된다.
- 그러나 사용중인 테이블에서의 인덱스를 생성할 경우?
[그림
1-2-4 참조]
(알고리즘)
1.
데이터를 모두 정렬한다
2. 데이터를 리프블록에 순서대로 저장을 시작한다.
3. 리프블록이 2개 이상으로 늘어나기 시작하면 브랜치블록을 생성한다.
- 브랜치블록에 저장되는 킷값의 개수는 DB_BLOCK_SIZE가 클수록 PCTFREE 값이 작을수록
유리하며, 키값의 길이가 짧은 것이 유리하다.
- 키값의 길이를 줄이는 방법은 키값을
압축하는 방법이다.
SQL문의 예) CREATE INDEX
ord_customer_idx
ON
orders(customer_id, sales_id) COMPRESS 1;
나)
인덱스블록의 분할(데이터 삽입)
- 데이터의 삽입이 될 때 인덱스블록의 분할이 발생한다.
- 데이터가 삽입될때
case 1 : 데이터블록이 여유가
있다(PCTFREE 값보다 작다)
=> 바로 저장(문제없음)
case 2 : 데이터블록이 여유가 없다.
case
21 : 데이터가 마지막 값이면[그림 1-2-5의 아래부분]
=> 새로운 블록을 생성하여 여기에 삽입된 데이터를 저장하고 상위 브랜치블록에 이 값을 전달
case 22 : 데이터가 중간 값이면[그림 1-2-5의 위부분]
=> 블록을 2개로 균등 분할(새로들어간 데이터를 포함하여)하여 브랜치블록에
중간 키 값을 전달
* case 21, 22에서 분할된 키값을 상위
브랜치블록에 전달했을 경우 만약 브랜치블록 또한
PCTFREE
값을 초과했을 경우에는 브랜치블록을 다시 분할하며 상위 브랜치블록에 다시 전달하며
이
과정이 루트블록에 도달항 때까지까지 진행된다.
- 데이터의 삽입과 삭제가
빈번하다보면 저장공간의 활용의 효율성이 떨어질 수 있다
이 경우는 인덱스를
재생성(rebuild) 한다.
SQL 사용예) ALTER INDEX
emp_index REBUILD ONLINE;
다) 데이터의 삭제및 갱신
- 데이터를 삭제할 경우는 삭제된 데이터의 위치에 삭제를 표시하는 flag로 해결한다.
- 데이터블록에 저장된 데이터가 모두 삭제될 경우는 상위 브랜치블록의 해당로우에 삭제 표시를 한다.
- 데이터의 삽입과 삭제가 빈번한 테이블은 정기적으로 인덱스를 재생성한다.
라) 인덱스를 경유한 검색
- B-tree 인덱스를 이용한 검색은 루트블록에서 시작한다.
-
[그림 1-2-6의 예] col1+col2의 복합인덱스에서 col1=B and col2=ACC를 검색
1. 루트블록을 검색한다. col1=B와 같거나 큰 브랜치블록 21를 찾았다.
2. 21번 브랜치블록에서 col2=ACC에 해당하는 20번 데이터블록을 찾았다.
3. 20번 데이터블록에서 Rowid 값을 찾는다.
-
범위 검색일 경우는 위 과정에서 찾은 Rowid를 이용하여 데이터블록을 검색한다.
2.1.3 리버스 키 인덱스
-
데이터가 비슷한 킷값을 가지고 지속적으로 발생하는 경우 B-tree 인덱스에서 비슷한 영역에 계속 저장되게 된다.
이렇게 되면 인덱스 구조가 비효율적일 수 있다.
- 이
문제를 해결하려면 키값을 역전(reverse) 시킨 다음에 인덱스에 저장하는 방법이 리버스키인덱스 방법이다.
- 동등(=) 검색이 아닌 LIKE, BETWEEN을 사용해야하는 경우는 불가능하다.
- 데이터 검색시 같은 브랜치블록에 접근이 몰리는 것을 피할 수 있다.
- 인덱스를 생성할 때 NOSORT 옵션을 사용할 수없으며, 비트맵인덱스, 일체형인덱스에서는 사용할 수없는
단점이 있고, 실제 적용 사례는 많지 않다.
