11강. 인덱싱

1. 인덱스의 개념

• 데이터 검색 시 발생하는 비효율적인 데이터 입출력 문제를 해결하기 위한 목적으로 시작
  • 인덱스 : 요청된 레코드에 빠르게 접근할 수 있도록 지원하는 데이터와 관련된 부가적인 구조
  • 인덱싱 : 인덱스를 구성하고 생성하는 작업
• 인덱스의 탐색키를 이용하여 해당 레코드가 저장된 블록의 위치를 파악하고 해당 블록을 빠르게 적재
• 탐색키( 검색키 )
  • 파일에서 레코드를 찾는데 사용되는 컬럼이나 컬럼의 집합

2. 인덱스의 종류와 평가기준

• 인덱스의 종류
  • 순서 인덱스
    • 특정 값( 탐색키 )에 대해 정렬된 순서 구조
  • 해시 인덱스
    • 버킷의 범위 안에서 값의 균일한 분포에 기초한 구조로 해시 함수가 어떤 값이 어느 버킷에 할당되는지 결정
• 인덱스의 평가기준
  • 접근 시간 : 데이터를 찾는 데 소요되는 시간
  • 유지 비용 : 새로운 데이터 삽입 및 기존 데이터 삭제 연산으로 인한 인덱스 구조 갱신 비용
  • 공간 비용 : 인덱스 구조에 의해 사용되는 부가적인 공간 비용

3. 순서 인덱스의 특징

• 탐색키로 정렬된 순차 파일에 대하여 레코드에 대한 빠른 접근이 가능하도록 구성한 인덱스
  • 탐색키를 정렬하여 해당 탐색키와 탐색키에 대한 레코드와의 연계를 통하여 인덱스 생성
  • 순서 인덱스의 종류
    • 밀집 인덱스
    • 희소 인덱스
    • 다단계 인덱스

4. 인덱스 엔트리

• 인덱스를 구성하는 가장 작은 요소, 인덱스 엔트리
• 인덱스 엔트리가 담아내야 하는 것
  • 어떤 정보를 담고 있는지?
  • 디스크 어느 위치에 저장되어 있는지?
• 인덱스 엔트리 구조
  • 인덱스 엔트리는 데이터 검색을 빠르게 하기 위해 사용되며, 다음과 같은 구조로 되어 있다.
  • 탐색키 값 : 검색 기준이 되는 키 값 ( ex. ECE24 )
  • 포인터 : 해당 레코드가 저장된 위치를 가리킴
    • 블록 ID : 해당 레코드가 어느 블록에 저장되어있는지 ( ex. b2 )
    • 오프셋 : 해당 블록의 몇 번째에 위치하는지 ( ex. 30 )

5. 밀집 인덱스( dense index )

• 모든 레코드에 대해 탐색키 값과 포인터 쌍을 유지
  • 밀집 인덱스는 데이터 파일에 존재하는 모든 레코드에 대해 탐색키 값과 해당 레코드의 위치를 가리키는 포인터 쌍을 구성
• 장점
  • 원하는 레코드를 빠르게 찾을 수 있음
• 단점
  • 모든 데이터 레코드에 대해 대응하는 인덱스가 존재하므로, 인덱스 자체의 크기가 방대해짐
  • 레코드가 많아지면 조회 시 오랜 시간 소요

6. 희소 인덱스( sparce index )

• 인덱스의 엔트리가 일부의 탐색키 값만을 유지
  • 요청된 탐색키보다 작거나 같은 인덱스의 탐색키 값 중 가장 큰 인덱스 엔트리의 포인터가 가리키는 블록을 스캔
• 장점
  • 밀집 인덱스에 비해 작은 크기 → 인덱스 메모리 적재 빠른 속도
• 단점
  • 인덱스 엔트리에 없는 레코드를 찾아야 할 경우, 블록 내에서 재검색 필요

7. 다단계 인덱스의 필요

• 4KB 크기의 한 블록에 100개의 엔트리가 삽입될 때, 100,000,000개의 레코드에 대한 밀집 인덱스
  • 1,000,000개의 블록 = 4GB의 공간 필요
• 인덱스 크기에 따른 검색 성능
  • 인덱스 크기 > 메모리 크기
    • 저장된 블록을 여러 번 나누어 읽어야 하기 때문에 디스크 I/O 비용이 증가하여 탐색 시간이 증가
  • 인덱스 크기 < 메모리 크기
    • 디스크 I/O이 줄어 탐색 시간이 축소
• 복수 계층의 인덱스를 구성

8. 다단계 인덱스의 구조

• 내부 인덱스와 외부 인덱스로 구성됨
• 외부 인덱스는 내부 인덱스보다 희소한 인덱스로 구성되며, 외부 인덱스의 각 엔트리 포인터는 내부 인덱스 블록을 가리킴
• 구조 설명
  • 외부 인덱스는 인덱스 블록 A에 저장되어 있음
  • 외부 인덱스의 각 엔트리는 내부 인덱스 블록(예: 인덱스 블록 0, 1 등)을 가리킴
  • 내부 인덱스는 각각 여러 데이터 블록(예: 데이터 블록 0, 1, ..., m+1)을 가리킴
  • 전체 구조는 상위 인덱스 → 하위 인덱스 → 실제 데이터 순서로 구성되며, 탐색 효율성을 높이기 위한 계층적 인덱스 시스템

