6. Ubiquitous B-Tree

지난 글에서 정리했듯 BST 는 on-disk 자료구조로는 적합하지 않았다.

그래서 BST 를 기반으로 fanout 이 크고 트리의 높이도 더 작은 B-Tree 라는 자료구조가 등장했다.

이번 글에서는 제일 기본적인 B-Tree 에 대해 정리해본다.

 

B-Tree 를 그림으로 표현하면 아래와 같이 표현할 수 있다.

 

 

또는 책에 따라서 아래와 같이 표현하기도 한다.

 

 

B-Tree 내부 각 노드가 보유한 key 값들은 일정한 순서로 정렬되어 있다.

(위 그림의 경우라면 key1 < key2 < key3 으로 정렬되어 있다.)

따라서 하나의 노드 안에서 특정 키를 찾을 때는 이분 탐색을 사용하여 원하는 키를 찾을 수 있다.

 

꼭 노드 내부가 아니더라도, B-Tree 의 데이터 탐색 시간복잡도는 로그 시간복잡도를 갖는다.

예를 들어 40억개 데이터 중에서 원하는 데이터를 찾는데 필요한 비교 횟수는 대략 32번 정도가 필요하다.

만약 매 비교를 진행할 때마다 디스크를 탐색해야 한다면, 탐색 속도가 매우 느려지겠지만, B-Tree 는 key 값들을 묶어서 저장하고 있기 때문에 탐색하는 트리의 level 이 바뀔 때만 디스크를 탐색하면 된다.

 

또한 B-Tree 는 점 질의(point query, = 조건)와 범위 질의(range query, < > ≤ ≥ 조건) 모두에 대해 효율적으로 데이터를 조회할 수 있다.

 

B-Tree 의 구조

B-Tree 의 각 노드는 최대 N 개의 key 를 갖고 있고, N+1 개의 포인터를 갖고 있다.

그리고 각 노드들은 다음 3가지 종류 중 하나로 분류할 수 있다.

 

1. 루트 노드 : 부모가 없는, 트리의 꼭대기 노드

2. 리프 토드 : 자식이 없는, 트리의 밑바닥 노드

3. 내부 노드 : 1, 2 번 종류 이외의 노드로, 리프 노드와 루트 노드를 연결하는 노드

 

 

B-Tree 는 고정된 크기의 페이지를 구성하는 기법이기 때문에, B-Tree 의 node 와 page 는 같은 의미로 이해할 수 있다.

각 노드의 최대 용량과 실제로 저장하고 있는 키의 개수 사이의 관계를 가리켜 occupancy (점유) 라고 한다.

 

B-Tree 는 각 노드에 저장된 키의 숫자를 가리키는 fanout 수에 따라 특성이 결정된다.

fanout 값이 클수록 tree 밸런스를 유지하기 위한 작업 비용이 줄어들고, 키와 포인터를 정렬할 때 디스크를 탐색하는 횟수가 줄어든다.

그리고 밸런스를 유지하는 과정에서 수행하는 작업 (merge, split) 은 어떤 노드가 거의 비어있거나 가득 찼을 때 수행된다.

 

구분 키

B-Tree 에 저장된 키 값들은 index entry, separator key, divider cell 등의 이름으로 부른다.

(인덱스 파일에 저장된 레코드 하나하나를 가리켜 index entry 라고 부른다고 했던 것과 동일한 개념)

각각의 키값들은 트리를 서브트리로 쪼개며, 각 포인터가 가리키는 서브트리는 그 키 값이 가리키는 범위의 값들을 갖고 있다.

 

 

예를 들어 위와 같이 노드가 구성되어 있고, P1, P2, P3, P4 가 가리키는 서브트리 내 값을 v1, v2, v3, v4 라고 해보자.

 

v1 < 3 

3 <= v2 < 8

8 <= v3 < 13

13 <= v4

 

가 성립한다.

즉, i 번째 포인터가 가리키는 트리에 저장된 모든 값 v는 i-1 번째 키 값 ≤ v < i 번째 키 값 을 만족한다.

 

B-Tree 는 여러가지 변형된 형태가 존재한다.

어떤 B-Tree 변형 버전에서는 부모 노드에 대한 포인터에 더해 형제 노드와 연결되는 포인터를 갖고 있기도 하다.

