[DB]인덱싱

📚인덱싱의 이해

• 인덱스의 개념
  인덱싱은 데이터 검색에서 발생하는 비효율적인 데이터 입출력 문제를 해결하기 위한 목적으로 제안되었습니다.
  인덱스는 책들의 마지막 부분에 있는 색인과 같습니다. 색인은 책의 내용 중 중요한 내용이나 단어 등을 뽑아 본문 몇 페이지에 있는지 쉽게 찾아볼 수 있도록 한 페이지입니다.
  DBMS의 인덱스도 이와 같은 역할을 합니다. 인덱스는 탐색키를 이용하여 해당 레코드가 저장된 블럭을 디스크 저장장치 또는 메모리에서 파악하여 해당 블럭을 빠르게 적재시키기 위한 보조적인 도구입니다.

💡탐색키: 파일에서 레코드를 찾는데 사용되는 컬럼이나 컬럼의 집합

• 인덱스: DBMS에서 요청된 레코드에 빠르게 접근할 수 있도록 데이터와 관련된 부가적인 구조입니다.
• 인덱싱: 인덱스를 구성하고 생성하는 작업입니다.

• 인덱스 기반의 검색 과정
  DBMS는 실제 레코드를 메모리에 올리는 것이 아니라 인덱스 블럭들을 메모리에 올려서 레코드가 디스크 또는 메인 메모리의 어느 블럭에 저장되어 있는지 파악하고 해당 블럭을 읽어 들여 레코드에 접근합니다.

데이터베이스에서 인덱스의 용도로 모든 레코드의 정보를 정렬하여 리스트로 관리하는 경우 인덱스 크기가 비대해지기 때문에 인덱스 탐색 비용이 늘어나게 됩니다. 따라서 효율성을 향상시킨 여러 종류의 인덱스 구조를 사용해야 하는데 인덱스의 종류는 아래와 같이 크게 두 가지로 나뉩니다.

• 인덱스의 종류

  • 순서 인덱스: 특정 값에 대해 정렬된 순서 구조
  • 해시 인덱스: 버킷의 범위안에서 값의 균일한 분포에 기초한 구조로 함수가 어떤 값이 어느 버킷에 할당되는지 결정

• 인덱스의 평가기준

  • 접근 시간: 데이터를 찾는데 걸리는 시간
  • 유지 비용: 새로운 데이터 삽입 및 기존 데이터 삭제 연산으로 인한 인덱스 구조 갱신 비용
  • 공간 비용: 인덱스 구조에 의해 사용되는 부가적인 공간 비용

📚순서 인덱스

순서 인덱스는 가장 기본적인 형태의 인덱스입니다.

• 순서 인덱스의 특징

  • 탐색키로 정렬된 순차 파일에 대하여 레코드에 대한 빠른 임의 접근이 가능하도록 구성한 인덱스입니다. 탐색키를 정렬하여 해당 탐색키와 탐색키에 대한 레코드와의 연계를 통하여 인덱스를 생성합니다.

• 순서 인덱스의 종류

  • 밀집 인덱스
  • 희소 인덱스
  • 다단계 인덱스

📄밀집과 희소 인덱스

• 인덱스 엔트리의 구조
  인덱스 엔트리는 <탐색키값, 포인터> 쌍으로 구성됩니다. 포인터는 탐색키에 대응되는 레코드에 대한 포인터로, 데이터 레코드가 저장되어 있는 디스크 블럭의 식별자와 블럭 안에서 레코드의 위치를 가리키는 오프셋으로 구성됩니다.

• 밀집 인덱스
  밀집 인덱스는 모든 레코드에 대해 <탐색키값, 포인터> 쌍을 유지합니다. 각 과목 레코드의 과목 코드에 대해 인덱스 엔트리가 구성되어 있는 것을 볼 수 있습니다. 따라서 과목 레코드를 찾는 경우 레코드를 직접 찾기 보다 크기가 훨씬 작은 밀집 인덱스를 메모리로 읽어 인덱스 엔트리를 찾은 후 레코드에 대한 포인터를 따라 접근하여 레코드를 빠르게 찾습니다.
  
  하지만 모든 레코드에 쌍으로 인덱스 엔트리가 대응되기 때문에 인덱스의 크기가 커지는 단점이 있습니다.

