1장. 처음부터 끝까지 읽던 시절 — 순차 스캔과 ISAM

{/* 삽화 자리 — 끝없는 서가를 처음부터 끝까지 훑고 손에는 얇은 폴더 한 장 */}

인덱스가 없으면 테이블을 처음부터 끝까지 읽습니다. 다들 아는 문장이에요. 문제는 그 “끝까지”가 얼마인지를 행 수로 세면 계속 틀린다는 겁니다.

면접 실전 질문: ① 인덱스가 없으면 왜 느린가요? ② 정렬해두고 색인을 붙인 ISAM은 왜 B-tree로 대체됐나요? ③ 풀스캔 비용은 행 수에 비례하나요?

배경 — 찾는다는 게 곧 처음부터 읽는 것이던 시절

초창기 컴퓨터에게 “데이터를 찾는다”는 말은 문자 그대로 처음부터 읽는다는 뜻이었습니다. 저장장치가 자기 테이프였기 때문입니다. 테이프는 물리적으로 순차 매체예요. 1,000번째 레코드를 보려면 앞의 999개를 지나가는 것 말고 방법이 없습니다.

그래서 그 시절 데이터 처리는 전부 “정렬해두고 한 번에 훑는” 모양이었습니다. 오늘의 배치 잡이 그 시절 사고방식의 화석입니다.

1956년 9월, IBM이 이 전제를 깼습니다. 305 RAMAC에 실린 IBM 350 디스크 저장장치는 자기 디스크 50장에 500만 문자를 담았습니다. 요즘 스마트폰 사진 한 장 남짓이에요. 무엇보다 헤드가 움직여 원하는 자리로 바로 갈 수 있었습니다. RAMAC이라는 이름 자체가 Random Access Method of Accounting and Control이에요. 순차가 아니라 임의로 접근한다는 게 제품명에 박혀 있을 만큼 새로운 일이었습니다.

📄 문서 기반 (미검증) — IBM 350의 평균 탐색 시간은 약 600밀리초였습니다. 출처에 따라 최대 800밀리초로도 적힙니다.

이 600ms라는 숫자를 잠깐 붙들고 갑시다. 한 번 찾아가는 데 0.6초입니다. 요즘 NVMe SSD의 임의 읽기가 수십 마이크로초니까 자릿수로 네 개쯤 차이가 납니다.

이 값이 이후 수십 년의 자료구조 설계를 끌고 갑니다. 디스크에 한 번 갔다 오는 게 이렇게 비싸면, 알고리즘을 고를 때 세야 하는 건 비교 횟수가 아니라 디스크에 몇 번 갔다 오는가입니다. 이 관점이 2장에서 B-tree의 모양을 정하고, 이 장 끝에서 이 책이 쓸 단위를 정합니다.

임의 접근이 가능해지자 곧바로 따라온 질문이 있었습니다. “그래서 원하는 레코드가 어느 자리에 있는지는 어떻게 아는가?” 디스크가 아무 데나 갈 수 있어도, 어디로 가야 할지 모르면 결국 처음부터 읽는 것과 같습니다.

스토리 — 1966년의 답, 그리고 그 답이 무너진 방식

IBM의 답은 ISAM이었습니다. Indexed Sequential Access Method, 색인 순차 접근 방식. 1966년 OS/360과 함께 나왔습니다. 이름에 답이 들어 있어요 — 순차(sequential)로 정렬해 두되, 색인(indexed)을 옆에 붙인다.

구조는 이렇습니다.

찾는 절차는 직관적입니다. 마스터 인덱스로 실린더를 고르고, 실린더 인덱스로 그 실린더의 트랙 인덱스를 찾고, 트랙 인덱스로 트랙 하나를 정합니다. 그리고 그 트랙만 읽어요. 테이블 전체를 훑는 대신 작은 표 두세 개를 거쳐 목적지 한 곳으로 갑니다. 오늘 우리가 인덱스에 기대하는 게 정확히 이 3단 축소이고, 그 기대의 원형이 여기서 만들어졌습니다.

여기까지는 좋은 설계입니다. 무너진 건 삽입이었어요.

정렬을 유지한다는 약속의 대가

ISAM의 인덱스는 파일을 만들 때 고정됩니다. 트랙 인덱스가 “이 트랙의 최대 키는 4500”이라고 적어 뒀다면, 그 구조는 이후에 변하지 않아요.