이 경우, 대부분 리프노드에서 형제 노드에 대한 포인터를 갖고 있어, 범위 스캔을 효율적으로 수행할 수 있다.

(즉, 형제 노드를 찾기 위해 다시 부모부터 탐색할 필요가 없어진다.)

이 형제 노드에 대한 포인터는 양방향으로 만들어 역순으로 데이터를 조회할 때도 효율적으로 조회하도록 구현할 수도 있다.

 

B-Tree 는 키를 구성하는 방법에서도 BST 와 구분되는데, B-Tree 는 자료구조를 구성할 때 Bottom-Up 방식으로 구성한다.

BST 를 구성할 때는 루트노드부터 시작해서 데이터를 추가할 때마다 좌/우 중 어디에 저장할 지 결정하여 추가하는 Top-Down 방식으로 저장하지만, B-Tree 를 구성할 때는 leaf node 를 먼저 설정하고, 이로부터 internal node 와 root node 가 결정된다.

따라서 leaf node 수가 증가하면, internal node 수와 트리 높이가 증가하게 된다.

 

또한 B-Tree 는 추후 삽입/수정될 데이터를 위해 여유 공간을 남겨두기 때문에, 트리의 점유율이 50%까지 낮아지기도 한다.

하지만 일반적으로는 그보다 높은 점유율로 유지되고, 점유율이 높다고 해서 B-Tree 성능에 안 좋은 영향을 끼치지는 않는다.

 

키의 개수

교과서마다 하나의 노드가 가질 수 있는 키와 자식 포인터 개수를 설명하는 방식이 조금씩 다르다.

 

어떤 교과서에서는 각 장치에 맞게 설정되는, 최적의 페이지 크기를 나타내는 자연수 k 를 상정한다.

(데이터베이스 수업에서는 이 k 를 가리켜 '차수(degree)' 라고 말했다.

그리고 이 값이 '장치에 맞게 설정된다' 는 것은 그 장치가 한번에 읽고 쓰는 블록의 크기에 맞게 설정되는 값임을 유추할 수 있다.)

 

각 노드가 가질 수 있는 최대 키의 개수는 2k 이며, 루트 노드를 제외한 모든 노드는 그 안에 k개 이상의 키를 가져야 한다.

(그렇다면 자식 포인터의 개수는 최소 k+1 개부터 최대 2k + 1 개까지 가질 수 있다)

루트 노드의 경우에는 1 ~ 2k 개의 키를 가질 수 있다.

맨 처음 키가 들어왔을 때는 당연히 1개 밖에 데이터가 존재하지 않기 때문에 k 개 이상을 가진다는 조건을 만족할 수 없기 때문이다.

또한 l 이라는 값을 추가로 상정하고, 리프노드가 아닌 노드는 l + 1 개의 키를 가질 수 있다고도 설명한다.

 

다른 교과서에서는 노드가 최대 N 개의 구분 키와 N+1 개의 포인터를 가질 수 있다고만 말하며, 최솟값에는 제한을 두지 않기도 한다. 두 가지 설명 방법 모두 결국엔 구분키가 최대 N 개일 때, 포인터는 최대 N+1 개 가질 수 있다는 설명을 하는 점에서는 비슷하다.

(실제로도 키의 개수가 절반 이상 들어있어야 한다고 딱 정하기보다는, 물리 공간 기준으로 절반 이상 차있어야 한다고 느슨하게 정의한다. 하나의 키 값에 들어있는 데이터 길이가 가변적인 경우도 있기 때문)

 

조회 연산

B-Tree 의 조회 연산을 수행하는 알고리즘과 그 복잡도를 정리해보자.

B-Tree 의 조회 연산은 root 로부터 특정 leaf node 까지 일련의 경로를 따라가는 과정이다.

그리고 이 조회의 목적은 하나의 search key 를 찾거나 그 search key 의 predecessor 를 찾는 것이다.

 

하나의 특정 search key 를 찾는 것은 점 질의 (point query) 를 처리할 때,

search key 의 predecessor 를 찾는 것은 범위 스캔, 데이터 삽입을 처리할 때 사용된다.

(search key 의 predecessor 를 찾는다는 것은 해당 search key 가 들어갈 수 있는 위치를 찾는 것)

 

조회 연산은 루트 노드에서 이분 탐색을 하는 것으로 시작한다.

 

 

