[DB Deep Dive] 1. 내 쿼리는 왜 느릴까? 인덱스(Index)의 본질과 B+Tree가 선택받은 이유

1. 시작하며: 왜 내 쿼리는 데이터가 많아질수록 느려질까?

우리가 구축한 플랫폼이나 대규모 서비스를 운영하다 보면, 초기에는 순식간에 끝나던 조회(SELECT) 쿼리가 데이터가 10만 건, 100만 건을 넘어가는 순간 급격하게 느려지는 현상을 마주하게 됩니다. 데이터베이스의 모든 레코드를 처음부터 끝까지 싹 다 뒤지는 전체 탐색(Full Scan)이 일어나기 때문입니다.

이 문제를 해결하기 위해 백엔드 개발자가 손에 쥐어야 할 가장 강력한 무기가 바로 인덱스(Index)입니다. 오늘은 인덱스의 본질적인 개념과 장단점, 그리고 데이터베이스가 왜 하필 수많은 자료구조 중 B+Tree를 선택했는지 그 내부 깊은 곳의 작동 원리를 파헤쳐 보겠습니다.

 

2. 인덱스(Index)의 본질과 양날의 검 (Overhead)

인덱스는 쉽게 말해 '책의 맨 뒤에 있는 색인(찾아보기)'과 같습니다. 수천 페이지짜리 전공 서적에서 특정 단어를 찾기 위해 첫 페이지부터 한 장씩 넘기는 바보 같은 짓을 하지 않듯, 데이터베이스도 데이터와 그 데이터가 저장된 물리적 위치를 묶은 별도의 자료구조를 만들어 두고 빠르게 찾아갑니다.

인덱스는 단순히 조회의 속도만 높이는 것이 아닙니다. UPDATE나 DELETE 연산을 수행할 때도 해당 대상을 먼저 '조회'해야 수정을 하든 삭제를 하든 할 수 있기 때문에, 전반적인 데이터 제어 성능이 함께 향상됩니다.

⚠️ 세상에 공짜는 없다: 인덱스의 오버헤드

인덱스를 무차별적으로 생성하면 DB가 터집니다. DBMS는 인덱스를 항상 '최신의 정렬된 상태'로 유지해야 하므로, 데이터 변경이 일어날 때마다 다음과 같은 무거운 추가 연산(오버헤드)이 발생합니다.

• INSERT: 새로운 데이터에 대한 인덱스 노드를 새로 추가하고 정렬해야 함.
• DELETE: 데이터를 지울 때 인덱스를 완전히 삭제하는 게 아니라 '사용하지 않음' 처리를 해둠. (인덱스 크기가 줄어들지 않음)
• UPDATE: 기존 인덱스를 '사용하지 않음' 처리하고, 갱신된 데이터에 대한 인덱스를 새로 추가함. (기존 데이터와 신규 데이터 오버헤드가 동시에 발생)

만약 수정과 삭제가 빈번한 컬럼에 인덱스를 남용하면, 실제 데이터는 10만 건인데 인덱스 찌꺼기는 100만 건이 쌓여 오히려 성능이 심각하게 저하되는 역효과를 낳게 됩니다. 따라서 인덱스는 데이터의 규모가 크고, 중복도가 낮으며(정밀도가 높고), 삽입/변경보다 조회가 압도적으로 많은 컬럼에 신중하게 걸어야 합니다.

 

3. 왜 해시 테이블(Hash Table)이 아니라 B-Tree 계열일까?

인덱스를 구현할 때 가장 먼저 떠오르는 자료구조는 단연 시간 복잡도 O(1)을 자랑하는 해시 테이블(Hash Table)일 것입니다. Key 값을 넣으면 단 한 번의 연산으로 원하는 가치를 찾아내니 완벽해 보입니다. 하지만 실제 데이터베이스 인덱스의 메인은 해시 테이블이 아닌 B-Tree 계열이 차지하고 있습니다. 이유가 무엇일까요?

🚫 해시 테이블의 치명적인 한계: 부등호 연산의 불가능

해시 함수는 값이 단 1만 달라져도 완전히 다른 해시 값을 생성합니다. 이는 정확히 일치하는 등호(=) 연산에는 특화되어 있지만, 부등호(<, >) 연산이나 범위 검색에는 무용지물임을 뜻합니다.

