09 인덱싱과 해싱 I

1. 인덱싱과 해싱 I

   9.1 인덱싱

• 인덱싱이란?
  • 인덱싱은 데이터 검색에서 발생하는 비효율적인 문제를 해결하기 위한 기법
    • 인덱스: DBMS에서 요청된 레코드에 빠르게 접근할 수 있도록 하는 데이터와 관련된 부가적인 구조
    • 인덱싱: 인덱스를 디자인하고 생성하는 작업
  • DMBS는 인덱스를 통하여 레코드가 디스크 저장장치 또는 메모리의 어느 블록에 저장되어 있는지 파악하고, 해당 블록을 읽어 들임
    • 검색키: 파일에서 레코드를 찾는데 사용되는 컬럼이나 컬럼의 집합

         

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

       

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

       

9.2 순서 인덱스

• 순서 인덱스
  • 검색키로 정렬된 순차파일에 대하여 레코드에 대한 빠른 접근이 가능하도록 순서 인덱스를 사용
    • 검색키를 정렬하여 해당 검색키와 관련된 레코드와의 연계를 통하여 인덱스 생성
• 인덱스 엔트리의 구조

검색키 값

포인터

포인터: 검색키에 대응되는 한 개 이상의 레코드에 대한 포인터로, 레코드가 저장되어 있는 디스크블록의 식별자와

블록 안에서 레코드를 인식하기 위한 오프셋으로 구성

• 순서 인덱스의 분류
  • 밀집(dense) 인덱스
  • 희소(sparse) 인덱스
• 밀집 인덱스
  • 모든 레코드에 대해 [ 검색키 값 | 포인터 쌍 ] 을 유지

    

  • 인덱스의 엔트리가 소수의 검색키 값만을 유지

    

   

• 다단계 인덱스
  • 4KB 크기의 한 블록에 100개의 엔트리가 들어간면, 100,000,000 개의 레코드의 인덱스를 유지
    • 100,000,000ro의 블록 = 4GB의 공간
    • 인덱스의 용량이 작아 전체가 메모리에 적재되면 탐색시간이 축소
    • 인덱스가 메모리보다 크다면 저장된 블록을 디스크로부터 읽어야하기 때문에 I/O 비용이 증가하여 탐색시간 증가

      => 다단계 인덱스를 구성하여 해결

  • 내부 인덱스와 외부 인덱스로 구성
    • 외부 인덱스를 내부 인덱스보다 희소한 인덱스로 구성하여 엔트리의 포인터가 내부 인덱스 블록을 지칭
    • 포인터가 가리키는 블록을 스캔하여 원하는 레코드보다 작거나 같은 검색키 값 중에 가장 큰 값을 가지는 레코드를 찾음
  • 내부 인덱스는 1,000,000 개의 블록을 갖고, 외부 인덱스는 100개의 블록만 사용하여 40MB의 외부 인덱스는 메모리에 적재가능

    

   

   

9.3 B+_트리 인덱스

   

   

• B+_트리 인덱스
  • 루트 노드로부터 모든 단말 노드에 이르는 경로의 길이가 같은 높이 균형 트리
    • 순서 인덱스는 파일이 커질수록 데이터 탐색에 있어서 접근 비용이 커지는 문제점을 해결하기 위해 제안
    • 현재까지도 널리 사용되는 대표적인 순서 인덱스

         

  • B+_트리의 노드 구조

    

     

• B+_트리 구성
  • 인덱스 세트: 단말이 아닌 노드로 구성
    • 단말 노드에 있는 검색키 값을 신속하게 찾아갈 수 있도록 경로를 제공하는 목적으로 사용
    • [n/2], n 사이의 자식을 가짐
  • 순차 세트: 단말 노드로 구성
    • 모든 노드가 순차적으로 서로 연결
  • 단말 노드의 예

    

       

• 

     

