[DB] 인덱스 (B 트리)

인덱스란?

인덱스는 책의 목차와 유사하다. 책을 읽을 때 목차를 이용하면 원하는 내용을 빠르게 찾아 읽을 수 있다. 마찬가지로 테이블도 인덱스를 이용하여 원하는 데이터를 빠르게 조회할 수 있다.

데이터베이스에서 인덱스는 테이블에 대한 검색 속도를 높여주는 자료 구조를 의미한다. 특정 컬럼에 인덱스를 생성하면 전체 테이블을 스캔 (full scan) 하는 대신 인덱스를 참조하여 원하는 결과를 빠르게 조회할 수 있다.
 

B 트리

인덱스는 데이터를 미리 정렬하여 검색 연산의 성능을 향상시킨다. 트리 알고리즘은 검색 및 정렬 연산에서 효과적인 자료 구조이므로 인덱스는 트리를 사용하여 구현된다.

💡 균형 잡힌 이진 트리의 경우 O(log n)의 시간 복잡도를 갖는다.

 
인덱스는 주로 B 트리로 구현되는데, B 트리는 일반 이진 트리와 비교하여 몇 가지 중요한 차이점이 있다. 이진 트리의 노드는 최대 두 개의 자식을 가질 수 있지만, B 트리는 여러 개의 자식을 가질 수 있다.

🌳 B 트리의 특징

• 각 노드는 여러 개의 자식을 가질 수 있다.
• 각 노드는 정렬된 순서의 키들을 가지고 있다.
• 자동으로 균형을 유지한다. (모든 리프노드가 동일한 레벨에 위치한다!)

 
그렇다면 이진 트리보다 B 트리가 인덱스에 더 적합한 이유는 뭘까? 해당 이유에 대해 알아보기 전에 B 트리의 노드에 대해 알아보자.
B 트리에는 세 종류의 노드가 존재한다.

1. 루트노드 - 인덱스의 시작 지점으로, 모든 검색이 루트노드부터 시작된다.
2. 내부노드 - 트리의 중간에 위치한 노드로, 키 값의 범위에 따라 자식 노드로 안내한다.
3. 리프노드 - 실제 데이터를 담고 있는 노드로, 키 값과 그에 해당하는 데이터 위치를 갖고 있다.

🚨 루트노드와 내부노드는 데이터를 찾아가기 위한 경로를 제공하는 키 값들을 저장한다. 리프노드에 도달하면 실제 데이터 위치를 찾아 데이터베이스에 접근한다.

 
앞서 말했듯이 B 트리는 많은 자식을 가질 수 있다. 한 레벨 당 더 많은 키를 저장할 수 있으므로 전체 트리의 높이가 낮아진다. 루트노드에서 리프노드까지 가는 경로가 짧아지므로 이진트리보다 더 빠르게 데이터를 조회할 수 있다.
 

인덱스를 사용하면 무조건 성능이 향샹될까

인덱스를 사용하면 검색 속도가 증가한다. 하지만 인덱스를 사용했을 때의 단점도 존재한다.
인덱스는 디스크 공간을 차지한다. 게다가 인덱스가 적용된 컬럼에 삽입/수정/삭제 연산이 일어나면 정렬된 상태를 유지하기 위해 업데이트가 발생하여 쓰기 작업이 느려질 수 있다.