[database] 인덱스

• 인덱스의 필요
  • 데이터 검색에서 발생하는 비효율적인 데이터 입출력 문제를 해결하기 위한 목적으로 시작
    • 인덱스: DBMS에서 요청된 레코드에 빠르게 접근할 수 있도록 지원하는 데이터와 관련된 부가적인 구조
    • 인덱싱: 인덱스를 구성하고 생성하는 작업
  • 인덱스의 탐색키를 이용하여 해당 레코드가 저장된 블럭을 디스크 저장장치 또는 메모리에서 파악하여 해당 블럭을 빠르게 적재
    • 탐색키
      • 파일에서 레코드를 찾는데 사용되는 컬럼이나 컬럼의 집합
• 인덱스 기반의 검색 과정
  • 인덱싱 되어 있는 컬럼을 메모리에 빠르게 올리고 디스크에서 찾음
• 인덱싱의 종류
  
  • 인덱스의 종류
    • 순서 인덱스: 특정 값에 대해 정렬된 순서 구조
      • 순서 인덱스의 특징
        • 탐색키로 정렬된 순차파일에 대해 레코드에 대한 빠른 접근이 가능하도록 구성한 인덱스
          • 탐색키를 정렬하여 해당 탐색키와 탐색키에 대한 레코드와의 연계를 통해 인덱스 생성
          • 탐색키의 순서로 정렬된 순차파일에서 데이터레코드에 대한 빠른 임의접근이 가능하도록 순서 인덱스를 사용할 수 있음 
        • 인덱스 엔트리의 구조
          • 탐색키값, 블럭ID, 오프셋으로 구성
        • 밀집 인덱스
          • 모든 레코드에 대해 탐색키값, 포인터 쌍을 유지
        • 희소 인덱스
          • 인덱스의 엔트리가 일부의 탐색키 값만을 유지
        • 다단계 인덱스의 필요
          • 4KB 크기의 한 블럭에 100개의 엔트리가 삽입될 떄, 1억개의 레코드에 대한 순서 인덱스
            • 1억개의 블럭 = 4GB의 공간 필요
          • 인덱스 크기에 따른 검색 성능
            • 인덱스 크기 < 메모리 크기
              • 디스크 I/O이 줄어 탐색 시간이 축소
            • 인덱스 크기 > 메모리 크기
              • 저장된 블럭을 여러번 나누어 읽어야 하기 때문에 디스크 I/O 비용이 증가하여 탐색 시간이 증가 
        • 다단계 인덱스
          • 내부 인덱스와 외부 인덱스로 구성
            • 외부 인덱스를 내부 인덱스보다 희소한 인덱스로 구성하여 엔트리의 포인터가 내부 인덱스 블럭을 지징
            • 포인터가 가리키는 블럭을 스캔하여 원하는 레코드보다 작거나 같은 탐색키 값 중에 가장 큰 값을 가지는 레코드를 탐색
          • 내부 인덱스는 1000000개의 블럭을 갖는 반면, 외부 인덱스는 100개의 블럭만 사용하여 작은 크기의 외부 인덱스로 메모리에 적재 가능
        • 다단계 인덱스의 구조
          • 외부 인덱스 -> 내부 인덱스 -> 데이터 블럭 ... 
    • 해시 인덱스: 버킷의 범위 안에서 값의 균일한 분포에 기초한 구조로 해시 함수가 어떤 값이 어느 버킷에 할당되는지 결정
  • 인덱스의 평가기준
    • 접근시간: 데이터를 찾는 데 걸리는 시간
    • 유지 비용: 새로운 데이터 삽입 및 기존 데이터 삭제 연산으로 인한 인덱스 구조 갱신 비용
    • 공간 비용: 인덱스 구조에 의해 사용되는 부가적인 공간 비용
  • B+ 트리 인덱스
    • 이진 탐색 트리(binary search tree)와 특징이 유사함
    • 루트노드, 중간노드, 단말노드로 이루어짐
    • B+ 트리의 구조
      • 루트 노드로부터 모든 단말 노드에 이르는 경로의 길이가 같은 높이 균형 트리
        • 순서 인덱스는 파일이 커질수록 데이터 탐색에 있어서 접근 비용이 커지는 문제점을 해결하기 위해 제안
        • 상용 DBMS에서도 널리 사용되는 대표적인 순서 인덱스
      • B+ 트리의 rntjd dyth
        • 인덱스 세트: 루트노드와 중간노드로 구성
          • 단말노드에 있는 탐색키 값을 신속하게 찾아갈 수 있도록 경로를 제공하는 목적으로 사용
          • [n/2] ~ n 사이의 개수를 자식으로 소유
        • 순차 세트: 단말노드로 구성
          • 모든 노드가 순차적으로 서로 연결
          • 단말 노드는 적어도 (n-1) / 2 개의 탐색키를 포함
          • 탐색키에 대한 실제 레코드를 지칭하는 포인터를 제공

•  
  •  
    •  
      •   B+ 트리에서 데이터를 찾아가는 과정
        • 노드를 접근하는 과정은 해당 데이터 값보다 더 큰 값중에서 가장 작은 노드를 따라가는 것이 일반적
          • 만약 해당 데이터 값보다 큰 값이 없을 경우 오른쪽 노드를 가리키는 포인터를 따라감
      • B+ 트리에서의 삽입, 삭제
        • 레코드 삽입, 삭제 시 B+ 트리 수정
          • 레코드 삽입
            • 노드에서 유지해야 할 탐색키와 포인터 수 즈악로 인해 노드를 분할해야 하는 경우가 발생
          • 레코드 삭제
            • 노드에서 유지해야 할 탐색키 값과 포인터 수 감소로 형제 노드와 키를 재분배 또는 병합해야 하는 경우가 발생
          • 높이 균형 유지
            • 노드가 분할되거나 병합되면서 높이의 균형이 맞지않는 경우가 발생
        • 삽입: 검색과 같은 방법을 사용하여 삽입되는 레코드의 탐색키 값이 속할 단말 노드를 탐색
          • 해당 단말 노드에 <탐색키, 포인터> 쌍을 삽입
          • 삽입 시 탐색키가 순서를 유지
        • 삭제: 삭제될 레코드의 탐색키를 통해 삭제될 탐색키와 포인터를 포함한 단말 노드를 탐색
          • 같은 탐색키 값을 가지는 다중 엔트리가 존재할 경우 삭제될 레코드를 가리키는 엔트리를 찾을 떄까지 탐색 후 단말 노드에서 제거
          • 단말 노드에서 제거된 엔트리의 오른쪽에 있는 엔트리들은 빈 공간이 없도록 왼쪽으로 이동
      • 노드가 분할되는 삽입
        • 삽입 대상 노드에 추가적인 저장할 공간 부족: 노드 분할
          • 왼쪽 탐색키를 하나의 단말 노드로 구성
          • 추가된 탐색키와 기존 오른쪽 탐색키를 하나의 단말 노드로 구성
        • 부모 노드에 탐색키를 조정하고 추가된 노드에 대한 포인터를 삽입
    • 탐색키의 삭제
      • 탐색키가 재분배되는 삭제
        • 해당 단말노드가 삭제 후에 탐색키가 존재하지 않는 경우
        • (n-1) / 2개보다 탐색키가 적으므로 다른 노드와 별도의 재구성하는 작업이 필요
      • 삭제 대상인 탐색키가 저장된 노드의 오른쪽의 형제 노드와 키를 재분배