그런데 키가 4200인 레코드가 새로 들어오면 어떻게 될까요. 키 4200이 들어갈 트랙은 이미 꽉 차 있습니다. 정렬을 지키려면 뒤의 레코드를 전부 한 칸씩 밀어야 하는데, 그건 파일 전체를 다시 쓰는 일입니다.

그래서 ISAM은 밀지 않고 딴 데 둡니다. 트랙에서 밀려난 레코드를 오버플로 영역에 놓고, 원래 자리에 “다음은 저쪽” 포인터를 남깁니다. 삽입이 쌓이면 이 포인터가 줄줄이 이어져 오버플로 체인이 됩니다.

체인은 정렬돼 있지 않습니다. 인덱스도 그 안을 모릅니다. 그래서 체인에 걸린 레코드를 찾으려면 체인을 처음부터 따라가야 합니다. 인덱스로 트랙 하나까지 좁혀 놓고, 거기서 다시 순차 탐색을 하는 거예요.

시간이 지날수록 이 체인이 길어집니다. 조회 성능이 서서히 나빠지는데, 스키마도 그대로고 쿼리도 그대로입니다. 바뀐 건 삽입이 쌓였다는 것뿐이에요.

밤마다 다시 세우는 의식

이 시절의 해법은 주기적인 재구성(reorganization)이었습니다. 파일 전체를 순서대로 읽어서 새 프라임 영역에 다시 깔고, 인덱스를 새로 만듭니다. 오버플로에 흩어져 있던 레코드가 제자리를 찾고, 체인이 사라집니다.

📄 문서 기반 (미검증) — 1960년대 데이터베이스 운영에서 이런 재구성은 흔한 일과였고, 보통 매일 밤이나 매주 돌렸습니다.

이 대목이 중요합니다. 자료구조의 결함을 운영 절차로 메우고 있었던 거예요. “삽입하면 느려집니다. 대신 밤마다 다시 세우세요.” 시스템이 24시간 돌아가지 않던 시절이라 가능한 타협이었습니다.

그리고 이 타협이 깨지는 순간이 옵니다. 온라인 시스템이 등장하면서 “밤에 멈춘다”는 전제 자체가 사라지거든요.

1970년, 보잉의 두 사람

1970년 7월, 보잉 과학연구소(Boeing Scientific Research Laboratories)의 루돌프 바이어와 에드워드 맥크레이트가 이 문제를 정면으로 다룹니다. 「Organization and Maintenance of Large Ordered Indexes」. 같은 해 ACM SIGFIDET 워크숍에서 발표됐고, 1972년 학술지 Acta Informatica 1권 173–189쪽에 실렸습니다.

이들이 세운 목표가 정확히 ISAM이 실패한 지점이었습니다. 재구성 없이도 삽입과 삭제를 견디는 인덱스. 그리고 비용을 셀 때 비교 횟수가 아니라 디스크 접근 횟수를 셌습니다. 600ms짜리 탐색이 지배하는 세계에서는 그게 유일하게 말이 되는 계산이니까요.

그 답이 B-tree입니다. 왜 하필 그런 모양이 됐는지는 2장에서 뜯어봅니다.

다만 그 전에 확인하고 갈 게 있어요. ISAM이 풀려던 문제 — “인덱스가 없으면 얼마나 드는가” — 를 우리는 아직 숫자로 모릅니다. 그리고 그 값을 재는 순간, 이 책 전체가 쓰는 단위가 결정됩니다.

핵심 — 풀스캔의 값을 재보면 단위가 드러납니다

풀스캔이 얼마나 드는지 직접 재봤습니다. 조건은 인덱스가 하나도 없는 테이블, 그리고 존재하지 않는 값으로 조회하기입니다. 중간에 멈출 구실을 없애야 스캔 비용이 온전히 드러나니까요.

여기서부터 풀스캔은 InnoDB의 type=ALL, 즉 클러스터드 인덱스를 처음부터 끝까지 훑는 동작을 가리킵니다. 앞에서 말한 테이프 시대의 순차 스캔과 정신은 같지만 대상이 다릅니다.

-- 세컨더리 인덱스 0개. WHERE 는 무조건 풀스캔이 된다.
CREATE TABLE scan_demo (
  id             BIGINT    NOT NULL AUTO_INCREMENT PRIMARY KEY,
  transaction_no CHAR(20)  NOT NULL,
  status         CHAR(8)   NOT NULL,
  payload        CHAR(180) NOT NULL
) ENGINE=InnoDB;
 
