"왜 hash table이 아닌가"를 생각해 보면 B+Tree 선택의 이유가 분명해집니다. hash index는 등호 비교(=)는 O(1)로 더 빠르지만, hash 함수가 값의 순서를 파괴하므로 범위 검색(>, BETWEEN), 정렬(ORDER BY), 접두사 검색(LIKE 'kim%')에 전혀 쓸 수 없습니다. 실제 쿼리의 상당수가 순서에 의존하기 때문에, 순서를 보존하는 B+Tree가 범용 기본값이 된 것입니다.

높이가 실제로 얼마나 낮은지는 계산으로 확인할 수 있습니다. 노드 하나가 disk page 하나(MySQL InnoDB 기준 16KB)에 대응하고 자식 포인터를 수백 개 담을 수 있으므로, 높이 3이면 수백의 3제곱, 즉 수천만-수억 row를 커버합니다. row가 10배로 늘어도 높이는 거의 그대로라, "데이터가 커져도 조회 속도가 유지된다"는 index의 약속이 이 구조에서 나옵니다.

두 장점이 어떻게 생기는지 이어 보면, 내부 노드의 역할은 "어느 자식으로 갈지" 안내뿐입니다. 여기에 데이터까지 두면(B-Tree) 그만큼 key가 덜 들어가 분기 수가 줄고 트리가 높아집니다. 트리 높이는 곧 디스크 읽기 횟수이므로, 내부 노드를 key 전용으로 비워 분기를 늘리는 것(B+Tree)이 디스크 기반 저장소에서는 직접적인 성능 이득입니다.

range query의 차이도 구체적입니다. B-Tree에서 범위를 훑으려면 트리를 오르내리며 다음 값을 찾아야 하지만, B+Tree는 범위의 시작점만 트리로 찾고 그다음부터는 leaf의 연결 리스트를 따라 순서대로 읽으면 끝입니다. WHERE id BETWEEN 100 AND 200 같은 쿼리가 "탐색 한 번 + 순차 읽기"로 처리되는 것이고, 이 패턴은 디스크의 순차 읽기 강점과도 맞아떨어집니다.

연결 리스트가 없을 때의 비용을 따져 보면 이유가 분명해집니다. 트리에서 어떤 key의 바로 다음 key를 찾으려면 부모 방향으로 올라가 경로를 되짚어야 하는데, DB에서는 노드 하나가 disk page 하나이므로 오르내리는 매 단계가 page 읽기입니다. 범위에 걸린 값이 1만 개라면 값 하나마다 트리 순회가 반복되는 셈입니다. leaf에 다음 leaf의 위치를 적어 두면 같은 작업이 "이웃 page 따라 읽기"가 되어, 1만 개를 읽어도 leaf page 수십 장을 차례로 읽는 것으로 끝납니다.

이 설계는 B+Tree라서 가능합니다. B-Tree는 데이터가 내부 노드에도 흩어져 있어 leaf만 이어 봐야 정렬된 전체를 얻을 수 없지만, B+Tree는 모든 데이터가 leaf 층에 모여 있으므로 leaf 리스트를 따라가는 것만으로 전체가 정렬 순서가 됩니다. MySQL InnoDB는 leaf를 양방향 연결 리스트로 이어 ORDER BY ... DESC 같은 역방향 읽기도 같은 방식으로 처리합니다.

Big-O 비교보다 디스크 I/O 횟수로 보면 차이가 더 실감납니다. full scan은 table의 모든 disk page를 읽어야 하므로, row 100만 개가 page 수만 개에 담겨 있다면 수만 번의 page 읽기입니다. B+Tree 탐색은 root에서 leaf까지 높이만큼, 즉 page 서너 개 읽기로 끝납니다. 게다가 root와 상위 노드는 거의 모든 쿼리가 거치므로 메모리 캐시(buffer pool)에 이미 올라와 있어, 실제 디스크 읽기는 더 적습니다.

단서도 있습니다. 이 비교는 소수의 row를 찾을 때 이야기이고, 조건에 걸리는 row가 table의 큰 비율이면 관계가 뒤집힙니다. index로 수십만 row를 하나씩 찾아가는 random 접근보다 table을 처음부터 순차로 읽는 full scan이 빠를 수 있어, optimizer는 예상 row 수를 보고 두 방식 중 싼 쪽을 고릅니다. "full scan = 나쁨"이 아니라 "찾는 양에 따라 다름"이 정확한 이해입니다.

조회할 때마다 정렬한다면 index는 성립할 수 없습니다. 정렬은 O(n log n)이라 full scan의 O(n)보다도 느리므로, 그 방식이면 index를 만들 이유 자체가 사라집니다. index의 전제는 정렬 비용을 조회 시점에 내지 않는 것입니다.