• 희소 인덱스
  희소 인덱스는 인덱스의 엔트리가 일부의 탐색키 값만을 유지합니다. 희소 인덱스에서 레코드를 찾는 경우 모든 탐색키가 존재하지 않기 때문에 찾고자 하는 탐색키 보다 작거나 같은 값 중에서 가장 큰 키값을 찾습니다.
  
  희소 인덱스는 인덱스 엔트리의 수가 적어 인덱스를 찾는 비용은 적게 드는 장점이 있지만 모든 레코드에 인덱스 엔트리가 만들어져있지 않아 검색 비용이 크다는 단점이 있습니다.

📄다단계 인덱스

4KB 크기의 한 블럭에 100개의 엔트리가 삽입될 때, 100,000,000개의 레코드에 대한 순서 인덱스는 1,000,000개의 블럭이 필요하고 4GB 공간이 필요합니다. 인덱스가 너무나 많은 공간을 차지하기 때문에 좀 더 효율적인 인덱스 관리를 위해 다단계 인덱스를 만들었습니다.

• 인덱스 크기에 따른 검색 성능

  • 인덱스 크기 < 메모리 크기
    디스크 I/O이 줄어 탐색 시간 축소

  • 인덱스 크기 > 메모리 크기
    저장된 블럭을 여러번 나누어 읽어야 하기 때문에 디스크 I/O 비용이 증가하여 탐색 시간이 증가

• 다단계 인덱스는 내부 인덱스와 외부 인덱스로 구성

  • 외부 인덱스를 내부 인덱스보다 희소한 인덱스로 구성하여 엔트리의 포인터가 내부 인덱스 블럭을 지칭
  • 포인터가 가리키는 블럭을 스캔하여 원하는 레코드 보다 작거나 같은 탐색키 값 중에 가장 큰 값을 가지는 레코드를 탐색

내부 인덱스는 1,000,000개의 블럭을 갖는 반면 외부 인덱스는 100개의 블럭만 사용하여 작은 크기의 외부 인덱스로 메모리에 적재 가능합니다.

내부 인덱스는 밀집 인덱스로, 외부 인덱스는 희소 인덱스로 구성되고 항상 정렬된 순서로 존재합니다.

• 다단계 인덱스에서 레코드를 읽는 순서
  
  1. 외부 인덱스에서 원하는 엔트리의 탐색키 값보다 작거나 같은 탐색키 값 중에서 가장 큰 값을 갖는 인덱스 엔트리를 찾는다.
  2. 이 인덱스 엔트리의 포인터가 가리키는 블럭을 적재한다.
  3. 내부 인덱스에 도달할 때까지 1~2 과정을 반복한다.
  4. 내부 인덱스에서 조건과 일치하는 인덱스 엔트리의 탐색키를 찾아 데이터 블럭을 적재한다.
  5. 해당 레코드를 사용자에게 반환한다.

📚B⁺-트리 인덱스

B⁺-트리 인덱스는 상용 DBMS에서 가장 널리 사용되는 순서 인덱스의 일종으로 경로의 길이가 같은 높이 균형 트리 형태로 구성되어 검색의 속도를 일정하게 향상시켜 안정적인 데이터 검색이 이뤄질 수 있도록 고려한 인덱스 구조입니다. 이진 탐색 트리와 다단계 인덱스를 섞어 놓은 구조입니다.

📄B⁺-트리 구조

루트 노드로 부터 모든 단말 노드에 이르는 경로의 길이가 같은 높이 균형 트리 구조입니다.

순서 인덱스는 파일이 커질수록 데이터 탐색에 있어서 접근 비용이 커지는 문제점을 해결하기 위해 제안되었습니다.