예를 들어 5 라는 값을 찾는 과정을 따라가보자.

먼저 루트 노드에 들어있는 <13, 17, 24, 30> 안에서 이분 탐색을 통해 5 라는 값보다 큰 첫 번째 seperator key 를 찾는다.

(즉, upper bound 를 찾는다)

그러면 13 이라는 키를 찾게 된다.

 

이제 5를 13과 비교해서 왼쪽 / 오른쪽 포인터 중 어떤 포인터를 따라갈지 결정한다.

왼쪽 포인터는 13 미만의 수를, 오른쪽 포인터는 13 이상 17 미만의 수를 저장하는 노드를 가리킨다.

따라서 5를 찾기 위해 왼쪽 포인터를 따라간다.

 

위 그림은 B+Tree 의 구조도로, B+Tree 의 리프 노드는 실제 데이터를 갖고 있기 때문에 (data entry) 각 값 사이의 포인터는 존재하지 않는다.

리프 노드 내에서 다시 5에 대해 이분 탐색을 진행하면 우리는 5라는 값을 찾을 수 있다.

 

만약 점 질의를 처리하고 있었다면 5라는 값의 존재 여부로 질의 결과를 확인할 수 있고,

만약 범위 스캔을 처리하고 있었다면 5라는 범위의 경계값에서 제일 가까운 값을 찾은 뒤, 형제 노드 포인터를 따라 범위 끝에 도달할 때까지 값을 순차적으로 읽으면 된다.

 

정리하면 조회 연산의 처리 과정은 '이분 탐색 → 포인터 따라가기' 를 리프노드에 도착할 때까지 반복하는 것으로 이해할 수 있다.

이렇게 루트에서부터 트리를 따라 내려가면 점점 탐색 범위를 줄여나가면서 우리가 원하는 값을 찾을 수 있다.

 

---

 

 

다음으로 B-Tree 조회시 연산의 복잡도를 살펴보자.

조회 연산의 처리과정이 '이분 탐색' 과 '포인터 따라가기' 로 구분되었기 때문에, 그 복잡도 역시 2가지 관점에서 살펴볼 수 있다.

 

1. 디스크로부터 읽고 쓰는 (전달하는) 블록의 개수 (포인터 따라가기)

2. 조회과정에서 수행되는 비교 횟수 (이분 탐색)

 

전달되는 블록의 개수 관점

하나의 노드에 저장되는 키의 최대 개수를 N

새로운 레벨이 만들어질 때, 이전 레벨보다 증가하는 노드의 배수를 K배 (=하나의 노드에 대한 포인터의 개수 = N+1)

B-Tree 에 저장된 모든 데이터의 개수를 M이라고 하자.

 

그러면 자식 노드 포인터를 따라갈 때마다 탐색 공간의 크기가 N 배씩 줄어든다.

(N개의 키 중에서 1개를 선택하는 과정을 반복하므로)

그리고 루트노드부터 리프노드까지 도달하는 과정에서 경유하는 자식 포인터의 개수는 트리의 높이 h 와 같다.

 

따라서 B-Tree 에서 하나의 값을 조회할 때 디스크에서 읽어오는 페이지의 수는 log_k M (=트리의 높이) 이다.

(상술했듯 B-Tree 는 고정된 크기의 페이지를 구성하는 방법이므로 하나의 노드 = 하나의 페이지로 본다.)

 

비교 횟수 관점

다음으로 이렇게 디스크로부터 읽어들인 하나의 노드에서 조건에 맞는 탐색 키를 찾기 위해서 이분탐색을 수행한다.

그리고 이분 탐색에서의 비교 횟수는 log_2 기반으로 표현할 수 있으므로 비교 횟수 관점의 복잡도는 log_2 M 으로 표현할 수 있다.

 

이렇게 조회 연산의 복잡도와 B-Tree 의 조회 동작 과정을 이해할 때는 '디스크를 탐색하는 횟수'와 '비교 횟수'를 구분하는 것이 좋다.

그리고 이 두 관점을 고려하면 B-Tree의 조회 복잡도를 일반적으로 log M 으로 표기한다.

(big-O 에서 로그의 밑은 상수값으로서 생략할 수 있다.)

 

 

삽입 연산 (노드 분할)

B-Tree 에 새로운 데이터를 삽입하려면, 먼저 해당 데이터가 삽입될 리프 노드와 위치를 찾아야 하므로 조회연산을 먼저 수행한다.

