인덱스(index)란?

1. 인덱스란?

• DB 테이블에 대한 검색 속도를 향상시켜주는 자료구조
• 인덱스는 보통 B-Tree로 구현되며, 다른 것으로는 Hash Table, Bitmap 등이 있음
• 인덱스를 테이블의 특정 컬럼에 생성하면 해당 컬럼의 값을 정렬하여 별도의 메모리 공간에 데이터를 물리적 주소와 함께 저장함
• 인덱스는 insert, update, delete 와 같은 데이터 변경 작업을 느리게 할 수 있지만, select와 같은 검색 작업은 빠른 수행 가능
• 인덱스는 적절하게 설계하고 유지보수하는 것이 DB 성능 향상에 중요한 역할을 함

예를 들면, 책에서의 목차 또는 색인이라 볼 수 있다. 목차를 보고 빠른 내용을 찾을 수 있기 때문이다.

 

1-1. 왜 인덱스를 사용하면 검색 속도가 빠를까?

• 기존 where 문으로 특정 조건 데이터를 찾기 위해서는 전체 테이블 스캔 작업이 필요함
• 인덱스를 이용하면 데이터들이 정렬되어 있기에 조건에 맞는 데이터를 더 빠르게 탐색 가능
• 또한, order by문이나 min/max 같은 경우도 이미 정렬되어 있기에 빠른 수행 가능

전체 테이블 스캔(Full Table Scan) : 테이블에 존재하는 모든 데이터를 읽으면서 조건 비교
인덱스 스캔(Index Scan) : 인덱스를 구성하는 컬럼의 값을 기반으로 데이터를 추출하는 액세스 기법

 

2. Hash Table이란?

• 간단하고 빠른 검색이 가능한 자료구조
• 등호 연산에 최적화되어 있으며, key-value 구조로 데이터 저장
• 인덱스에서는 컬럼 값이 key, 저장된 레코드의 물리적 주소가 value
• 해시 함수를 이용해 key를 해시값으로 변환하고, 이를 이용해 빠른 데이터 검색 가능
• 해시 함수를 이용할 때 충돌 발생 시, 일반적으로 해시 테이블은 각각의 슬롯에 연결리스트 사용해서 충돌 처리(Separate Chaining)
• 해시 테이블은 검색 속도가 매우 빠르지만, 범위 검색에는 적합하지 않음
• 범위 검색이 자주 일어나는 경우 B-Tree와 같은 자료구조를 사용하는 것이 좋음

 

2-1. Hash Table에서 범위 검색은 왜 비효율적일까?

• 범위 검색 수행 시, 일반적으로 연속된 인덱스 엔트리를 찾아야함
• 해시 테이블은 해시함수에 의해 무작위로 분산되어 저장되기에 인덱스 엔트리들이 서로 물리적으로 연속되어 저장되지 않을 수 있음
• 이 경우, 연속된 인덱스 엔트리를 찾기 위해 모든 인덱스 엔트리를 검색해야 하기 때문에 비효율적
• 따라서, 해시 테이블은 주로 동등비교(equality search)에 사용하며, 범위 검색에는 비효율적

인덱스 엔트리(Index Entry)란?
- DB 인덱스에서 각각의 인덱스 키 값에 대한 정보를 담고 있는 데이터 레코드를 말함
- 인덱스 엔트리에는 인덱스 키 값과 해당하는 레코드의 위치 정보가 포함
- 인덱스 엔트리는 인덱스 자료구조의 종류에 따라 다양한 방식으로 구현됨
- B-Tree에서는 인트리가 키와 포인터로 이루어짐
- Hash Table에서는 해시값과 해당 키에 대응되는 데이터 레코드의 위치 정보로 이루어짐

 

3. B-Tree란?

• 자주 사용되는 데이터를 효율적으로 검색하기 위해 설계된 트리 구조
• B-Tree는 Balanced Tree의 약자로, 트리의 균형을 유지하여 검색 속도를 높이는 것이 핵심
• DB 인덱스를 구현하는 데 많이 사용되며, 대용량 데이터를 저장 및 검색하는 데 매우 효율적

 

3-1. B-Tree 특징

• 균형 잡힌 트리
• 여러 개의 자식 노드를 가질 수 있음
• 각 노드에는 여러 개의 데이터가 저장될 수 있음
• 데이터 삽입, 삭제, 검색할 때 모든 연산은 트리의 높이에 비례
• 평균적으로 시간 복잡도는 O(log n)

 

4. 인덱스 사용 시 주의사항

• 자주 검색하지 않는 컬럼이면 인덱스 생성 및 관리 비용이 더 늘어날 수 있음
• 중복 인덱스 방지
  • 동일 컬럼을 기준으로 여러 개의 인덱스 생성하지 않도록 주의
  • 중복된 인덱스는 불필요한 저장공간을 차지하며 데이터 삽입, 삭제, 수정 시에도 불필요한 비용 발생 가능
• 인덱스는 공간적 비용이 발생하므로, 너무 많은 인덱스는 성능 저하가 올 수 있음
• 필드의 크기가 크면 인덱스의 크기도 커짐
• 인덱스를 지정하면 데이터 삽입, 수정, 및 삭제의 성능이 감소될 수 있음

 

4-1. 범위 조건 검색일 때 인덱스 사용 주의사항

• 인덱스는 특정 열에 대한 검색을 빠르게 수행할 수 있도록 테이블의 데이터를 정렬하여 저장함
• 인덱스의 효율성은 범위 조건 검색의 시작점과 종료점을 찾는 것에 크게 영향을 받음
• 예를 들면, `WHERE age BETWEEN 20 AND 30` 과 같은 쿼리 실행 시
  • `age` 열에서 20~30까지의 범위를 찾아야 함
  • 만약 인덱스에서 20~30까지의 값이 연속적으로 저장되어 있다면 인덱스를 효율적으로 사용 가능
  • 만약 인덱스에 20,25,30,35와 같이 불규칙하게 저장되어 있다면 인덱스를 사용할 수 있으나 매우 많은 페이지를 탐색해야 하므로 검색 성능이 떨어짐
• 위 예시를 이유로 범위 조건 검색에서는 인덱스의 효율성이 상대적으로 떨어질 수 있음