비-트리 인덱스(B-Tree Index)

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에 저장되는 데이터 키 값의 전체 개수는 약 k^d-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 옵션을 사용할 수없으며, 비트맵인덱스, 일체형인덱스에서는 사용할 수없는 단점이 있고, 실제 적용 사례는 많지 않다.