[DBMS] Heap File & Sorted File

Heap file은 앞서 살펴 본것 처럼  레코드 간 순서가 없이 파일에 빈 공간이 있으면 레코드를 저장하는 방법이다. 

(Unnordered collection of record)

이 장에서는 어떻게 File record를 Heap file이 관리하는지. Insert/delete/modify에서 확이하고 각각의 cost를 확인해보려고 하다. 

Type of File

File의 구조 유형은 앞서 살펴본 것과 같이 다음과 같다. 

• Heap Files (Unordered): full scan of record에 유리
  • 레코드가 순서 없이 페이지에 저장.
  • 레코드 삽입 시 페이지와 빈 공간 관리 필요.
  • Heap file 자체는 조건 기반 검색 시 파일의 순차 스캔만 가능 -> Index가 필요한 이유 
  • 새로운 레코드는 파일 끝에 추가한다고 아래에서는 가정 
• Sorted Files: order 혹은 특정 range of record가 있을 때 유리
  • 레코드가 정렬된 순서로 저장.
  • Seqeuntial이라고도 함 
  • 삽입: 새로운 레코드는 정렬된 위치를 찾은 후 삽입되며, 다른 레코드가 이동해야 할 수 있음
• Clustered Files: group data in to blocks 
  • 비슷한 레코드가 물리적으로 가까운 페이지에 저장.
  • 연관된 레코드들을 모아서 관리하기 때문에 JOIN쿼리에 유리
  • 단일 테이블을 조회하는 쿼리에는 공간적으로 비효율적
• Index Files:
  • B+ 트리 또는 해싱을 통해 레코드에 빠르게 접근.
  • B+트리의 leaf node에 레코드를 저장하는 방식으로, INSERT와 DELETE연산에서도 순서가 보장
  • 해시함수에 search-key를 넣어 계산한 값을 통해 레코드가 어느 블록에 위치하는지 찾을 수 있음 

그렇다면 가장 좋은 File organization은 무엇인가? 이는 Access pattern에 따라 다를 것이다. 그럼으로 아래의 cost model을 통해 데이터베이스의 연산 비용을 정량적으로 추정해보자.  

 

아래의 내용을 보기 전에 먼저 답지를 공개하면 다음과 같다. 

 

Cost Model and Analysis

다음과 같은 구조에서 아래와 같이 정의히자. 

• B: The number of data blocks in the file
• R: Number of records per block
• D: (Average) time to read/write disk block

또한 기본가정으로 아래의 가정을 가진다

 

• 데이터가 디스크에 저장됨: 파일은 블록 단위로 관리.
• 균일한 접근: 랜덤한 접근 패턴을 가정.
• 연산 단위: 평균적으로 블록 읽기/쓰기 비용만 고려(메모리 작업 비용 제외)
• Heap file 가정: Insert는 가장 마지막 파일 이후에만 append한다
• Sorted fle 가정: pack은 deletion이후에 이루어진다

 

아래의 예시상황을 가정하자. 

 

• B: The number of data blocks = 5 
• R: Number of records per block = 2 
• D: (Average) time to read/write disk block = 5ms

For Scan all records

전체 스탠의 경우 모든 블록을 읽어 레코드를 순차적 접근함으로

Scan all record Cost = B×D

Cost는 둘다 B * D와 같다(읽고 쓰기는 block단위로 이루어진다!!)

 

Equality Search

특정 값을 가지는 레코드를 검색하는 cost는 다음과 같다. 

Heap file

Heap file은 unordered collection이라는 것을 생각하자. 

• P(i): 우리가 찾고자하는 key가 page i에 있을 확률 = 1/B

• T(i): page i에 있는 key를 toch하기 위해 몇개의 page를 들려야하는가? = i

 

그럼으로 cost는 아래와 같고 이는 B/2로 근사된다. 

즉, D까지 고려하면 0.5×B×D 이다. 

Sorted file

Sorted file의 경우 정렬이 되어있기에 Binary search를 사용 가능하다. 그럼으로 Worst와 Avg모두 log2B이다.

 

즉 D까지 고려하면 log2​(B)×D이다. 

 

Range Search

특정 범위(예: 값이 10에서 20 사이인 레코드)를 검색할 때

Heap file

모든 블록을 스캔해야한다. 이는 Heap file이 정렬 기준 없이 unorder하기에 모든 블록의 정보를 알고나서 범위 조건을 확인해야하기 때문이다. 

그럼으로 Cost는 B x D이다. 

Sorted file

범위의 시작 위치를 이진 검색으로 찾은 후 연속적으로 읽음.

연산에서 접근해야하는 페이지 or 레코드의 수를 pages라고 할 때 

cost는 log2​(B + pages) × D 이고 

Insert

Heap file

앞서 말한 것처럼 file의 맨 끝에 추가하면 되기에 Cost는 2*D이다. 이때 2는 읽기/쓰기가 모두 필요하기에 추가된다. 

 

Sorted file

정렬된 위치를 찾아 삽입하고, 이후에 데이터 이동이 필요하다(정렬을 유지)

Find location for record. Cost = log2BD 와 이동하는데 B*D 비용이 발생하여 최종적으로 

Cost는 ((log2B)+B)*D 이다. 

Delete

Heap file

평균적으로 삭제하려는 record를 찾기 위해 B/2의 cost가 소요되고, 해당 파일을 삭제하기 위해 +1의 디스크 작업이 필요로 한다. 

따라서 (B/2 + 1) * D의 Cost가 소요된다. 

• Cost = (B/2 + 1) * D

Sorted file

Sorted File의 경우 해당 record를 찾는데 log2B*D의 cost가 발생하고 이후 

정렬상태를 유지하기 위해 삭제된 블록 이후의 모든 레코드를 이동(shift)해야 한다, 이때 이는 이동 작업은 나머지 모든 레코드가 포함된 블록을 읽고 쓰는 작업을 포함하기에 B*D의 비용이 든다. 

그럼으로 이 둘을 합하면

 

Cost  = (log2​(B)+B)×D

 

Index..?

Index를 이용하면 특정 레코드를 효율적으로 찾을 수 있기에 다음에는 Index에 관해 알아보자.