EXPLAIN ANALYZE SELECT * FROM scan_demo WHERE transaction_no = '99999999999999999999';

실행계획은 네 크기 모두 type=ALL, key=NULL이었습니다. 풀스캔이 맞습니다.

페이지 수와 요청 수는 이렇게 뽑습니다.

-- 테이블 페이지 수 (근사값이지만 DATA_LENGTH 와 교차 확인했습니다)
SELECT CLUST_INDEX_SIZE FROM information_schema.INNODB_TABLESTATS st
  JOIN information_schema.INNODB_TABLES t ON st.TABLE_ID = t.TABLE_ID
 WHERE t.NAME = 'bookdb/scan_demo';
 
-- 페이지 요청 — 쿼리 전후로 두 번 찍어 차이를 본다
SHOW GLOBAL STATUS LIKE 'Innodb_buffer_pool_read_requests';

재는 값은 셋입니다. 테이블 페이지 수(INNODB_TABLESTATS.CLUST_INDEX_SIZE), 버퍼풀 페이지 요청 수(Innodb_buffer_pool_read_requests 델타), 그리고 스캔 시간입니다.

가운데 값은 이름 그대로 읽어주세요. 요청 수는 “버퍼풀에 페이지를 달라고 한 횟수”이지 서로 다른 페이지의 개수가 아닙니다. 같은 페이지를 열 번 달라고 하면 10으로 셉니다. 뒤에서 이 구분이 결정적으로 쓰입니다.

실험 1 — 행 수를 8배로 늘려봤습니다

✅ 실측 (MySQL 8.0.40 / Docker / Apple M1 8코어 / macOS, 2026-08. 버퍼풀 1GB, 가장 큰 테이블 498MB로 전부 메모리 상주. 크기마다 6회 실행 후 최솟값. 전체 소스: docs/book/code/db-index/ch01/run.sh)

행이 8배가 되니 페이지도 7.96배, 시간도 8.07배가 됐습니다.

그런데 이 표로는 범인을 못 가립니다. 행과 페이지가 손을 잡고 같이 움직였으니, 시간을 끌고 간 범인이 둘 중 누구인지 알 수 없어요. 갈라놓아야 압니다.

갈라놓기 전에 표에서 짚고 갈 게 하나 더 있습니다. 시간은 흔들렸고 페이지 수는 안 흔들렸습니다. 1,000,000행 구간은 페이지당 시간이 이웃들보다 20%쯤 높게 나왔어요. 시드부터 다시 만들어 두 번 재도 그대로였습니다. 원인은 못 찾았고, 지우지 않고 표에 남겼습니다. 시간을 최솟값으로 쓴 것도 이 흔들림 때문이에요 — 측정하는 동안 같은 노트북에서 IDE가 CPU를 쓰고 있었고, 잡음은 한쪽으로만 더해지니 최솟값이 가장 방해를 덜 받은 회차입니다.

실험 2 — 행 수를 고정하고 폭만 바꿔봤습니다

행 수를 25만 행으로 고정하고 payload 컬럼의 타입만 바꿨습니다. 행 수가 비용을 정한다면 셋의 값이 같아야 합니다.

✅ 실측 (같은 환경. 한 번에 테이블 하나만 남겨 버퍼풀 경합을 없앴고, 세 테이블 모두 전 회차 물리 read 델타 0 — 전부 버퍼풀 히트임을 확인했습니다. 테이블당 4회 실행 후 최솟값이며, 두 요청 열은 같은 조건(EXPLAIN ANALYZE)으로 쟀습니다. 시간 열은 페이지 열보다 훨씬 약한 증거입니다 — JSON 행은 독립 실행 세 번에서 106ms·118ms·973ms로 최대 8배까지 흔들렸고 원인은 못 찾았습니다. 반면 페이지와 요청 수는 세 번 모두 한 자리도 다르지 않았어요. 전체 소스: docs/book/code/db-index/ch01/rowwidth.sh)

첫 행은 실험 1의 25만 행과 같은 테이블입니다. 페이지와 요청은 한 자리도 안 다르고 시간만 58.7 → 58.0ms로 다른데, 다른 회차라 그렇습니다. 시간 비교는 각 표 안에서만 하세요.

행 수는 셋 다 똑같이 25만입니다. 그런데 테이블 크기는 63MB에서 653MB까지, 10.4배 차이가 납니다.