그 비용은 쓰기가 대신 냅니다. INSERT 한 번마다 "제자리 찾기 + 끼워 넣기"가 붙고, index가 5개면 5번 붙습니다. "index는 쓰기 성능을 깎는다"는 트레이드오프의 정체가 바로 이 비용으로, 매 쓰기마다 O(log n)씩 분할 납부하고 조회 때 회수하는 구조입니다.

책장에 비유하면 index는 새 책을 살 때마다 가나다순 제자리에 꽂아 두는 방식이고, full scan은 산 순서대로 쌓아 두고 찾을 때마다 전부 뒤지는 방식입니다. "찾을 때마다 책장 전체를 재배열한 뒤 찾기"에 해당하는 세 번째 방식은 어디에도 없습니다. 두 방식 중 무엇이 나은지는 꽂는 횟수(쓰기)와 찾는 횟수(읽기)의 비율이 정합니다.

full scan의 실체도 이 구조가 정합니다. PostgreSQL의 full scan은 heap page를 처음부터 끝까지 읽는 것이고, InnoDB의 full scan은 clustered B+Tree의 leaf 체인을 처음부터 끝까지 따라 읽는 것입니다. 어느 쪽이든 "트리 탐색 없이 전부 순차로 읽기"라는 점은 같습니다.

구조 차이는 조회 경로 차이로 이어집니다. PostgreSQL은 어떤 index로 찾든 "index → heap"의 간접 참조 한 번으로 경로가 균일합니다. InnoDB는 PK 조회라면 트리 하나로 row까지 도달해 가장 빠르지만, secondary index 조회는 PK 값을 얻어 clustered tree를 다시 타는 이중 조회가 됩니다. InnoDB에서 PK 설계(짧게, 단조 증가)가 유독 강조되는 이유가 table 자체가 PK 순서로 저장되기 때문이고, PostgreSQL에서 모든 index가 대등한 이유가 table이 어떤 index와도 무관한 heap이기 때문입니다.

전화번호부 비유가 정확합니다. (성, 이름) 순으로 정렬된 전화번호부에서 "김"씨는 몰려 있으니 바로 찾고, "김"씨 중의 "민수"도 그 안에서 정렬되어 있으니 찾을 수 있습니다. 하지만 성을 모른 채 이름이 "민수"인 사람을 찾으려면 결국 전체를 훑어야 합니다. (a, b) index에서 WHERE a = ?와 WHERE a = ? AND b = ?는 index를 타지만 WHERE b = ?만으로는 못 타는 이유가 이것입니다.

범위 조건이 끼면 한 가지 규칙이 더 생깁니다. WHERE a > 10 AND b = 5처럼 앞 column에 범위 조건을 쓰면, a가 10보다 큰 구간 안에서 b는 더 이상 정렬 상태가 아니므로 b 조건은 index 탐색에 쓰이지 못하고 걸러내기로만 쓰입니다. 그래서 composite index를 설계할 때는 등호로 쓰는 column을 앞에, 범위로 쓰는 column을 뒤에 두는 것이 일반 원칙입니다.

clustered 구조에서는 PRIMARY KEY 선택이 저장 배치를 결정하므로 성능 문제가 됩니다. auto increment PK는 새 row가 항상 마지막 page에 순서대로 붙어 삽입이 순차적입니다. 반면 무작위 UUID를 PK로 쓰면 삽입 위치가 트리 전체에 흩어져, 이미 찬 page 중간에 끼워 넣느라 page를 반으로 쪼개는 작업(page split)이 반복되고 캐시 효율도 나빠집니다. InnoDB에서 "PK는 짧고 단조 증가하게"라는 권장이 여기서 나옵니다.

이중 조회를 없애는 기법이 covering index입니다. 쿼리가 필요로 하는 column이 전부 index 안에 있으면, table까지 가지 않고 index만 읽고 끝낼 수 있습니다. SELECT user_id FROM orders WHERE status = ?에 (status, user_id) index가 있다면 leaf에 답이 이미 있는 식입니다. 자주 쓰는 쿼리의 SELECT 목록에 맞춰 index에 column을 추가하는 것은 이 효과를 노린 설계입니다.

DB가 선택도를 아는 방법은 통계입니다. optimizer는 쿼리를 실행하기 전에 "이 조건에 몇 row가 걸릴까"를 추정해야 index 사용 여부를 정할 수 있는데, 이를 위해 각 column의 고유값 수와 값 분포(histogram)를 주기적으로 수집해 둡니다. PostgreSQL의 ANALYZE, MySQL의 통계 갱신이 이 작업입니다.

이 구조의 함정은 통계가 낡을 수 있다는 것입니다. 대량 적재나 삭제 직후에는 통계가 실제 분포와 어긋나, optimizer가 "소수만 걸릴 것"이라 잘못 추정하고 index를 탔다가 실제로는 수십만 row를 random 접근하는 나쁜 실행 계획이 나올 수 있습니다. "어제까지 빠르던 쿼리가 갑자기 느려졌다"의 단골 원인 중 하나가 통계 불일치이고, 이때 통계 재수집이 처방이 됩니다.