그리고 그렇게 발견한 위치에 key-value 값을 삽입한 뒤, 기존의 key 와 새로 추가된 값을 연결한다.

 

그런데 데이터를 삽입하려는 노드에 여유 공간이 충분하지 않을 수 있다.

이런 상황을 가리켜 해당 노드가 overflow 되었다고 표현하며, 이 경우 해당 노드를 2개로 쪼개서 쪼개진 조각에 새로운 데이터를 저장한다.

 

구체적으로는 리프노드와 비리프노드를 구분하여 다음과 같은 상황에서 분할이 발생한다.

 

- 리프노드

노드가 최대 N 개의 key-value 를 저장할 수 있다고 할 때,

노드에 N개의 데이터가 꽉 찬 상태에서 새로운 데이터를 이 노드에 저장하려는 경우

 

- 비-리프노드

노드가 N+1 개의 포인터를 저장할 수 있을 때,

노드의 N+1 개의 포인터가 꽉 찬 상태에서 새로운 포인터를 이 노드에 저장하려는 경우

 

즉, 리프노드에서는 데이터를 기준으로, 비-리프노드에서는 포인터를 기준으로 분할한다.

 

노드의 분할 및 삽입 과정은 다음과 같다.

 

1. 새로운 노드를 생성한다.

2. 분할하려는 노드의 데이터 중 절반을 새로운 노드에 이동하여 저장한다.

3. 쪼개진 2개 노드 중 적절한 노드에 데이터를 삽입한다.

4. 새로운 노드의 첫 번째 키 값과, 새로운 노드에 대한 포인터를 부모 노드에 추가한다.

 

이런 상황을 가리켜 '키가 승격되었다' 고 표현하며, (말 그대로 키를 위로 올려보내기 때문)

노드가 분할되는 위치(index)를 가리켜 split point 또는 midpoint 라고 부른다.

 

만약 부모 노드도 가득 차서 새롭게 생성된 노드의 키와 포인터를 저장할 수 없다면 부모 노드 역시 분할 과정을 수행한다.

따라서 분할 작업은 루트 노드를 향해 재귀적으로 전파되기도 한다.

 

만약 루트 노드도 가득 찼다면 (즉, 트리의 capacity 가 가득찼다면) 루트 노드를 분할 해야 한다.

루트 노드를 분할할 때는 새로운 split point 에 해당하는 키 값 하나를 갖는 새로운 루트 노드를 만들고, 이전 루트 노드는 둘로 쪼개져 형제 노드와 함께 새로운 로트 노드의 다음 level 노드에 속하게 된다.

 

이렇게 B-Tree 의 높이는 루트 노드가 쪼개지거나 두 노드가 하나의 루트 노드로 병합될 때만 변하고,

내부 노드나 리프 노드에서의 분할/병합은 트리의 높이에는 영향을 주지 않고, 수평 넓이에만 영향을 준다.

 

 

구체적인 예시를 위해 위와 같은 B-Tree 에 8을 추가하는 과정을 살펴보자.

먼저 8이 추가될 리프 노드를 찾기 위해 조회 연산을 수행한다.

그런데 리프노드가 가득 차서 새로운 데이터를 삽입할 수 없는 상태이다.

 

 

따라서 기존 노드를 분할하기 위해, 새로운 노드를 만들고, 기존 노드의 데이터 절반을 새로운 노드로 옮긴다.

이때 분할하는 과정은 새로 추가할 노드를 포함하여 정렬시킨 뒤, 그 기준으로 절반을 자르면 된다.

위 경우, <2, 3, 5, 7> 에 8을 추가하면 <2, 3, 5, 7, 8> 이 되며, 이를 가운데 5를 기준으로 쪼개면

<2, 3> 과 <5, 7, 8> 로 쪼갤 수 있다.

 

이제 새롭게 만들어진 노드의 첫번째 키 값인 5를 부모 노드에 복사해서 포인터를 저장해야 한다.

(리프 노드에서 분할하는 경우, 그 값은 데이터 엔트리이므로 부모노드에 '복사해서' 저장한다.)

 

그런데 부모 노드 역시 가득찬 상태이므로 부모 노드도 분할해야 한다.

부모 노드를 분할할 때도 데이터를 추가하여 정렬한 값을 기준으로 분할한다.