여기서 “25만 행짜리 테이블”이라는 말이 비용에 대해 아무것도 알려주지 않는다는 게 드러납니다. 같은 25만 행이 63MB일 수도 653MB일 수도 있어요.

SELECT *가 붙이는 값, 그리고 JSON만 다른 이유

가운데 두 열을 나란히 보면 더 재미있는 게 나옵니다.

SELECT id처럼 넓은 컬럼을 안 읽으면 요청 수가 페이지 수와 거의 정확히 같습니다 — 1.03, 1.01, 1.00. 페이지를 한 번씩만 만지고 지나간다는 뜻이에요.

그런데 SELECT *로 넓은 컬럼을 달라고 하는 순간 달라집니다. CHAR(180)과 VARCHAR(1000)은 1.39와 1.43으로 비슷한데, JSON만 6.98로 튑니다. 폭이 4.5배 차이 나는 앞의 둘이 같은 비를 유지하는 걸 보면, JSON은 폭 때문이 아니라 종류 때문에 다른 겁니다.

(앞의 둘에서 페이지당 0.4쯤이 남는 건 설명을 못 찾았습니다. 지우지 않고 남겨둡니다.)

숫자를 하나 더 보죠.

291,671 (SELECT *)  −  41,839 (SELECT id)  =  249,832  ≈  행 수 250,000

JSON 컬럼을 읽으면 행마다 페이지를 한 번씩 더 요청합니다.

6.98이라는 비도 그대로 쪼개집니다. 이 테이블은 페이지당 5.98행(250,000 ÷ 41,792)이니까요.

5.98 (행마다 하나)  +  1.00 (페이지마다 하나)  =  6.98

소수점까지 맞습니다.

📄 문서 기반 (미검증) — InnoDB에는 여러 행을 묶어 가져오는 프리페치 캐시가 있고, 읽을 컬럼에 BLOB 계열(JSON 포함)이 끼면 이 캐시가 꺼진다고 알려져 있습니다. 그러면 행마다 페이지를 다시 잡게 되어 위 숫자와 맞아떨어집니다. 다만 필자가 소스로 확인한 것은 아닙니다.

여기서 한 가지 오해를 미리 지웁니다. 이 추가 요청은 오버플로 페이지 때문이 아닙니다(제 블로그 글이 그렇게 썼다가 정정했습니다). InnoDB에서 값이 페이지 밖으로 빠지는 건 행이 페이지의 절반(약 8KB)에 안 들어갈 때인데, 이 JSON은 2.1KB라 한참 밑돕니다. 실제로 DATA_LENGTH가 653MB이고, 이걸 실제 행 수로 나누면 행 하나가 페이지에서 차지한 공간이 평균 2,739바이트입니다 — 값이 페이지 안에 그대로 들어 있다는 뜻이에요. 정말 페이지 밖으로 빠졌다면 클러스터드 인덱스는 20MB도 안 됐을 겁니다.

여기서 AVG_ROW_LENGTH 컬럼을 그냥 믿으면 안 됩니다. 그 값은 3,286바이트로 나오는데, 분모인 TABLE_ROWS가 InnoDB에서는 추정값이라 그렇습니다(실제 25만 행을 208,360으로 추정했습니다). 행 폭을 볼 때는 DATA_LENGTH ÷ COUNT(*)로 직접 나누세요.

이 구분은 16장에서 다시 씁니다. 커버링 인덱스가 하는 일이 정확히 “안 읽어도 될 컬럼을 안 읽는 것”이거든요. 위 표의 SELECT id 열이 그 미리보기입니다.

두 실험을 화해시키면

두 실험은 다른 말을 하는 것처럼 보입니다.

가운데 줄이 가장 깨끗한 대조입니다. 행 수가 그대로고 요청/페이지 비도 그대로(1.39 → 1.43)인데 페이지만 4.47배 늘렸어요. 시간은 18% 늘었습니다.

메모리에 다 올라와 있을 때 스캔 시간을 끌고 가는 건 페이지가 아니라 행을 처리하는 비용입니다. 실험 1에서 시간이 페이지를 따라간 것처럼 보였던 건 행이 같이 늘었기 때문이고요.

세 번째 줄이 1.83배로 더 붙는 건 페이지가 더 늘어서가 아닙니다. 앞 절에서 본 행마다 붙는 추가 요청 때문이에요. 그러니 이 줄도 결국 행 쪽 비용입니다.