9. B⁺-트리의 구조

• 구성
  • 루트 노드
    • 트리의 최상위 노드. 하나만 존재하며 중간 노드를 가리킨다.
  • 중간 노드
    • 루트 노드 또는 다른 중간 노드로부터 연결되어 있으며, 하위 노드( 중간 또는 단말 노드 )를 가리킨다.
  • 단말 노드( 리프 노드 )
    • 실제 데이터를 가리키는 포인터를 가지고 있는 노드.
    • 단말 노드들끼리는 오른쪽 방향으로 연결되어 있어 순차 접근이 가능하다.
• 루트 노드부터 모든 단말 노드에 이르는 경로의 길이가 같은 높이 균형 트리 구조
  • 순서 인덱스는 파일이 커질수록 데이터 탐색 비용이 커지는 문제를 해결하기 위해 제안
  • 상용 DBMS에서도 널리 사용되는 대표적인 순서 인덱스 구조
• B⁺-트리의 노드 구조
  • P₁ K₁ P₂ ... Pₙ₋₁ Kₙ₋₁ Pₙ
    • 각 노드에는 키(K)와 포인터(P)가 번갈아 저장되며, P는 하위 노드나 데이터 블록을 가리킨다.
  • 팬아웃( fanout )
    • 하나의 노드가 가질 수 있는 자식 노드의 최대 개수를 의미
    • 이는 트리의 높이와 탐색 효율에 영향
      • 팬아웃 값이 적으면 트리 높이가 커지기에, 팬아웃 값을 크게 구성해야 함

10. B⁺-트리의 구성 요소

• 인덱스 세트
  • 루트노드와 중간노드로 구성
  • 단말노드에 있는 탐색키 값을 신속하게 찾아갈 수 있도록 경로를 제공하는 목적으로 사용
    • 트리의 상위에 있는 루트노드와 중간노드는 탐색 경로를 제공하기 위해 존재하며, 직접 데이터를 저장하지 않음
  • [n/2] ~ n 사이의 개수를 자식으로 소유
  • 어느 범위에 가면 원하는 포인터를 찾을 수 있는지 힌트 제공
• 순차 세트
  • 단말노드로 구성
    • 단말노드( leaf node )들은 좌우로 연결되어 있으며,
    • 이는 순차 탐색 시 왼쪽 → 오른쪽 노트로 신속한 접근을 가능하게 함
  • 모든 노드가 순차적으로 서로 연결
  • 적어도 [(n-1)/2]개의 탐색키를 포함
  • 탐색키에 대한 실제 레코드를 지정하는 포인터를 제공

11. B⁺-트리 상에서의 삽입, 삭제

• 레코드 삽입, 삭제 시 B⁺-트리 수정
  • 레코드 삽입
    • 노드에서 유지해야 할 탐색키와 포인터 수 증가로 인해 노드를 분할해야 하는 상황이 발생
  • 레코드 삭제
    • 노드에서 유지해야 할 탐색키 값과 포인터 수 감소로 형제 노드와 키를 재분배 또는 병합해야 하는 상황이 발생
  • 높이 균형 유지
    • 노드가 분할되거나 병합되면서 높이의 균형이 맞지 않는 상황이 발생
• 삽입 : 검색과 같은 방법을 사용하여 삽입되는 레코드의 탐색키 값이 속할 단말 노드를 탐색
  • 해당 단말 노드에 <탐색키, 포인터> 쌍을 삽입
  • 삽입 시 탐색키가 순서를 유지
• 삭제 : 삭제될 레코드의 탐색키를 통해 삭제될 탐색키와 포인터를 포함한 단말 노드를 탐색
  • 같은 탐색키 값을 가지는 다중 엔트리가 존재할 경우, 삭제될 레코드를 가리키는 엔트리를 찾을 때까지 탐색 후 단말노드에서 제거
  • 단말노드에서 제거된 엔트리의 오른쪽에 있는 엔트리들은 빈 공간이 없도록 왼쪽으로 이동

12. 노드가 분할되는 삽입

• 부모 노드에 탐색키를 조정하고 추가된 노드에 대한 포인터를 삽입

13. 탐색키가 재분배되는 삭제

• 예시
  • 'COM12' 삭제
    • 'COM12'가 있는 단말 노드를 검색하고 탐색키를 삭제
      • 해당 단말 노드는 삭제 후 탐색키가 존재하지 않음
      • [(n - 1)/2]개보다 탐색키가 적으므로 다른 노드와 별도의 재구조화 작업이 필요
    • 'COM12'가 저장된 노드의 오른쪽의 형제 노드와 키를 재분배