위 상황의 경우, <13, 17 ,24, 30> 이라는 키 값에 <5> 라는 키를 추가하면 <5, 13, 17, 24 ,30> 이 되며, 이를 분할하면

<5, 13> 17 <24, 30> 으로 분할할 수 있다.

 

리프노드가 아닌 경우, 분할시 중간값은 상위 노드로 이동해서 올려보내야 한다. (리프노드와 달리 '복사' 가 아니다)

그런데 지금 분할하는 노드는 루트 노드로서 상위노드가 없기 때문에 새로운 루트 노드를 만들어서 분할해야 한다.

 

 

따라서 최종적으로 위와 같이 분할된다.

 

 

 

삽입 방법의 변형으로는 노드를 분할하기 전에 '재분배' 를 통한 삽입이 가능한지 확인하는 방법도 있다.

이 방법은 내가 삽입될 노드에 공간이 없을 경우, 그 형제 노드를 살펴보고 형제 노드에 공간이 남아있다면 형제 노드에 삽입하고 키 값을 변경한다.

 

위 예시에서 8이 삽입될 노드에 <2, 3, 5, 7> 이 가득 차있으므로 원래는 분할을 해야 하지만,

옆의 형제노드의 경우, <14, 16> 으로 공간이 남아있기 때문에, 8을 형제 노드에 삽입하고 해당 노드의 부모 키값을 변경해주면

 

 

 

이렇게 데이터를 삽입할 수 있다.

그리고 재분배 방식으로 삽입하면 B-Tree 의 공간 점유율을 높게 유지할 수 있으므로 (=트리의 높이를 낮출 수 있으므로) 조회시 성능상 이점이 더 좋다. (단말 노드의 경우)

 

이때 재분배 가능성을 점검하는 것은 내 좌우 형제 노드(페이지)의 데이터를 읽어야 한다는 것을 의미하므로, 삽입 작업의 성능에 악영향을 주는 단점이 있으며, 분할 작업이 루트 노드로 전파되고 있는 상황에서 재분배를 점검하는 작업으로 입출력이 줄어들 가능성은 낮기 때문에 비단말 노드라면 재분배를 통한 삽입은 하지 않는 편이 더 낫다.

 

 

삭제 연산 (노드 병합)

삭제 연산 역시 먼저 삭제할 데이터의 위치를 찾는 것부터 시작하므로 조회 연산이 먼저 진행된다.

만약 데이터를 삭제한 후에 자신과 형제 노드에 들어있는 데이터들이 너무 조금 남아있다면

(즉, 점유율이 일정 기준값 (degree) 밑이라면) 자신과 형제노드를 하나의 노드로 병합한다.

 

이 상황을 가리켜 underflow 라고 부르며, underflow 에는 크게 2가지 시나리오가 있다.

 

 

1. 같은 부모 노드를 공유하는 두 인접 노드의 데이터 개수가 하나의 노드에 모두 들어갈 수 있는 개수라면, 두 노드는 병합되어야 한다.

 

 

2. 같은 부모 노드를 공유하는 두 인접 노드의 데이터 개수가 하나의 노드에 모두 들어갈 수 없다면, 두 노드가 보유한 키의 개수가 균형이 맞게 재분배되어야 한다.

이를 가리켜 리밸런싱이라고 부르며, 리밸런싱을 통해 분할과 병합 연산의 발생 횟수를 줄일 수 있다.

 

 

다시 노드 병합으로 돌아오면, 노드 병합은 다음과 같이 2가지 상황에서 발생한다.

 

- 리프 노드의 경우

노드 하나가 최대 N개의 키-값 쌍을 가질 수 있을 때, 두 이웃 노드의 키-값 쌍 개수 합이 N개 이하라면 하나로 병합한다.

 

- 비-리프 노드의 경우

노드 하나가 최대 N+1 개의 포인터를 가질 수 있을 대, 두 이웃 노드의 포인터 개수 합이 N+1개 이하라면 하나로 병합한다.

 

 

노드의 삭제 및 병합 과정은 다음과 같은 순서로 이루어진다.

 

1. 삭제하려는 값을 찾아 노드에서 제거한다.

2. 해당 노드의 오른쪽 이웃 노드의 모든 데이터를 왼쪽으로 복사해온다.

