인덱스는 왜 B+ tree 구조로 설계되었을까요? - 기술 면접 준비

 

 

 

면접관: 많은 자료구조들이 있는데, 데이터베이스의 인덱스는 왜 B+ tree 구조로 설계되었을까요?

 

 

🥉 하수

데이터를 빠르게 찾기 위해서 인덱스를 사용하는데, 그 구조로 B+ Tree를 사용하는 이유는 정렬된 데이터를 균형 잡힌 구조로 관리할 수 있기 때문입니다.

B+ Tree는 항상 균형을 유지하면서 검색, 삽입, 삭제가 빠르게 되기 때문에 인덱스에 적합합니다.

 

가능한 추가 질문
그럼 B Tree와 B+ Tree의 차이는 뭐예요?
이진 탐색 트리랑은 뭐가 달라요?

 

 

🥈 중수

인덱스나 데이터가 주로 디스크에 저장되기 때문에, 디스크 I/O가 적게 발생하는 자료구조가 적합한데,

B+ Tree는 노드 하나에 많은 key를 저장할 수 있는 M-진 트리이기 때문에, 트리의 높이가 낮고 디스크 I/O가 적게 발생합니다.
또, 모든 데이터를 리프 노드에만 저장하고, 리프 노드끼리 연결 리스트로 이어져 있어서 범위 검색에도 유리합니다.
그래서 디스크 기반 DBMS에서는 B+ Tree가 가장 일반적으로 쓰입니다.

가능한 추가 질문
그럼 Hash 자료구조의 인덱스와는 어떤 차이가 있나요?
그럼 B+ Tree의 fan-out이 크면 어떤 장점이 있나요?

 

 

🥇 고수

인덱스가 B+ tree로 주로 설계되는 이유는 크게 3가지가 있습니다.

DB는 디스크에서 데이터를 읽을 때, 한 번에 가령 4KB와 같이 블록 단위로 읽는데, B+ Tree도 하나의 노드에 많은 key 값을 담는 자료구조라서, 디스크의 페이지 단위 저장 구조와 잘 맞는 자료구조입니다.
그리고, B+ tree는 리프 노드에만 데이터가 있고, 이를 연결 리스트로 연결해서 범위 탐색에도 유리하다는 장점이 있습니다.
또, 높이가 낮으므로 탐색 시간(log base fan-out)이 적게 소요되고, 디스크 접근 횟수도 줄어듭니다.
결국, 구조의 일치, 범위 검색 최적화, 디스크 I/O 최소화가 가능한 점에서 B+ Tree가 최적입니다.

가능한 추가 질문
그럼 인덱스 페이지 하나에 몇 개의 키가 들어가나요?
리프 노드가 페이지 split될 때 성능에 미치는 영향은?

 

 

🧙 고인물

B+ Tree는 높은 fan-out 덕분에 트리의 depth가 작고, 그로 인해 디스크 I/O가 최소화됩니다.
DBMS는 인덱스를 페이지 단위로 저장하며, 하나의 페이지는 여러 키 값을 담을 수 있게 튜닝됩니다.
리프 노드만 데이터를 가지기 때문에 삽입·삭제 리밸런싱도 B Tree보다 단순하고 예측 가능합니다.
또한, 리프 노드끼리 연결된 구조 덕분에 클러스터드 인덱스에서는 데이터 페이지도 물리적으로 인접하게 유지할 수 있고, 레인지 스캔이 효율적입니다.
추가적으로, 현대의 InnoDB 같은 스토리지 엔진은 B+ Tree 인덱스 뿐만 아니라, leaf page split 관리, redo log를 통한 write buffering, buffer pool 캐싱 같은 고급 기법과 결합하여 성능을 끌어올립니다.

가능한 추가 질문
InnoDB에서 B+ Tree 인덱스의 리프 노드에는 실제 데이터가 있나요?
클러스터드 vs 세컨더리 인덱스의 차이는?
MVCC와 인덱스는 어떤 관계가 있나요?

 

 

 

👏

 

자, 이렇게 인덱스는 왜 B+ tree로 설계되었을까? 에 대해서 다뤄봤습니다!

여러분들은 하수 ~ 고인물 중에서 어떤 위치에 속하시나요?

저도 이 포스팅을 작성하면서, 좀 더 상세하게 공부를 하게 된 것 같은데요...!

 

평비의 이 평범한 글이 여러분에게 비범한 도움이 되었으면 좋겠습니다 👍