• 노드 구조
  일반적인 B⁺-트리의 노드 구조는 아래 그림과 같습니다. n - 1개의 탐색키값 K₁, K₂, …, K_n-1과 자식 노드를 가리키는 n개의 포인터 P₁, P₂, …, P_n을 포함합니다.
  노드 안의 탐색키 값은 정렬된 순서로 유지되어 있고 한 노드에 저장되는 최대 포인터 개수는 B⁺-트리의 차수에 의해 결정됩니다.

• 구성 요소
  1. 인덱스 세트: 루트노드와 중간노드로 구성
     • 단말노드에 있는 탐색키 값을 신속하게 찾아갈 수 있도록 경로를 제공하는 목적으로 사용됩니다. [n/2] ~ n 사이의 개수를 자식으로 소유합니다.
       
       
  2. 순차 세트: 단말노드로 구성
     • 모든 노드가 순차적으로 서로 연결되어 있습니다. 단말 노드는 적어도 \(\lceil (n-1)/2 \rceil\)개의 탐색키를 포함합니다. 탐색키에 대한 실제 레코드를 지칭하는 포인터를 제공합니다.

http://www.kwangsiklee.com/2018/10/개념정리-db-indexing과-hashing/

📄B⁺-트리 검색

단계 1: 현재 탐색 대상을 조사하여 탐색키값과 같거나 큰 탐색키 중 가장 작은 키를 찾습니다.

단계 2: 아래의 조건에 따라 다음 노드를 결정합니다.

1. K = V일 경우 포인터 P이 가리키는 노드를 N으로 결정
2. K > V일 경우 P가 가리키는 노드를 N을 결정
3. V보다 큰 탐색키가 없는 경우, 노드 내의 NULL이 아닌 마지막 포인터가 가리키는 노드를 N으로 결정

단계 3: N이 단말 노드가 아니면, 단계1 부터 반복합니다. N이 단말 노드인 경우, 탐색키값 K와 V가 같은 포인터 P를 반환합니다.

📄B⁺-트리 삽입, 삭제연산

• 레코드 삽입, 삭제 시 B⁺-트리 수정

  • 레코드 삽입: 노드에서 유지해야 할 탐색키와 포인터 수 증가로 인해 노드를 분할해야 하는 경우가 발생
  • 레코드 삭제: 노드에서 유지해야 할 탐색키 값과 포인터 수 감소로 형제 노드를 재분배 또는 병합해야 하는 경우가 발생
  • 높이 균형 유지: 노드가 분할되거나 병합되면서 높이의 균형이 맞지 않는 경우가 발생

• 삽입
  검색과 같은 방법을 사용하여 삽입되는 레코드의 탐색키 값이 속할 단말 노드를 탐색합니다. 해당 단말 노드에 <탐색키, 포인터> 쌍을 삽입합니다. 삽입 시 탐색키가 순서를 유지하도록 합니다.

아래의 B⁺-트리에 COM24를 삽입해봅시다.

삽입 대상 노드에 추가적인 저장할 공간이 부족할 경우 노드를 분할합니다.

• COM12를 하나의 단말 노드로 구성
• COM24와 COM31이 하나의 단말 노드로 구성

부모 노드에 탐색키를 조정하고 추가된 노드에 대한 포인터를 삽입합니다. COM24를 삽입한 모습입니다.

• 삭제
  삭제될 레코드의 탐색키를 통해 삭제될 탐색키와 포인터를 포함한 단말 노드를 탐색합니다. 같은 탐색키 값을 가지는 다중 엔트리가 존재할 경우, 삭제될 레코드를 가리키는 엔트리를 찾을 때까지 탐색 후 단말 노드에서 제거합니다. 단말 노드에서 제거된 엔트리의 오른쪽에 있는 엔트리들은 빈 공간이 없도록 왼쪽으로 이동합니다.

위의 B⁺-트리에 COM12를 삭제하면 아래와 같습니다.

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