파일과 인덱스

파일과 인덱스

DBMS의 상위 계층 구조는 사실상 페이지를 레코드의 집단으로 취급하고 세부적인 저장 구조에 대해서는 무시합니다. 레코드는 페이지에 저장되며, 페이지는 파일에 저장된다. 페이지가 파일에서 조직되는 형태에 따라 DB의 성질과 속도가 달라집니다.

힙(HEAP) 파일

• 가장 간단한 파일 구조이며, 레코드가 파일의 빈 공간에 순서 없이 저장
• 페이지 내의 데이터가 어떠한 형태로도 정렬되지 않음
  • 파일의 모든 레코드를 검색하면 다음 레코드를 되풀이하며 요청해야 함
• 파일의 레코드는 각기 유일한 RID를 가지며, 한 파일에 속하는 페이지는 크기가 모두 같다
• 파일의 Create Destory Insert와 RID를 통한 레코드 Delete Get 그리고 파일내의 모든 레코드 Scan 연산 지원

스캔 연산을 수행하려면 각 힙 파일에 속한 페이지들이 무엇이 있는지 알아야 하며, 삽입을 효율적으로 수행하려면 자유 공간이 남아있는 페이지들을 알아야 한다.

인덱스 개요

• 대부분의 자료 구조에서는 저장된 데이터의 RID를 직접 알 수 없다
• 정렬되지 않은 자료 구조에서 동등 검색을 수행할 경우, 전체 자료 구조를 스캔해야 한다.
• Index - 선택 조건에 맞는 RID를 구할 수 있도록 만든 보조 자료 구조

어떤 필드의 값에 대해 같은 데이터를 검색하는 경우가 많다. 이때 검색하려는 레코드의 RID만 알 수 있다면, 정렬되지 않은 힙과 같은 형식의 파일에서 해당 레코드는 쉽게 검색할 수 있으나, 힙 파일에는 그러한 기능이 없다. 이런 경우 Index를 사용하면, 선택 조건에 맞는 레코드의 RID를 구할 수 있는 보조 자료구조이다.

Clustered	Non-Clustered
항상 순서를 유지한다	순서와 상관 없다
한 테이블당 하나만 존재한다(테이블 인덱스)	한 테이블에 여러개 생성할 수 있다
범위 검색에 유리하다(군집화)	index를 저장할 추가적인 공간이 필요하다
데이터가 많아 질수록 insert 성능이 나빠진다	insert시 추가 작업 (인덱스 생성) 필요하다

ISAM

• 색인 순차 접근 방식 (Indexed Sequential Access Method) 파일
• 데이터를 순서대로 저장하거나 특정 항목을 색인으로 처리할 수 있는 파일 처리 방법
• 인덱스를 순차적으로 구성하여 큰 인덱스의 성능 문제를 해결
  • 인덱스 파일이 클 경우, 인덱스를 계층화하여 인덱스에 대한 인덱스를 생성
  • 완전한 정적 구조로, 인덱스 계층의 페이지가 수정되지 않음
• 파일 구조
  • 인덱스 구역 (비 단말 페이지) 기본 구역에 있는 레코드들의 위치를 찾아가는 인덱스가 기록되는 구역
  • 기본 구역 (기본 단말 페이지) 실제 레코드들을 기록하는 부분으로, 각 레코드는 키 값 순으로 저장
  • 오버플로우 구역 (오버 플로우 페이지) 기본 구역에 빈 공간이 없을 경우 새 레코드의 삽입을 위한 예비적 구역

ISAM은 인덱스가 큰 경우에 대한 문제를 해결하기 위해 착안 되었습니다.

B+ 트리

• ISAM의 오버 플로의 단점을 개선한 동적 트리 자료구조
• 내부 노드들이 탐색 경로를 유도하고 단말 노드들이 데이터 엔트리를 가지는 군형 트리
• 일반적으로 ISAM보다 우수한 구조