10 인덱싱과 해싱 II

• 인덱싱과 해싱 II

  10.1 B-트리 인덱스

• B-트리 인덱스
  • B+-트리의 원형
  • B-트리와 B+-트리의 차이점
    • 단말 노드의 검색키가 비단말 노드에 중복되어 삽입되지 않음
    • 리프 노드의 모든 검색키와 레코드가 순차적으로 정렬되고 연결되어 있지 않음

         

  • 비단말 노드의 구조

    

       

    

   

   

10.2 정적 해싱과 동적 해싱

• 해싱의 개념

  검색키 값에 직접 산술적인 연산을 적용하여 데이터가 저장되어 있는 버킷의 주소를 계산하여 데이터에 접근하는 방법

  • 해시 함수 : 검색키 값을 입력하면, 레코드에 대한 디스크 블록 주소(버킷)를 반환하는 함수
  • 버킷
    • 해시 파일 구조에서 사용하는 한 개 이상의 레코드를 저장할 수 있는 공간의 단위
    • 일반적으로 버킷 하나가 디스크 블록 하나를 나타내지만 크기 조정이 가능함

      

• 정적 해싱
  • 정적 해싱: 저장 공간의 단위인 버킷 개수가 고정된 기법

       

  • 정적 해싱에서 키값이 𝑘𝑖인 레코드 삽입
    • ℎ𝐾𝑖을 통하여 𝐾𝑖에 대응하는 버킷 주소를 구함
    • 레코드를 해당 버킷에 저장

         

  • 정적 해싱에서의 레코드 탐색
    • ℎ𝐾3=hK7= 𝑗 인 경우
    • 두 레코드 모두 같은 버킷에 있으므로 𝑗 번 버킷안의 모든 레코드를 탐색하여 선택하는 과정이 필요

         

• 해시 함수
  • 충돌: 서로 다른 레코드가 동일한 버킷에 대응되는 경우
  • 동거자: 같은 버킷 주소를 갖는 레코드들
  • 오버플로
    • 버킷에 레코드를 저장할 수 있는 여유 공간이 없을 때 발생
    • 주로 별개의 버킷을 할당하여 처리
    • 오버플로는 많이 발생할수록 레코드 접근시간이 길어지고 성능이 저하

         

    

     

• 동적 해싱
  • 정적 해싱의 문제점
    • 데이터베이스의 크기가 커짐에 따른 성능 감소
    • 미리 큰 공간을 잡을 경우 초기에 상당한 양의 공간이 낭비
    • 재구성 시 새로운 해시 함수를 선택하면 모든 레코드에 대하여 다시 계산하고 버킷에 할당하는 비용이 발생
  • 동적 해싱: 버킷의 개수가 데이터베이스의 크기에 따라 변경되는 기법

       

• 확장성 해싱
  • 데이터베이스의 증대 혹은 축소에 따른 인덱스의 구조를 조절하기 위해 해시 함수의 동적 변경을 허용하는 기술
  • 디렉터리와 버킷으로 구성된 2단계 구조
    • 디렉터리는 디스크에 저장되는 버킷 주소 테이블
    • 디렉터리 깊이를 의미하는 정수값 d를 포함하는 헤더와 데이터가 저장된 버킷에 대한 2^d개의 포인터로 구성
  • 모조키(pseudo key)
    • 레코드의 키 값을 일정 길이와 비트 스트링으로 변환한 것
    • 모조키의 첫 d 비트를 사용하여 디렉터리에 접근
  • 버킷 헤더
    • 정수값 𝑖(≤𝑑)가 저장되어 있음을 표시
    • –𝑖는 버킷에 저장되어 있는 레코드의 모조키들이 처음부터 𝑖 비트까지 일치함을 표시

         

      

         

  • 레코드 삽입에 의해 분할된 확장성 해싱 파일

       

    

       

  10.3 비트맵 인덱스

• 비트맵 인덱스
  • 다중키를 가진 질의를 효율적으로 처리하기 위해 고안된 특수한 형태의 인덱스
  • 비트맵
    • 간단한 비트의 배열
    • 릴레이션 𝑟의 속성 𝐴 에 대한 비트맵 인덱스는 𝐴가 가질 수 있는 값에 대해 비트맵을 구성
    • 각 비트맵은 릴레이션에 있는 레코드 수 n개 만큼의 비트로 표현
  • 𝑖 번째 레코드가 속성 𝐴에 대해 해당 속성값을 가지면 비트맵의 𝑖 번째 비트를 1로, 그렇지 않으면 0으로 설정

    

• 비트맵 인덱스의 사용 예
  • 성별이 남자이고 성적이 B인 학생의 정보를 출력

    => SELECT *FROM 학생

    WHERE 성별='남자' AND 성적='B'

       

  • 성별의 '남자'와 성적의 'B'의 비트열에 대한 비트 논리곱 연산을 수행

    => 성별 남자 1 0 0 1 0 1

    &

    성적B 1 0 0 1 0 0

    1 0 0 1 0 0

       

    

       

  • 비트맵의 활용
    • 속성에 대한 값이 유한하고 범위가 비교적 작은 규모일 때 용이

      Ex) 직책, 학과, 혈액형 등

  • 비트맵 인덱스의 크기
    • 실제 렐레이션 크기에 비해 자유로움
    • 레코드의 길이가 수백 바이트가 되어도 바이트 인덱스에서는 하나의 비트로 표시