비용이 페이지 단위로 청구되는 건 그 페이지를 디스크에서 가져와야 할 때입니다. 그때는 63MB냐 653MB냐가 곧바로 초 단위로 환산됩니다.

운영에서 잰 값이 정확히 그 경우였습니다. 370만 행 2.2GB 테이블에서 거래번호 하나를 찾는 데 45.36초가 걸렸고, 그중 41.17초가 순수 테이블 스캔이었습니다. 초당 약 54MB — 순차 읽기라기엔 낮습니다. 왜 낮은지는 8장에서 버퍼풀을 뜯어보며 다룹니다.

(✅ 운영 실측 인용 — 조건을 안 걸면 빠릅니다. 그 테이블도 headers·body를 JSON으로 들고 있었습니다. 행당 평균 625바이트로 이 실험의 2,739바이트보다 4.4배 가볍지만, 행 수가 15배라 총량이 2.2GB였습니다. 다만 그 글은 같은 JSON 값이 오버플로 페이지로 빠진다고 설명하는데, 이 장의 측정과는 어긋납니다 — 625바이트는 DATA_LENGTH ÷ 행 수라 인라인인지 오버플로인지 구분해주지 못합니다. 그 테이블을 직접 확인하지는 못했습니다.)

그래서 이 책은 페이지를 셉니다

정리하면 이렇습니다.

• 행 수는 읽어야 할 양을 알려주지 않습니다. 같은 25만 행이 63MB일 수도 653MB일 수도 있으니까요.
• 양을 알려주는 건 페이지 수입니다. 그리고 페이지 수는 행 수가 아니라 행 수 × 행 폭에서 나옵니다.
• 그 양이 시간으로 바뀌는 환율은 버퍼풀이 정합니다. 메모리에 있으면 싸고, 디스크에서 가져와야 하면 45초가 됩니다.

그래서 이 책은 앞으로 비용을 셀 때 행이 아니라 16KB 페이지를 셉니다. 인덱스가 하는 일도 같은 단위로 다시 쓸 수 있어요 — 인덱스는 읽지 않아도 될 페이지를 안 읽게 만드는 장치다.

정리

• 테이프 시절에는 찾는다는 게 곧 처음부터 읽는 것이었습니다. 1956년 IBM 350이 임의 접근을 열었지만 평균 탐색이 600밀리초라, “디스크에 몇 번 갔다 오는가”가 곧 비용이었습니다.
• ISAM(1966)은 정렬을 유지하고 색인을 옆에 붙였습니다. 오늘 우리가 인덱스에 기대하는 그림의 원형입니다.
• ISAM이 무너진 지점은 삽입이었습니다. 자리가 없는 레코드를 오버플로 체인에 매달았고, 체인이 길어질수록 조회가 느려졌습니다. 해법은 자료구조가 아니라 밤마다 파일을 다시 세우는 운영 절차였습니다.
• 1970년 보잉의 바이어와 맥크레이트가 그 문제를 정면으로 겨눕니다. 재구성 없이 삽입·삭제를 견디는 인덱스, 그리고 디스크 접근 횟수로 비용을 세는 관점. 그 답이 B-tree입니다.
• 풀스캔 비용의 단위는 행이 아닙니다. 행 수가 같아도(25만) 폭이 다르면 크기는 10.4배 차이 났고, 넓은 컬럼을 실제로 읽으면 페이지 요청이 행마다 하나씩 더 붙었습니다.

생각해볼 질문

1. 실험 2에서 SELECT id는 요청 수가 페이지 수와 같았는데(1.00배) SELECT *는 6.98배였습니다. 조회에 필요한 컬럼이 전부 인덱스 안에 있다면 어떻게 될까요? (16장 커버링 인덱스가 이 질문의 확장판입니다)
2. ISAM은 “인덱스 구조를 고정하고 넘치는 건 딴 데 둔다”를 택했습니다. B-tree가 이걸 어떻게 다르게 풀지 상상해본다면, 삽입할 자리가 없을 때 무엇을 해야 할까요?
3. 이 장의 측정에서 페이지 수는 매번 같았지만 시간은 최대 8배까지 흔들렸습니다. 성능을 이야기할 때 어느 쪽을 근거로 삼아야 할까요?

▶ 2장. B-tree는 왜 이진트리가 아닌가 — 디스크가 정한 모양