이론공부/화일처리및응용

화일 처리 및 응용 공부 #17 (인덱스된 순차화일 ,B+트리)

한반가 2021. 6. 4. 18:32

2021.05.31 - [이론공부/화일처리및응용] - 화일 처리 및 응용 공부 #16 (트라이)

인덱스된 순차화일의 구조

  • 인덱스된 순차 화일은 순차데이터 화일과 인덱스 화일로 구성

 

  • 순차 데이터 화일
    • 키 값에 따라 레코드들이 순차적으로 정렬
    • 레코드 전체에 대한 순차 접근 지원
  • 인덱스 화일
    • 화일의 레코드들에 대한 키 값과 포인터를 저장
    • 개별 레코드에 대한 직접 접근을 지원
  • 각 화일은 블록으로 구성
    • 인덱스화일
      • 인덱스 블록으로 구성
      • 트리 구조를 형성
    • 순차 데이터 화일
      • 데이터블록으로 구성
      • 데이터 블록들을 연결 리스트로 논리적 순서를 유지
    • 블록은 순차적으로 저장된 키 값과 자유 공간을 포함

 

인덱스된 순차 화일 구조

 

  • 마스터 인덱스
    • 인덱스 트리 최상위 레벨 인덱스 블록
  • 인덱스 엔트리 구성
    • <최대 키값, 포인터>
    • 포인터는 해당 키 값을 최대 키 값으로 갖는 다음 레벨의 인덱스 블록이나 데이터 블록에 대한 주소
  •  자유공간
    • 레코드 추가 삽입을 위한 예비공간
    • 화일 생성시 각 블록에 분산 배치
  • 키 32에 대한 직접 검색 방법
    - 데이터 블록 2를 찾고 블록내에서는 순차 탐색

 

레코드 삽입

 

B+ 트리

  • 인덱스 세트와 순차 세트로 구성되어있다.
  • 순차 탐색의 성능 향상을 목적으로 설계됨
  • 기존 B트리의 순차 탐색을 부완

 

  • 인덱스 세트
    • 리프 이외의 노드로 구성
    • 키 값만 저장
    • 리프 노드를 접근하는 경로로만 이용
  • 순차 세트
    • 리프 노드들로 구성
    • 실제 모든 <키 값, 데이터 레코드의 주소>들이 저장
    • 키 값의 순서에 따라 모든 레코드를 순차 접근하는데 이용

B+ 트리 구조 예시

인덱스 세트에 있는 20 43은 리프노드에 다가가기 편하게 하기위한 분기점(경로)으로 보자.

 

 

B+트리 구조

손으로 일일이 타이핑 하기 귀찮다...

 

 

B+ 트리와 B 트리 차이 정리

  • 인덱스 세트는 리프 노드에 있는 키값을 찾는 경로로만 이용
    - 인덱스 세트에 있는 키 값은 순차세트에 다시 나타난다

  • 순차 세트는 실제 데이타 레코드를 찾는데 이용(키값과 그 키값을 가진 레코드에 대한 포인터저장)

  • 인덱스 세트의 노드와 순차세트의 노드에 들어갈 수 있는 키의 개수가 다르다( 구조가 다르다 )

  • 순차 세트의 모든 노드는 링크로 연결되어 있다.
    - 화일 레코드의 순차 접근이 효율적

 

B+ 트리 키 값 삽입

  • B 트리의 리프 노드에 삽입하는것과 유사함

    - 다만 노드가 오버플로 되어 분할 시 중간 키값(분할된 노드 왼쪽 노드에서 제일 큰값)이 부모 인덱스 노드로 올라가 저장되고, 분할된 노드에도 저장.

    - 분할된 리프 노드는 순차 세트의 연결리스트에 순차성이 유지되는식으로 링크로 연결

    - 인덱스 노드 분할 시에는 B 트리와 똑같은 알고리즘을 수행하고 중간 키값이 부모 노드로 올라간다ㅐㅂ

삽입 예시
삽입 예시 2
삽입 예시 3

 

 

B 트리와 성능 비교

  • 키 값의 직접 검색
    • 검색은 항상 리프노드 까지 내려가야만 종료
    • 검색하고자 하는 키 값이 인덱스 세트에서 발견되더라도 리프 노드까지 내려가야만 실제 레코드의 주소를 알 수 있다.
    • 키값이 인덱스 세트에서 발견되더라도 레코드가 반드시 있다는 것은 아니다.(인덱스 세트에서 있다고 해서 순차세트에서 이미 삭제되 있을 수 있기 때문)
    • 같은 수의 키 값을 가지고 있는 B트리에 비해 레벨이 낮아 질 수 있다.
    • 인덱스 노드는 레코드 포인터를 저장하지 않으므로 노드 내 공간이 절약된다.
      -> 트리 레벨이 낮아 질 수 있다.
  • 순차 검색
    • 연결 리스트를 순회 -> B 트리에 비해 효율적
  • B+트리는 직접 처리와 순차 처리를 모두 필요로 하는 응용에서 효율적

 

VSAM 화일

  • B+ 트리 인덱스 구조 기법을 이용하는 대표적인 순처 화일 구성방법

  • VSAM 화일 구조
    • 제어구간
      - 데이터 레코드 저장을 위한 공간 단위
    • 제어 구역
      - 일정 수의 제거구간으로 구성된 공간 단위
    • 순차 세트
      - 제어 구역에 대한 인덱스를 저장하는 인덱스 공간
    • 인덱스 세트
      - 순차세트에 대한 상위 인덱스, 다단계로 구성

VSAM 화일 구조

 

가볍게 이해만 하고 넘어 가자

ISAM 화일

ISAM 화일 설명

 

ISAM 화일 구조

VSAM 화일과 마찬가지로 가볍게 읽고 넘어가도 되는 내용이라 수업 자료만 캡처 해서 정리
B+ 트리와 인덱스된 순차화일 구조를 이해해 두자, 이전내용의 B트리 B*트리도 이해해 두자