우리가 개발하는 플랫폼에서 WHERE 가격 >= 10000 이라거나 WHERE 생성일자 BETWEEN A AND B 같은 범위 검색 쿼리를 날릴 때, 해시 테이블 인덱스는 정렬되어 있지 않기 때문에 혜택을 전혀 받지 못하고 결국 Full Scan으로 돌아가게 됩니다. 데이터베이스의 탐색은 정렬을 기반으로 한 '범위 스캔'이 핵심이기에, 우리는 항상 정렬된 상태를 유지하는 Tree 계열 자료구조를 사용해야 합니다.

 

4. B-Tree vs B+Tree: 데이터베이스 최적화의 정수

이진트리를 확장하여 하나의 노드가 2개 이상의 자식 노드를 가질 수 있도록 균형을 맞춘 구조가 바로 B-Tree입니다. 노드 내부의 데이터들이 항상 정렬된 상태를 유지하고, 자식 노드들이 부모의 값 범위를 나누어 가지기 때문에 탐색 속도가 O(log N)으로 매우 안정적입니다.

여기서 한 단계 더 나아가 실제 현대의 RDBMS(예: MySQL InnoDB)가 채택한 구조는 B-Tree를 인덱스 전용으로 더욱 극대화한 B+Tree 자료구조입니다. 두 구조의 결정적인 차이점은 크게 두 가지입니다.

[ B-Tree ]

- 모든 내부 노드와 리프 노드가 Key와 함께 실제 데이터(Value)를 주렁주렁 들고 있음.

[ B+Tree ]

• - 내부 노드(Index Node)들은 오직 경로를 찾기 위한 'Key(가이드)'만 가짐.
• - 실제 데이터(Value)는 오직 최하단의 '리프 노드(Leaf Node)'에만 몰아서 저장됨.
• - 🌟 결정적으로 리프 노드들끼리 LinkedList(InnoDB는 Double LinkedList)로 연결되어 있음!

💡 B+Tree가 인덱싱에 압도적으로 유리한 이유

첫째, 내부 노드가 무거운 실제 데이터를 들고 있지 않기 때문에 하나의 메모리 페이지에 훨씬 더 많은 인덱스 Key들을 촘촘하게 채워 넣을 수 있습니다. 이는 결과적으로 트리의 전체 높이(Depth)를 낮추어 디스크 I/O 탐색 횟수를 획기적으로 줄여줍니다.

둘째, 범위 검색 시 B-Tree는 다른 노드로 가기 위해 다시 부모 노드를 거쳐 위아래로 복잡하게 트래킹해야 하지만, B+Tree는 원하는 범위의 시작 리프 노드로 단 한번 내려간 뒤, 리프 노드 간 연결된 LinkedList를 타고 오른쪽으로 쓱 밀면서 순차 검색(Linear Scan)을 끝내버릴 수 있습니다. 이 차이가 대용량 데이터 범위 조회 시 성능을 수십 배 가르는 핵심 원리입니다.

 

5. 1편을 마무리하며

오늘은 데이터베이스 검색 최적화의 첫 단추인 인덱스의 기본 메커니즘과, 왜 모든 메이저 RDBMS가 B+Tree라는 정교한 자료구조를 핵심 엔진으로 채택했는지 알아보았습니다. 면접관이 "왜 해시 인덱스를 안 쓰고 B+Tree를 쓰나요?"라고 묻는다면 이제 막힘없이 범위 검색과 디스크 I/O 효율성, LinkedList 스캔을 엮어서 당차게 대답할 수 있을 것입니다.

자료구조라는 기본 뼈대를 이해했으니, 이제 다음 2편에서는 이 B+Tree 아키텍처가 실제 디스크 공간 위에 어떤 형태로 물리적으로 배치되는지 알아보는 Clustered Index(영어 사전) vs Non-Clustered Index(찾아보기 색인)의 치명적인 차이점과, 면접에서 90% 이상 출제되는 MySQL InnoDB만의 독특한 구조를 낱낱이 파헤쳐 보겠습니다!

 

6. 추가 링크

https://mangkyu.tistory.com/96

[Database] 인덱스(index)란?

https://code-lab1.tistory.com/217

[자료구조] B-트리(B-Tree)란? B트리 그림으로 쉽게 이해하기, B트리 탐색, 삽입, 삭제 과정