File Organization - Heap vs Sorting vs Hash

File Organization- Heap vs Sorting vs Hash

파일구조(File Organization)

파일이 디스크에 저장되어 있을 때 레코드를 파일에 배치하는 방법이다. 예를 들어 직원들을 알파벳 순으로 검색 할때 파일을 이름 순으로 정렬하는 것이 좋은 File Organization이다.

비용 모델(Cost Model)

B개의 데이터 페이지(=블록)이 있고, 페이지마다 R개의 레코드가 있다고 하자.
페이지 하나를 읽고 쓰는데 걸리는 평균 시간을 D라고 하며, 한 레코드를 처리하는데 걸리는 시간은 C라고 하자.
그리고 한 레코드에 해시 함수를 적용시키는데에 걸리는 시간은 H라고 하자.

보통 D는 15ms, C와 H는 100ns의 값을 가진다.
하드웨어적으로 전체 비용의 대부분은 입출력 비용이 차지하기 때문에, C와 H는 무시하는 걸로 하고 D, B, R로만 비용을 측정해보자.
디스크에서 읽고 쓰는 페이지의 수를 입출력의 기준으로 삼는 단순화된 모델을 사용하기로 한다.
디스크 시스템은 연속된 페이지들로 구성된 블록 단위 접근을 통해 단 한번의 입출력 요청으로 읽어낼 수 있기 때문이다.

---

비교할 연산들은 다음과 같다.

• Scan : 파일에 있는 모든 레코드를 가져온다. 파일에 있는 페이지들은 디스크로 부터 버퍼 풀로 반입되어야 한다. 버퍼 풀의 페이지 내에서 원하는 레코드로 가기 위한 CPU 오버헤드가 레코드 수만큼 추가로 필요하다.
• Equality Search : Equality 조건을 만족하는 모든 레코드를 가져온다. 예를 들어, ‘학번이 23인 학생에 대한 레코드를 찾아라’와 같은 검색이 이에 해당한다. 해당하는 레코드가 있는 페이지를 디스크로부터 반입한 후 그 페이지 내에서 원하는 레코드로 가야한다.
• Range Selection : Range 조건을 만족하는 모든 레코드를 가져온다. 예를 들어, ‘알파벳 순으로 이름이 “Smith” 이후가 되는 모든 학생 레코드를 찾아라’ 같은 탐색이 이에 해당된다.
• Insert : 주어진 레코드를 파일에 삽입한다. 디스크로부터 페이지를 꺼내서 새로운 레코드를 포함하도록 수정해 저장한다. File Organization에 따라서 다른 페이지들도 읽을 필요가 있을 수 있다.
• Delete : rid로 명세된 레코드를 삭제한다. 디스크로부터 해당 페이즈를 꺼낸 후, 레코드를 삭제 후 저장한다.

Heap vs Sorting vs Hash

Heap File

가장 간단한 파일 구조인 순서가 없는 파일이다.
페이지 내의 데이터가 어떠한 형태로도 정렬되지 않으며, 파일의 모든 레코드를 검색하려면 차위 레코드를 되풀이해서 요청해야한다.
파일의 레코드를 유일한 rid를 가지며, 한 파일에 속하는 페이지는 크기가 모두 같다.

• Scan:
  • B개의 페이지를 각각 검색해야 하는데 페이지당 D의 시간이 소요된다.
  • 즉, 총 비용은 BD 이다.
• Equality:
  • 원하는 레코드가 실제로 존재하고 탐색 필드의 값 분포가 균등하다면, 평균적으로 파일의 절반을 스캔하는 시간이 필요하다.
  • 그러므로 비용은 0.5BD 이지만, 조건을 만족하는 레코드가 존재하지 않은 경우에는 파일 전체를 검사하게 된다.
  • 그런데 primary key가 아닌 field에 대해서는 항상 파일 전체를 검사해야 한다.
  • 예를 들어 ‘age=18’을 만족하는 레코드는 파일 전체에 걸쳐 여러개가 존재할 수 있으며 몇개나 있는지는 미리 알 수 없기 때문이다.
• Range:
  • 조건에 맞는 레코드들이 파일 전체에 걸쳐 여러개가 존재할 수 있으므로, 전체 페이지를 검사해야 하므로 총 비용은 BD 이다.
• Insert:
  • 레코드는 항상 파일의 끝에 삽입된다고 가정하자.
  • 그러면 파일의 마지막 페이지를 꺼내와 레코드를 추가(D)하고 다시 저장(D)해야 하므로 비용은 2D 가 된다.
• Delete:
  • 레코드를 찾고, 해당페이지로부터 레코드를 삭제한 후, 수정된 페이지를 저장해야한다.
  • 삭제될 레코드는 rid로 지정된다고 가정하면, 탐색 비용은 D가 되고, 비용은 탐색 비용에 D를 더한 것과 같다.
  • 즉, 탐색비용(Search Cost) + D 가 된다

Sorting File

페이지 내의 데이터가 정렬되어 있는 파일구조를 말한다.

• Scan:
  • 모든 페이지들을 검사하므로 비용은 BD 이다.
