🟣 왜 디스크를 먼저 이해해야 하나
자료구조 수업에서는 배열 접근이든 리스트 접근이든 비용을 대체로 같게 놓고 시작한다. 메모리 안에서는 그 가정이 통한다. 그런데 데이터가 수백만 건이 되면 이야기가 달라진다. 메인 메모리는 빠르지만 용량이 작고, 전원이 꺼지면 사라진다. 은행 계좌나 회원 정보처럼 영구히 남아야 하는 데이터는 결국 디스크 같은 보조기억장치로 내려가야 한다.
문제는 디스크가 메모리보다 압도적으로 느리다는 데 있다. 메모리 접근이 나노초 단위라면 전통적인 하드디스크 접근은 밀리초 단위다. 수만 배의 격차다. 이 격차 때문에 파일 처리에서는 "연산을 몇 번 했나"보다 "디스크에 몇 번 손을 댔나"가 성능을 결정한다. 뒤에 나올 모든 트리 구조가 이 한 문장에서 출발한다. 그래서 먼저 디스크가 왜 느린지를 봐야 한다.
🟣 디스크는 왜 느린가: 접근 시간의 구조
하드디스크는 회전하는 원판(플래터) 위를 읽기·쓰기 헤드가 오가며 데이터를 읽는다. 원판은 동심원인 트랙으로 나뉘고, 트랙은 다시 섹터로 쪼개진다. 특정 데이터를 읽으려면 세 가지 일이 순서대로 일어난다.
먼저 헤드를 목표 트랙 위로 옮긴다. 이 시간이 탐색 시간(seek time)이다. 다음으로 원판이 돌아 목표 섹터가 헤드 밑에 올 때까지 기다린다. 이것이 회전 지연(rotational latency)이다. 마지막으로 데이터를 실제로 읽어 내는 전송 시간(transfer time)이 붙는다. 디스크 접근 시간은 이 셋의 합이다.
이 중에서 앞의 둘, 특히 탐색 시간이 지배적이다. 헤드라는 물리적인 팔을 움직이는 기계 동작이기 때문이다. 반면 일단 헤드가 자리를 잡은 뒤 연속된 데이터를 쭉 읽는 전송은 상대적으로 싸다. 여기서 파일 처리의 첫 번째 교훈이 나온다. 한 번 자리를 잡았으면 최대한 많이 읽어 오는 편이 이득이다. 띄엄띄엄 여러 번 접근하면 그때마다 비싼 탐색 시간을 다시 낸다.
SSD로 오면 회전하는 원판이 없어 탐색 시간과 회전 지연이 사라진다. 그래서 임의 접근이 훨씬 빨라진다. 다만 SSD도 읽기·쓰기의 최소 단위가 블록(페이지)이라는 성질은 그대로다. "한 번에 블록 단위로 다룬다"는 원칙은 저장 매체가 바뀌어도 유지된다.
🟣 블록: 디스크 입출력의 최소 단위
방금의 교훈을 구조로 옮긴 것이 블록이다. 디스크는 레코드 하나를 낱개로 읽지 않는다. 여러 레코드를 하나의 블록으로 묶어, 블록 단위로 통째로 읽고 쓴다. 블록 하나에 레코드가 몇 개 들어가는지를 블로킹 인수(blocking factor)라고 부른다.
블록이 왜 중요한지는 탐색 비용과 함께 봐야 한다. 레코드 하나를 읽으려고 디스크에 한 번 접근하나, 같은 블록 안의 레코드 100개를 읽으려고 한 번 접근하나 드는 탐색 시간은 같다. 그러니 자주 함께 쓰이는 레코드를 한 블록에 몰아 두면 접근 횟수가 줄어든다. 뒤에 나올 B트리가 "노드 하나를 블록 하나에 딱 맞춘다"는 발상도 정확히 여기서 나온다. 파일 처리에서 비용을 셀 때는 언제나 연산 횟수가 아니라 블록 접근 횟수로 센다.
🟣 순차 파일: 정렬해 두면 얻는 것과 잃는 것
가장 단순한 파일 구성은 레코드를 키 순서로 정렬해 차례로 쌓는 순차 파일이다. 학번 순으로 정렬된 학생 파일을 떠올리면 된다. 이렇게 정렬해 두면 두 가지를 얻는다.
첫째, 전체를 순서대로 훑는 작업이 빠르다. 블록을 앞에서부터 연속으로 읽으면 되니 비싼 탐색이 거의 없다. 정렬된 순서로 리포트를 출력하거나 전체를 일괄 처리하는 작업에 잘 맞는다. 둘째, 정렬돼 있으므로 특정 키를 찾을 때 이진 탐색을 쓸 수 있다. 블록 단위로 이진 탐색을 하면 대략 log₂(블록 수)번의 접근으로 원하는 레코드에 닿는다. 순차 탐색의 선형 비용보다 훨씬 낫다.
문제는 삽입과 삭제다. 순차 파일은 키 순서를 지켜야 하므로, 중간에 새 레코드를 하나 끼워 넣으려면 뒤의 레코드를 전부 한 칸씩 밀어야 한다. 백만 건 사이에 하나를 끼우자고 수십만 건을 다시 쓰는 셈이다. 삭제도 빈자리를 메우느라 비슷한 비용이 든다. 이 문제를 피하려고 실무에서는 삽입을 별도의 오버플로 영역에 쌓아 두고 나중에 한꺼번에 재정리(reorganization)하지만, 오버플로가 쌓일수록 탐색은 다시 느려진다.
여기서 방향이 갈린다. 자주 바뀌는 데이터를 정렬 상태로 유지하려면, 순차 파일의 재정렬 비용 없이 삽입·삭제·탐색을 모두 값싸게 하는 구조가 필요하다. 데이터 본문은 순차 파일에 두더라도, "어디에 있는지"를 가리키는 별도의 색인, 즉 인덱스를 두는 발상이 여기서 나온다. 그리고 그 인덱스를 담는 자료구조로 트리가 등장한다.
🟣 정리
- 파일 처리의 비용은 연산 횟수가 아니라 디스크 접근 횟수로 센다. 디스크가 메모리보다 수만 배 느리기 때문이다.
- 디스크 접근 시간은 탐색 시간, 회전 지연, 전송 시간의 합이고, 헤드를 움직이는 탐색 시간이 지배적이다. 그래서 한 번 자리 잡았을 때 많이 읽는 편이 이득이다.
- 디스크 입출력의 단위는 레코드가 아니라 블록이다. 자주 함께 쓰는 레코드를 한 블록에 몰면 접근 횟수가 준다.
- 순차 파일은 정렬 덕에 순회와 이진 탐색이 빠르지만, 중간 삽입·삭제가 뒤 레코드를 밀어내는 비싼 작업이라는 약점이 있다.
- 이 약점이 인덱스와 트리 구조의 출발점이다.
면접에서 "인덱스를 왜 쓰냐"는 질문에 "빨라서요"로 답하면 절반만 맞다. 디스크 접근 횟수를 줄이려고 쓴다는 관점, 그리고 인덱스가 삽입·삭제 비용과 탐색 속도 사이의 트레이드오프라는 관점까지 짚어야 이 장을 이해한 것이다.
다음 장에서는 그 인덱스를 담는 첫 자료구조인 이진 탐색 트리를 본다. 삽입과 탐색을 모두 값싸게 해 주지만, 데이터가 들어오는 순서에 따라 힘없이 무너지는 약점을 함께 만난다.