파일처리 ch1) 파일 구조 설계와 명세 소개

디스크는 왜 느릴까??

 

RAM vs 디스크 속도 비교!

 - RAM : 약 120ns

 - 디스크 : 약 30ms

 

=> 이를 비유하면, RAM의 1초 = 디스크의 2일 22시간

But, 디스크는 저렴하고 비휘발성이라 대용량 저장에 유리

 

추가 설명) 디스크는 저장 공간이 크고 가격도 저렴하지만, 접근 속도는 RAM에 비해 매우 느립니다.

                 파일 구조 설계는 이런 속도 차이를 극복하고 최적의 데이터 접근을 가능하게 하는 기술입니다.

                 (최대한 빠르게 원하는 정보를 얻기 위한 전략)

 

파일 구조 설계가 왜 필요한가???

1. 파일(FILE)이란 ? 

 - 하드 디스크 , 솔리드 스테이트 디스크, CD, 테이프 등과 같은 보조 기억 장치에 저장된 동일 종류의 레코드 집합

 

2. 파일 구조(FILE structure)이란 ?

 - 파일에 저장된 데이터의 표현 방식과 데이터를 접근하기 위한 연산들의 조합

   (데이터가 파일에 어떻게 표현되고 저장되는지와 그 데이터를 효율적으로 접근할 수 있는 방법들이 결합된 구조를 의미)

 

3. 좋은 설계의 목표 

 -> 가능한 적은 비용(특히 디스크 접근 횟수)으로 데이터를 읽는 것

 

초기 파일 구조 

1. Sequential access(순차 접근)

 - Tape 기반 구조 (데이터를 처음부터 순서대로 접근)

 - 순차적인 접근만 가능(Sequental access)

sequential의 예시

 

2. Simple index(인덱스 기반 접근)

 

 - 디스크 드라이브와 같은 저장 장치가 등장하면서 생김

 - Index File로 키와 포인터를 저장하는 방식

 - 문제점 :  특히 동적 파일(즉, 자주 변하는 파일)을 관리하는데 어려움이 있음

simple index 예시

 

ex) Gildong Hong | 1 (키 | 포인터)

      Data File 안에는 실제 데이터가 포함되어있음(인덱스 파일의 포인터가 가리키는 실제 레코드가 포함되어 있음)

 

3. Binary Tree(이진 트리)

 

 - 초기 형태의 트리 구조

 - 삽입/삭제 시 비균형 문제가 발생

 

비균형의 예시

 

4. AVL Tree

 - 이진 트리의 단점을 보완

 - 균형 조건 : 어느 노드에서든 좌우 subtree의 높이 차이가 1이하

 => 삽입/삭제 시 균형 유지 연산이 필요하지만, 데이터 접근 성능은 훨씬 안정적

AVL 트리 예시

 

 

5. Balanced Binary Tree

 - 주어진 n개의 키 -> 약 log2(n) + 1 높이의 트리

 - 예시 : 트리를 균형 있게 구성하여 탐색 최적화

Balanced Binary Tree 예

 

6. B-Tree, B+Tree, Hashing, Extendible Hashing

 

1. B- Tree (데이터를 빠르게 접근할 수 있도록 설계된 트리 구조)

•  이진 트리와 다르게, 각 노드에서 자식 노드의 수가 두 개 이상일 수 있음
•  디스크 기반 데이터 저장 시 효율적으로 사용됨

 

2. B+ Tree (B- tree 구조의 변형)

• 순차 접근과 빠른 인덱스 접근을 모두 제공
• 데이터가 리프 노드에만 저장되어, 순차적 검색이 용이

 

3. Hashing (검색 키를 저장 주소로 변환하여 데이터를 빠르게 접근하는 방법)

• 해시 값을 사용해 데이터를 빠르게 찾아낼 수 있음
• 빠른 데이터 접근을 가능하게 하지만 충돌 처리가 필요

 

4. Extendible Hashing (해싱 방식 중 하나로, 동적 파일에 적합한 해시 방식)

• 기존의 해싱 방식은 동적 파일에 적합하지 않음
• 확장 가능한 해싱은 파일 크기에 관계없이 최대 두 번의 디스크 접근만으로 정보를 검색할 수 있음