• Equality:
  • 밑이 2인 logB 단계의 이진 탐색으로 원하는 레코드가 들어있는 첫 페이지를 구할 수 있다.
  • 그러므로 총 비용은 DlogB 이다.
• Range:
  • 조건을 만족하는 첫 레코드를 equality 경우 처럼 찾는다.
  • 그 다음 레코드가 조건의 범위를 넘어갈 때까지 순차적으로 레코드를 가져오면 된다.
  • 그래서 비용은 탐색비용과 탐색 조건을 만족하는 레코드들을 검색하는 비용을 합친 것과 같다.
• Insert:
  • 정렬 순서를 유지한 채 레코드를 삽입해야 하기 때문에 일단 파일에서 레코드가 삽입될 위치를 찾아야 한다.
  • 그 위치에 레코드를 추가하고, 후속 페이지들을 모두 꺼내서 새로 다시 저장해야한다. (파일에 비어있는 슬롯이 없다면 예전의 레코드들은 모두 한 슬롯씩 뒤로 밀려야하기 때문)
  • 레코드는 평균적으로 파일의 중간부분에 삽입된다고 할 수 있으므로, 새로운 레코드를 추가한 다음엔 파일의 후반을 읽어서 다시 저장해야한다.
  • 따라서 새 레코드의 위치를 찾는 비용 + 2*(0.5BD) 만큼의 비용이 든다.
  • 즉, 비용은 탐색비용 + BD 가 된다.
• Delete:
  • 레코드를 탐색해서 그 페이지로부터 레코드를 삭제한 후, 수정된 페이지를 다시 기록해야한다.
  • 따라서 삭제비용은 삽입과 마찬가지로 탐색비용 +BD가 된다.

Hash File

간단한 hash file 구조로도 탐색 키 필드가 주어진 값과 같은 레코드를 신속하게 찾을 수 있다.
예를 들면 파일이 name 필드에 대해서 hash가 되어있는 경우에 ‘joe라는 이름의 학생 레코드를 찾아라’ 같은 검색이 이에 해당한다.
Hash file을 구성하는 페이지들은 버켓(bucket) 단위로 묶인다.
버켓 번호가 하나 주어지면 그 bucket에 해당하는 기본 페이지를 찾을 수 있는 것이 hash file 구조이다.
레코드가 속하게 될 버켓은 탐색 필드에 hash 함수(hash function) 라는 특수한 함수를 적용해서 결정한다.
삽입할 때엔 레코드를 알맞은 버켓에 삽입시키는데, 필요 시 버켓에 overflow page를 추가로 연결한다.
각 버켓에 붙는 overflow page들은 하나의 연결 리스트로 유지된다.
주어진 탐색 키 값으로 레코드를 검색할 때에는 hash 함수를 적용시켜 레코드의 버켓을 알아낸 후 그 버켓에 속한 모든 페이지를 살펴본다.
이러한 조직법을 정적 해쉬 파일(static hashed file) 이라고 한다.
이 조직법의 단점은 overflow page의 리스트가 길어질 수 있다는 것이다.
그래서 이 문제를 해결한 동적 해쉬 파일(dynamic hash file)이란 것이 있다.

• Scan:
  • Hash file에서는 페이지를 보통 80% 차도록 유지한다. (overflow의 페이지 수를 최소화 하기 위해)
  • 그래서 페이지 수와, 데이터 페이지의 탐색비용은 heap file의 1.25배(=100/80)가 되어서 1.25BD 가 된다.
• Equality:
  • selection 조건이 hash file의 탐색 키에 대한 것이라면 연산이 매우 효율적이다. (그렇지 않으면 파일 전체를 검사해야한다.)
  • 부합하는 레코드 들이 있는 페이지를 검색하는 비용은 D가되어 총 비용은 D가 된다.
• Range:
  • Hash file 구조는 이 연산에 전혀 도움이 되지 못한다.
  • 무조건 파일 전체를 검사해야 하므로, 비용은 1.25BD 이다.
• Insert:
  • 적절한 페이지를 찾아서 수정한 후 다시 기록해야 한다.
  • 따라서 비용은 탐색비용 + D 가 된다.
• Delete:
  • 레코드를 찾아서 페이지로 부터 제거한 후, 수정한 페이지를 기록해야 하므로 비용은 탐색비용 + D 가 된다.

결론

• Heap File
  • 저장 성능이 우수하고 Sacn, Insert, Delete가 빠르지만, 탐색이 느리다.
• Sorted File
  • Insert, Delete가 느리지만 탐색은 대단히 빠르고, Range Selection에 좋다.
  • 하지만 실제 DBMS에선 파일을 완전히 정렬된 형태로 계속 유지하는 경우는 거의 없으므로 이 조직법은 소용이 없다.
  • B+ Tree 라는 구조는 Sorted File의 장점을 그대로 모두 가지면서 삽입, 삭제를 효율적으로 수행해 줄 수 있다.
• Hash File
  • 공간을 잘 활용하지는 못하지만 삽입, 삭제가 빠르며, Equality Search가 매우 빠르다.
    
• 이처럼 어느 상황에 항상 좋은 파일 구조란 없기 때문에, 적절한 상황에 적절한 파일 구조를 사용해야 한다.