3. 부모 노드에서 오른쪽 이웃 노드의 포인터를 제거한다.

4. 오른쪽 이웃 노드를 제거한다.

 

그리고 삭제 과정 역시 루트를 향해 전파될 수 있다.

구체적인 예시를 통해 살펴보자.

 

 

 

이 트리에서 8을 삭제해보자.

만약 모든 노드의 키값이 절반 이상 차있어야 한다는 제약이 있다면 아직은 병합하지 않아도 된다.

하지만 위에서 기술한 병합 조건상, 리프 노드에서는 두 이웃 노드를 합쳤을 때 그 개수가 N 개 이하가 된다는 병합 조건을 만족하므로 병합을 해보자.

 

 

만약 병합을 한다고 해보면, 위 알고리즘을 따라 오른쪽 형제 노드 <14, 16> 의 데이터를 왼쪽으로 복사하고 형제 노드의 포인터를 부모노드에서 제거한다.

 

 

 

그런데 비-리프 노드인 13은 오른쪽 포인터가 없으므로 더 이상 필요하지 않은 값이다.

따라서 13을 제거한다.

(참고로 위에서 <5, 13> 과 <24, 30> 을 병합하지 못하는 이유는 '포인터' 의 개수가 5개를 넘기 때문이다. 비-리프 노드에서는 포인 터 개수가 병합의 조건인 이유)

 

 

그런데 이제 비단말 노드인 <5> 와 <24, 30> 도 병합할 수 있게 되었다.

비단말 노드를 병합할 때는 키 값보다 '포인터' 를 고려해야 한다.

위에서 왼쪽 비단말 노드에는 <5> 라는 값 1개와 포인터 2개가 존재하고

오른쪽 비단말 노드에는 <24, 30> 이라는 값 2개와 포인터 3개가 존재한다.

즉, 값은 3개 포인터는 5개인 상태이다.

 

따라서 각각의 포인터 사이사이에 값을 껴주기 위해서 병합하려는 두 노드의 공통 부모를 밑으로 가져와야 한다.

(이를 가리켜 demote 라고  표현한다. promote 의 반대 과정인 것)

 

따라서 부모 노드인 <17> 의 포인터를 버리고, 아래로 가져와 병합하면 다음과 같이 병합된다.

 

 

이 과정을 수행한 결과는 위와 같다.

그리고 루트 노드가 텅 비었으므로 루트 노드를 삭제해주면, 트리의 높이가 하나 줄어든다.

또한 전체 트리의 관점에서 포인터의 개수는 매 레벨마다 하나씩 줄어드는데, 삭제가 전파되는 것은 포인터의 삭제가 전파되는 것과 같기 때문이다.

 

---

지금까지 B-Tree 의 등장 배경과 기본적인 구조 및 연산 알고리즘에 대해 정리하였다.

 

BST 는 B-Tree 와 비슷하지만 disk 라는 저장매체에서 활용하기에는 적합하지 않았다.

fanout 이 작기 때문에 트리의 균형을 맞추는 작업이 자주 발생하고, 트리의 높이가 커서 하나의 값을 찾기 위한 경로가 길어 디스크 입출력이 자주 발생하기 때문이다.

B-Tree 는 이 문제를 해결하기 위해 하나의 노드에 저장되는 데이터의 개수를 늘려서 (high fanout), 균형을 맞추는 merge, split 연연산의 발생 빈도를 낮추었다.

 

다음으로 B-Tree 구조와 조회/삽입/삭제 알고리즘의 큰 개요를 살펴보면서 어떻게 split , merge 연산으로 삽입 / 삭제 연산 후 트리의 균형을 유지하는지 살펴보았다.

이와 같은 균형 유지 알고리즘으로 인해 트리의 높이를 최소화하면서 빈 공간에 데이터를 추가할 수 있었다.

 

하지만 지금까지의 지식만으로는 메모리를 넘는 disk 기반의 자료구조를 만들 수 없다.

B-Tree 를 disk 에서 사용하려면 B-Tree 의 각각의 노드가 어떻게 디스크에 배열되어 저장되고, 이 배열을 어떤 data encodeing 포맷으로 변환하여 압축할 것인지 공부할 필요가 있다.

 

따라서 다음 글부터는 디스크에 데이터를 저장하는 방식인 파일 포맷에 대해 자세히 정리해본다.