매주 각 스터디 팀원들이 담당 분량을 정리해서 올리고 토론식으로 진행합니다.
스터디 포스팅은 팀원들에의해 이루어지지만 스터디 참여는 사이트 회원 모두가 가능합니다.
진행기간: 2009.07 ~ 2009.10. 종료
2.1. B-tree 인덱스
2009.07.10 14:58
<!--StartFragment-->
2.1 B-tree 인덱스
* B-tree 인덱스에 대한 개괄
- 데이터베이스에서 가장 많이 쓰이는 인덱스이다.
- 오라클의 경우 CREATE INDEX 명령어를 사용하여 생성된다.
- B-tree의 B는 Balanced의 약자로 트리의 맆노드의 깊이가 같다는 균형을 의미한다.
- 검색시 걸리는 시간은 모든 데이터가 트리의 깊이 만큼 시간이 걸린다.
[참고] CREATE INDEX 문에 의하여 생성되는 인덱스
* B-tree의 성능
- B-tree의 검색 속도는 트리의 깊이 d에 의하여 좌우된다.
- 트리의 깊이 d는 데이터가 많아지면 깊어지지만 값이 크지 않아 큰 영향을 주지 않는다.
- 트리의 깊이 d를 줄이려면 브랜치블록 노드에 저장하는 key 값의 수 k를 늘린다.
- 키의값개수 k를 결정은 블록노드의 크기에 관계있으나 블록노드의 크기는 시스템의 디스크 블록의 크기와 관계가 있다.
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이다.
- 깊이가 d인 B-tree에 저장되는 데이터 키 값의 전체 개수는 약 kd-1이다.
- 예를 들어 브랜치블록이 200개이고 깊이가 3인 B-tree에 저장할 수 있는 키값은 800만개이다.
(무척 많이 저장할 수 있다. 실제 오라클에서 어느 정도 저장하는지?)
- 오라클의 경우 B-tree인덱스는 CREATE INDEX 명령어를 사용하여 생성된다.
- B-tree의 B는 Balanced의 약자로 트리의 맆노드의 깊이가 같다는 균형을 의미한다.
- 검색시 걸리는 시간은 모든 데이터가 트리의 깊이만큼 시간이 걸린다.
- 오라클의 경우 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 옵션을 사용할 수없으며, 비트맵인덱스, 일체형인덱스에서는 사용할 수없는 단점이 있고, 실제 적용 사례는 많지 않다.
제가 내일부터 25일 오전까지 개인적인 일이 있어서 인터넷 접근이 어렵습니다.
(양해부탁 드릴께요...)
25일 오프라인 미팅은 참석 하도록 하겠습니다.