성별(M/F) 컬럼에 인덱스를 걸고 WHERE gender = 'M'을 조회하면, 인덱스가 전체의 절반에 해당하는 row를 가리킵니다. 그 row들은 디스크에 흩어져 있어 하나씩 random access로 읽어야 합니다.

반면 full scan은 디스크를 처음부터 순차적으로 읽는 sequential I/O이고, 이는 random I/O보다 훨씬 빠릅니다.

optimizer가 이를 판단해 인덱스를 무시하고 full scan을 선택하기도 합니다.

비용을 구체화하면, index 5개가 걸린 table에 INSERT 하나가 들어오면 table 쓰기 1번에 B+Tree 갱신 5번이 따라붙습니다. 쓰기 한 번이 여러 배의 물리적 쓰기로 불어나는 이 현상을 쓰기 증폭(write amplification)이라 부릅니다. UPDATE도 바뀐 column을 포함한 index마다 "옛 위치에서 삭제 + 새 위치에 삽입"이 일어납니다.

그래서 index 설계는 추가만이 아니라 정리도 포함합니다. 대부분의 DB는 index별 사용 통계를 제공하므로(PostgreSQL의 pg_stat_user_indexes 등), 오랫동안 조회에 쓰이지 않으면서 쓰기 비용만 만드는 index를 찾아 제거할 수 있습니다. 겹치는 index도 정리 대상입니다. (a) index는 (a, b) index가 있으면 leftmost prefix로 대체되는 경우가 많아 중복일 수 있습니다.

"index가 있는데 안 탄다"의 단골 원인들은 패턴이 정해져 있습니다. column을 함수로 감싸면(WHERE UPPER(email) = ?) index는 원본 값 기준으로 정렬되어 있으므로 못 씁니다. 앞에 와일드카드가 붙은 LIKE '%kim'은 정렬의 시작점을 정할 수 없어 못 씁니다. 문자열 column을 숫자와 비교하면(WHERE phone = 01012345678) 암시적 형변환이 column 쪽에 걸려 함수로 감싼 것과 같아집니다. 셋 다 "index는 저장된 값 그대로의 정렬"이라는 성질에서 나오는 제약입니다.

진단 도구는 실행 계획입니다. EXPLAIN(PostgreSQL은 EXPLAIN ANALYZE)으로 실제 어떤 index를 탔는지, 예상 row 수와 실제 row 수가 얼마나 어긋나는지 확인할 수 있습니다. "느린 쿼리 → 추측으로 index 추가"가 아니라 "실행 계획 확인 → 원인에 맞는 수정"이 올바른 순서입니다.

B+Tree 갱신이 특히 비싸지는 순간이 page split입니다. 삽입할 leaf page가 이미 가득 차 있으면 page를 둘로 쪼개고 부모에 새 분기를 추가해야 하는데, 부모도 가득 차 있으면 분열이 위로 전파됩니다. 값이 무작위 순서로 들어오는 index일수록 삽입 위치가 흩어져 split이 자주 일어나고, 단조 증가하는 값(auto increment, timestamp)은 항상 끝에 붙어 split이 훨씬 적습니다.

이 비용 구조를 활용하는 실무 패턴이 대량 적재 시 index 전략입니다. 수백만 row를 넣어야 할 때 index가 걸린 채로 넣으면 row마다 트리 갱신이 반복되지만, index를 제거하고 데이터를 다 넣은 뒤 index를 다시 만들면 정렬된 데이터로 트리를 한 번에 쌓아 올릴 수 있어 훨씬 빠릅니다. 마이그레이션이나 초기 적재에서 흔히 쓰는 방법입니다.

여기서 자연스러운 다음 의문은 "InnoDB는 table 자체가 B+Tree인데, 그럼 INSERT마다 트리를 고치느라 느리지 않나"입니다. 이론상 맞지만 실제로는 빠르게 동작하도록 설계되어 있습니다. auto increment PK라면 새 row는 항상 가장 오른쪽 leaf 끝에 붙으므로 제자리를 찾는 탐색이 사실상 필요 없고, 그 끝 page와 상위 노드들은 계속 쓰이는 곳이라 메모리(buffer pool)에 이미 올라와 있습니다. 트리에 넣는다고 해도 실질적으로는 append입니다.

디스크 쓰기도 트리 조작과 분리되어 있습니다. 커밋 시점에 즉시 디스크에 쓰는 것은 변경 내역을 기록하는 redo log(순차 쓰기)뿐이고, B+Tree page 자체는 메모리에서 고쳐 뒀다가 나중에 모아서 내려씁니다. secondary index도 change buffer라는 장치가 변경 내용만 적어 뒀다가 나중에 병합합니다. 그래서 INSERT 하나는 보통 1ms 미만이고, 느려지는 것은 무작위 UUID PK로 삽입 위치가 흩어져 page split과 random I/O가 반복되거나 secondary index가 많아 갱신이 여러 배로 불어나는 경우입니다.