• B+_트리의 특징
  • 루트는 2, 혹은 𝑛/2~𝑛개 사이의 포인터를 가짐
  • 루트와 단말 노드를 제외한 모든 노드는 최소 𝑛/2 에서 𝑛개 사이의 포인터를 가짐
  • 모든 단말 노드는 루트로부터 같은 거리
  • 단말 노드가 아닌 노드에 있는 검색키 값의 수는 그 노드의 포인터 수보다 하나 적음
  • 단말 노드는 데이터 파일의 순차 세트를 나타내며 모두 리스트로 연결
  • 단말 노드는 적어도 (𝑛−1)/2 개의 검색키 값을 포함

       

• B+_트리 상에서의 검색
  • V=검색키, 현재 방문한 노드 = N
    • 𝑁을 조사하여 𝑉값과 같거나 𝑉보다 큰 검색키 중 가장 작은 𝐾𝑖를 찾음
    • 𝐾𝑖=𝑉이면 𝑃𝑖+1이 가리키는 노드를 방문함 (𝑁=𝑃𝑖+1)
    • 𝐾𝑖>𝑉 이면 𝑃𝑖 이 가리키는 노드를 방문함 (𝑁=𝑃𝑖)
    • 𝑉>𝐾𝑚−1 이면, 마지막 포인터 𝑃𝑚이 가리키는 노드를 방문함 (𝑁=𝑃𝑚)
    • 변경된 𝑁이 단말 노드가 아니라면, 단말 노드가 될 때까지 이전 과정을 반복
    • 𝑁이 단말 노드라면

      𝐾𝑖=𝑉이면 𝑃𝑖이 가리키는 레코드를 읽음

      𝐾𝑖와 같은 𝑉 가 없다면 𝑉를 가지는 레코드는 존재하지 않음

     

• B+_트리 상에서의 검색 예

  => '장보고' 검색

  

     

• B+_트리 상에서의 삽입과 삭제
  • 삽입: 검색과 같은 방법을 사용하여 삽입되는 레코드의 검색키 값이 속할 단말 노드를 찾음
    • 해당 단말 노드에 <검색키 값, 포인터> 쌍을 삽입
    • 삽입 시 검색키가 순서를 유지
  • 삭제: 삭제될 레코드의 검색키를 통해 삭제될 검색키와 포인터를 포함한 단말 노드를 찾음
    • 같은 검색 키 값을 가지는 다중 엔트리가 존재할 경우, 삭제될 레코드를 가리키는 엔트리를 찾을 때까지 탐색 후 단말 노드에서 제거
    • 단말 노드에서 제거된 엔트리의 오른쪽에 있는 엔트리들은 빈 공간이 없도록 왼쪽으로 이동

         

• 노드가 분할되는 삽입

  =>'강감찬' 삽입

  

     

     

  

  • 강감찬을 삽입하고자 하는 노드에 더 이상 저장할 공간이 없으므로 노드를 위 그림과 같이 분할
    • 강감찬과 김영희를 하나의 단말 노드로 구성
    • 나태양과 도철수가 하나의 단말 노드로 구성

         

    

    • 새로 만들어진 단말 노드의 가장 작은 검색키 값을 가진 '나태양'은 부모 노드에 공간이 존재하기 때문에

      추가적인 노드 분할 없이 새로운 노드를 가리키는 포인터를 삽입

   

   

• B+_트리 상에서 노드가 병합되는 삭제
  • 강감찬이 추가된 B+트리에서 피천득 삭제
    • 피천득이 있는 단말 노드를 검색

      해당 단말 노드는 삭제 후 홍길동만 남게 됨

      (𝑛−1)/2 개 보다 적은 검색키 값이 적으므로 다른 노드와의 병합이 필요

         

    • 홍길동이 저장된 노드의 왼쪽의 형제 노드와 병합

      홍길동을 포함한 엔트리를 형제 노드로 이동

      비워진 노드를 삭제

      비워진 노드를 가리키는 포인터도 삭제

      기존의 포인터를 대체할 '정도전＇을 부모 노드에 삽입

         

  • '피천득' 삭제 결과